算法的时间复杂度分析之O(logn)、O(nlogn)

浅浅的花香味﹌ 2022-12-15 11:29 154阅读 0赞

# 复杂度分析之O(logn)、O(nlogn) #

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。我通过一个例子来说明一下。

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

根据我们前面讲的复杂度分析方法，第三行代码是循环执行次数最多的。所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：  
![在这里插入图片描述][20201016153010470.jpg_pic_center]  
所以，**我们只要知道 x 值是多少，就知道这行代码执行的次数了**。通过  2x=n \\textit\{2x=n\} 2x=n 求解 x 这个问题我们想高中应该就学过了，我就不多说了。 x = log ⁡ 2 n x=\\log\_\{2\}n x=log2n，所以，这段代码的时间复杂度就是  O ( log ⁡ 2 n ) O(\\log\_\{2\}n) O(log2n)。现在，我把代码稍微改下，你再看看，这段代码的时间复杂度是多少？

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

根据我刚刚讲的思路，很简单就能看出来，这段代码的时间复杂度为  O ( log ⁡ 3 n ) O(\\log\_\{3\}n) O(log3n)。

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为  O ( log ⁡ n ) O(\\log\_\{\}n) O(logn)。为什么呢？我们知道，对数之间是可以互相转换的， O ( log ⁡ 3 n ) O(\\log\_\{3\}n) O(log3n)就等于  O ( log ⁡ 3 2 ) O(\\log\_\{3\}2) O(log32)\*  O ( log ⁡ 2 n ) O(\\log\_\{2\}n) O(log2n)，所以 O ( log ⁡ 3 n ) O(\\log\_\{3\}n) O(log3n) =  O ( C ∗ log ⁡ 2 n ) O(C\*\\log\_\{2\}n) O(C∗log2n)，其中  C = log ⁡ 3 2 C=\\log\_\{3\}2 C=log32 是一个常量。基于我们前面的一个理论：在采用大  O \\textit\{O\} O 标记复杂度的时候，可以忽略系数，即  O ( C f ( n ) ) = O ( f ( n ) ) O(Cf(n)) = O(f(n)) O(Cf(n))=O(f(n))。所以， O ( log ⁡ 2 n ) O(\\log\_\{2\}n) O(log2n) 就等于  O ( log ⁡ 3 n ) O(\\log\_\{3\}n) O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽对数的“底”，统一表示为  O ( log ⁡ n ) O(\\log\_\{\}n) O(logn)。如果你理解了我前面讲的  O ( log ⁡ n ) O(\\log\_\{\}n) O(logn)，那  O ( n log ⁡ n ) O(n\\log\_\{\}n) O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则吗？

如果一段代码的时间复杂度是  O ( log ⁡ n ) O(\\log\_\{\}n) O(logn)，我们循环执行 n 遍，时间复杂度就是 O ( n log ⁡ n ) O(n\\log\_\{\}n) O(nlogn) 了。而且， O ( n log ⁡ n ) O(n\\log\_\{\}n) O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是  O ( n log ⁡ n ) O(n\\log\_\{\}n) O(nlogn) 。

# 换底公式说明 #

log ⁡ b N = log ⁡ a N log ⁡ a b \\log\_\{b\}N =\\frac\{\\log\_\{a\}N\}\{\\log\_\{a\}b\} logbN=logablogaN  
运用换底公式  
 log ⁡ 3 N = log ⁡ 10 N log ⁡ 10 3 = log ⁡ 10 2 log ⁡ 10 3 ∗ log ⁡ 10 N log ⁡ 10 2 \\log\_\{3\}N =\\frac\{\\log\_\{10\}N\}\{\\log\_\{10\}3\} = \\frac\{\\log\_\{10\}2\}\{\\log\_\{10\}3\}\*\\frac\{\\log\_\{10\}N\}\{\\log\_\{10\}2\} log3N=log103log10N=log103log102∗log102log10N  
再次运用换底公式，将两个分数简化。  
 log ⁡ 3 N = log ⁡ 3 2 ∗ log ⁡ 2 N \\log\_\{3\}N = \\log\_\{3\}2 \* \\log\_\{2\}N log3N=log32∗log2N

# 总结 #

常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。  
![在这里插入图片描述][20201016161928667.jpg]

**转自**数据结构与算法之美

[20201016153010470.jpg_pic_center]: /images/20221123/7c488051c4f348d794de7b6b24b6648c.png
[20201016161928667.jpg]: /images/20221123/3429952bd7d945e0b8dab208137e7be7.png