分析复杂度方法

1. 只需要关注循环次数最多的一段代码
   • 忽略掉常量、低阶、系数
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

对数

在数学中，对数是对求幂的逆运算，正如除法是乘法的逆运算，反之亦然。

分析下方代码复杂度

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

其中 i = i * 2 的执行次数最多

i 的取值：2^0 2^1 2^2 ... 2^x = n

只要知道 x ，就可以求出执行次数

2^x=n 推导出 x=log2n

不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。

因为

对数之间是可以互相转换的，log3n 就等于 log32 log2n，所以 O(log3n) = O(C log2n)， 其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数， 即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里， 我们忽略对数的“底”，统一表示为 O(logn)。

如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了

归并排序、快速排序的时间复杂度都是 O(nlogn)。

练习：

分析下列代码时间复杂度

var isPowerOfThree = function(n) {
    while (n !== 0 && n % 3 === 0) {
        n = Math.floor(n / 3);
    }
    return n === 1;
};

时间复杂度为 O(logn): 当 n 是 3 的幂，程序执行 log3n 次，当 n 不是 3 的幂， 程序执行少于 log3n

当 n 是 3 的幂时，需要除以 3 的次数为 log3n = O(log n)； 当 n 不是 3 的幂时，需要除以 3 的次数小于该值。