Big O notation大零符号一般用于描述算法的复杂程度，比如执行的时间或占用内存（磁盘）的空间等，特指最坏时的情形。 Linus Torvalds说过“Talking is cheap, show me the code.”，那我们直接从代码(Python)上来学习Big O吧。
O(1)
def isFirstElementNull(elements, value): return elements[0] == value #print isFirstElementNull(["1","2"],"1")无论输入参数是什么，这个函数就只执行一次，所以它的复杂度为O(1)。
O(N)
def containsValue(elements, value): for e in elements: if e == value: return True return False #print isFirstElementNull(["1","2"],"1")这里有一个for循环，如果运气好就执行一次（elements里第一个值就跟value一样），运气不好就要执行N次（N等于elements的长度，碰巧elements里最后一个值跟value一样），因为Big O是表示最坏时情形，所以这个函数的复杂度为O(N)，好理解吧。
O( N2 )
def containsDuplicates(elements): for m in range(len(elements)): for n in range(len(elements)): if (m != n) and elements[m] == elements[n]: return True return False #print containsDuplicates(["1","2","3","2"])这里有两个嵌套的for循环，所以执行最多的次数肯定为两个for循环次数相乘，即N*N（N等于elements长度），所以这个函数的复杂度为O(N2)。
O( 2N )
def fibonacci(num): if num < 2: return num return fibonacci(num - 2) + fibonacci(num - 1) #print fibonacci(5)这是计算斐波那契数的函数，用递归方式实现，不太容易一下就看出执行了多少次。不要紧，我画了个图，这样就方便直观了。 容易看出执行多少次了吧，即2的N次方，所以这个函数的复杂度为O(2N)。 对了，斐波那契函数是什么鬼，看看下面这个图你立马就明白了。
O(logN) 是不是一看log（对数）就头大，其实没那么复杂，在看例子前我们先复习复习高中知识，什么是log。
如果x的y次方等于n（x>0，且x不等于1），那么数y叫做以x为底n的对数（logarithm） 记作logx n =y。其中，x叫做对数的底数。
1.底数为10时，写为lg； 2.底数为e时，称为自然对数写为ln,这个在高等数学中用的很多； 3.底数为2时，主要用在计算机中，写为log，也就是不写底数；
所以我们说的logN其实就是log2 n
我们以Binary Search（也叫拆半查询和二分查询）为例，感觉查询过程就跟切西瓜一样，先中间切一刀，然后选一块，再在选定的半个西瓜上再来一刀，再决定选哪块，再切再选，最后找到满意的，即1/2,1/4,1/8,1/16…这样下去。以下是算法脚本
public int binarySearch(int array[],int key) { int begin = 0; int end = array.length - 1; while (begin <= end) { int mid = begin + (end - begin) / 2; if (array[mid] > key){ end = mid - 1; } else if (array[mid] < key){ begin = mid + 1; }else{ return mid; } } return -1; }以下是测试程序
int[] a1 = {1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,100}; int result = binarySearch(a1, 4); System.out.println(result); //output: 3其实这样一刀一刀的找就是2的倍数关系，比如切了3刀找到，那就有8块了（其实是4块，因为你只切选中的那一块，但为了计算方便，我们就当把西瓜都切了），即2的3次方，如果切5刀找打，那就有32块，即2的5次方，所以这个算法的时间复杂度就是O(log2 N )，即O(logN)。
