数据结构杂谈番外篇——时间复杂度计算

我们先给出推导的方法&＃xff0c;然后下面一步一步来推导。

推导大O阶

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中&＃xff0c;只保留最高阶项
3. 如果最高阶存在且不是1&＃xff0c;则去除这个项相乘的常数
4. 所得结果即为大O阶

示例

int sum &＃61; 0&＃xff0c;n &＃61; 100; //以分号结尾&＃xff0c;代码执行一次
sum &＃61; (1&＃43;n)*n/2 //执行一次
cont<

运行次数为3&＃xff0c;而在上面推导的推导大O阶方法中我们说了&＃xff0c;用1代码所有的加法&＃xff0c;什么意思呢&＃xff1f;我们的3是经过1&＃43;1&＃43;1算出来的&＃xff0c;我们用1代替所有的加法。而这个表达式只有1&＃xff0c;没有最高阶项&＃xff0c;所以结果1即为大O阶。我们把具有O&＃xff08;1&＃xff09;的时间复杂度的叫做常数阶。

int i;
for(i &＃61; 0;i{/*其他常数阶程序代码*/
}


我们可以发现&＃xff0c;花括号里的就是常数阶&＃xff0c;而for循环循环了n次&＃xff0c;也就是说&＃xff0c;做了n&＃43;常数阶次执行次数&＃xff0c;根据上面推导大O阶方法&＃xff0c;我们找到了最高阶项n&＃xff0c;舍弃后面常数项&＃xff0c;所以我们的时间复杂度为O(n)&＃xff0c;我们把这类情况称为线性阶。

顺便一提&＃xff0c;一般来说&＃xff0c;我们分析算法的时间复杂度&＃xff0c;关键就是分析循环结构的运行情况。

int count &＃61; 1;
while(count {count &＃61; count * 2;/*其他常数阶程序代码*/
}


从这里的代码我们可以看出&＃xff0c;退出循环的条件是count2x&＃61;n2^{x}&＃61;n2x&＃61;n的式子&＃xff0c;而我们大O(n)里面的n实际上指的是这里的x&＃xff0c;根据高中数学所学的指对互换&＃xff0c;我们可以写出x&＃61;log2nx &＃61; log_2nx&＃61;log2​n。所以这个循环的时间复杂度为O(logn)&＃xff0c;我们把这类情况叫做对数阶。

int i ,j ;
for (i - 0; i }


对于这种就不必多说了&＃xff0c;时间复杂度为O(n2)(n^2)(n2)。我们把这类情况叫做平方阶。

说完上面所有的情况了&＃xff0c;现在我们来几个题来练手。

x &＃61; 0;y &＃61; 0;
for(int k &＃61; 0;k}
for(int i &＃61; 0;i}


分析算法&＃xff0c;根据推导大O阶方法&＃xff0c;第一行执行1次&＃xff0c;第一个循环执行n次&＃xff0c;第一个内嵌循环外层n次&＃xff0c;内层n次&＃xff0c;也就是n的平方。把常数变为1&＃xff0c;然后抓大头&＃xff0c;最高项系数为1&＃xff0c;那么只剩下n2n^2n2。所以该代码的时间复杂度为O(n2)(n^2)(n2)&＃xff0c;从完整的代码分析下来我们也可以发现&＃xff0c;实际上我们只需要找最复杂的那个循环开始分析就可以了&＃xff0c;因为其他的代码所含的时间复杂度最终根据推导大O阶方法都会被省略。下面看一个比较难的例子。

void exam(fload x[][],int m,int n)
{float sum[];for(int i &＃61; 0;i}


最复杂的就是中间的内嵌循环&＃xff0c;外层循环为从0到m&＃xff0c;内层循环0到n&＃xff0c;所以该时间复杂度应为O(m&＃43;n)。

for(i &＃61; 1;i<&＃61;n;i&＃43;&＃43;)for(j &＃61; 1;j<&＃61;n;j&＃43;&＃43;){c[i][j]&＃61;0;for(k &＃61; 1;k<&＃61;n;k&＃43;&＃43;)c[i][j] &＃61; c[i][j]&＃43;a[i][k]*b[k][j];}


上面这个是一个N×N矩阵相乘的算法&＃xff0c;连续三层循环&＃xff0c;第一次执行次数为n&＃xff0c;第二层执行次数也为n&＃xff0c;第三层执行次数还是n。所以该题算法复杂度为O(n3)(n^3)(n3)。

for(i &＃61; 1;i<&＃61;n;i&＃43;&＃43;)for(j&＃61;1;j<&＃61;i;j&＃43;&＃43;)for(k&＃61;1;k<&＃61;j;k&＃43;&＃43;)x &＃61; x&＃43;1&＃xff1b;


这里最外层执行次数n&＃xff0c;但是最外层执行1次&＃xff0c;第二层就循环1次&＃xff1b;最外层执行第2次&＃xff0c;第二层循环两次&＃xff1b;根据等差数列求和公式&＃xff0c;即第二层有1&＃43;2&＃43;3&＃43;…&＃43;n&＃xff0c;即n(1&＃43;n)2\frac{n(1&＃43;n)}{2}2n(1&＃43;n)​次。当然第三层就不好理解了&＃xff0c;所以我们接下来换一种方法。

对于三层循环问题&＃xff0c;我们还是直接列出最外层的前几项比较好。在i &＃61; 1的时候&＃xff0c;内层循环全部加起来只循环一次。在i &＃61; 2的时候&＃xff0c;第二层循环启动两次循环&＃xff0c;所以总共执行1&＃43;2&＃xff0c;对于i &＃61; 3&＃xff0c;第二层启动三次循环&＃xff0c;第三层也是三次循环。也就是说总共执行1&＃43;2&＃43;3。如果听不太懂&＃xff0c;我们可以用图来表示&＃xff0c;即&＃xff1a;

所以实际上以上规律是由n来控制的&＃xff0c;从上面的图来看的话&＃xff0c;根据我们所得规律&＃xff0c;i&＃61;1里面有一个i(1&＃43;i)2\frac{i(1&＃43;i)}{2}2i(1&＃43;i)​&＃xff0c;i &＃61; 2里面也有一个i(1&＃43;i)2\frac{i(1&＃43;i)}{2}2i(1&＃43;i)​&＃xff0c;以此类推我们可以写出下面的式子&＃xff1a;∑i&＃61;1ni(i&＃43;1)2\sum^n_{i&＃61;1}\frac{i(i&＃43;1)}{2}∑i&＃61;1n​2i(i&＃43;1)​。

我们化简一下上面的式子&＃xff1a;∑i&＃61;1n(i22&＃43;i2)&＃61;12∑i&＃61;1n(i2−i)\sum^n_{i&＃61;1}(\frac{i^2}{2}&＃43;\frac{i}{2}) &＃61; \frac1 2\sum^n_{i&＃61;1}(i^2-i)∑i&＃61;1n​(2i2​&＃43;2i​)&＃61;21​∑i&＃61;1n​(i2−i)。

这里用等差求和公式带入求解&＃xff0c;即可得出答案n(n&＃43;1)(n&＃43;2)6\frac{n(n&＃43;1)(n&＃43;2)}{6}6n(n&＃43;1)(n&＃43;2)​&＃xff0c;根据我们前面说的大O阶推导&＃xff0c;可以得出本题的时间复杂度为n3n^3n3。