作者:民海育来仁湖 | 来源:互联网 | 2023-10-10 14:50
我们先给出推导的方法,然后下面一步一步来推导。
推导大O阶
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中,只保留最高阶项
- 如果最高阶存在且不是1,则去除这个项相乘的常数
- 所得结果即为大O阶
示例
int sum = 0,n = 100; //以分号结尾,代码执行一次
sum = (1+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;log2n。所以这个循环的时间复杂度为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;1n2i(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。