度量一个程序的执行时间通常有两种方法
事后统计的方法
事前分析估算的方法 O
Ο(1)＜Ο(log n)＜Ο(n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)
大O表示法就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。（当常数非常大而n很小的时候并不是这样的，但是我们现在不要担心这种情况）
规律 Big-O
2 O(1) --> 就是一个常数
2n + 10 O(n) --> n 对整体结果会产生最大影响
5n^2 O(n^2) --> n^2 具有最大影响
O(1):如果算法的执行时间不随着问题规模n的增长而增长，及时算法中有上千条语句，其执行时间也不过是较大的常数。
explain:当你知道key（objects）或者index（arrays）时进行查找只需要一步就可以完成，所用时间就是一个常量。
O(log n):当数据增大n倍时，耗时增大log2(n)倍，即n为256倍时，耗时增大8倍。
explain：如果你知道在一个数组的哪一侧进行查找一个指定值时，你可以排除掉另外一半进而节约时间。
Ο(n)：数据量的增大几倍，耗时也增大几倍。
explain:单层for循环，你必须通过遍历整个数组（或者list）来完成这一任务。单一for循环的时间复杂度通常都是线性的。此外数组方法比如indexOf的复杂度也是线性的。你不过是使用已经抽象了的循环过程。
Ο(n^2)：数据量增大 n 倍时，耗时增大 n 的平方倍。(常见双层for循环)。
explain:for循环嵌套的复杂度就是二次方的，因为你在一个线性操作里执行另外一个线性操作（或者说： n*n =n² ）
O(C^n): 数据量增大n倍时，耗时一个常数的n次方（非常大的数字）。
explain:指数复杂度通常出现在这种情况：你对数据了解甚少，但是你必须尝试其所有的排列或者组合。
网友评论