药物研发网站怎么做,wordpress资讯类主题破解版,如何给网站做引流,做网站备案不少天我们先给出推导的方法#xff0c;然后下面一步一步来推导。
推导大O阶
用常数1取代运行时间中的所有加法常数在修改后的运行次数函数中#xff0c;只保留最高阶项如果最高阶存在且不是1#xff0c;则去除这个项相乘的常数所得结果即为大O阶
示例
int sum 0#xff0c;…我们先给出推导的方法然后下面一步一步来推导。
推导大O阶
用常数1取代运行时间中的所有加法常数在修改后的运行次数函数中只保留最高阶项如果最高阶存在且不是1则去除这个项相乘的常数所得结果即为大O阶
示例
int sum 0n 100; //以分号结尾代码执行一次
sum (1n)*n/2 //执行一次
contsumendl; //执行一次运行次数为3而在上面推导的推导大O阶方法中我们说了用1代码所有的加法什么意思呢我们的3是经过111算出来的我们用1代替所有的加法。而这个表达式只有1没有最高阶项所以结果1即为大O阶。我们把具有O1的时间复杂度的叫做常数阶。
int i;
for(i 0;in;i)
{/*其他常数阶程序代码*/
}我们可以发现花括号里的就是常数阶而for循环循环了n次也就是说做了n常数阶次执行次数根据上面推导大O阶方法我们找到了最高阶项n舍弃后面常数项所以我们的时间复杂度为O(n)我们把这类情况称为线性阶。
顺便一提一般来说我们分析算法的时间复杂度关键就是分析循环结构的运行情况。
int count 1;
while(count n)
{count count * 2;/*其他常数阶程序代码*/
}从这里的代码我们可以看出退出循环的条件是countn而count是通过自身乘2来更新自我然后跳出循环的。也就是说设count更新次数为x其可以写出2xn2^{x}n2xn的式子而我们大O(n)里面的n实际上指的是这里的x根据高中数学所学的指对互换我们可以写出xlog2nx log_2nxlog2n。所以这个循环的时间复杂度为O(logn)我们把这类情况叫做对数阶。
int i ,j ;
for (i - 0; i n; i) {for ( j - 0 ; j n ; j ){/*时间复杂度为O(1)的程序步骤序列*/}
}对于这种就不必多说了时间复杂度为O(n2)(n^2)(n2)。我们把这类情况叫做平方阶。
说完上面所有的情况了现在我们来几个题来练手。
x 0;y 0;
for(int k 0;kn;k){x;
}
for(int i 0;in;i){for(int j 0;jn;j){y;}
}分析算法根据推导大O阶方法第一行执行1次第一个循环执行n次第一个内嵌循环外层n次内层n次也就是n的平方。把常数变为1然后抓大头最高项系数为1那么只剩下n2n^2n2。所以该代码的时间复杂度为O(n2)(n^2)(n2)从完整的代码分析下来我们也可以发现实际上我们只需要找最复杂的那个循环开始分析就可以了因为其他的代码所含的时间复杂度最终根据推导大O阶方法都会被省略。下面看一个比较难的例子。
void exam(fload x[][],int m,int n)
{float sum[];for(int i 0;im;i){sum[i] 0.0;for(int j 0;jn;j){sum[i]x[i][j];}}for(i 0;im;i)couti:sum[i]endl;
}最复杂的就是中间的内嵌循环外层循环为从0到m内层循环0到n所以该时间复杂度应为O(mn)。
for(i 1;in;i)for(j 1;jn;j){c[i][j]0;for(k 1;kn;k)c[i][j] c[i][j]a[i][k]*b[k][j];}上面这个是一个N×N矩阵相乘的算法连续三层循环第一次执行次数为n第二层执行次数也为n第三层执行次数还是n。所以该题算法复杂度为O(n3)(n^3)(n3)。
for(i 1;in;i)for(j1;ji;j)for(k1;kj;k)x x1这里最外层执行次数n但是最外层执行1次第二层就循环1次最外层执行第2次第二层循环两次根据等差数列求和公式即第二层有123…n即n(1n)2\frac{n(1n)}{2}2n(1n)次。当然第三层就不好理解了所以我们接下来换一种方法。
对于三层循环问题我们还是直接列出最外层的前几项比较好。在i 1的时候内层循环全部加起来只循环一次。在i 2的时候第二层循环启动两次循环所以总共执行12对于i 3第二层启动三次循环第三层也是三次循环。也就是说总共执行123。如果听不太懂我们可以用图来表示即 所以实际上以上规律是由n来控制的从上面的图来看的话根据我们所得规律i1里面有一个i(1i)2\frac{i(1i)}{2}2i(1i)i 2里面也有一个i(1i)2\frac{i(1i)}{2}2i(1i)以此类推我们可以写出下面的式子∑i1ni(i1)2\sum^n_{i1}\frac{i(i1)}{2}∑i1n2i(i1)。
我们化简一下上面的式子∑i1n(i22i2)12∑i1n(i2−i)\sum^n_{i1}(\frac{i^2}{2}\frac{i}{2}) \frac1 2\sum^n_{i1}(i^2-i)∑i1n(2i22i)21∑i1n(i2−i)。
这里用等差求和公式带入求解即可得出答案n(n1)(n2)6\frac{n(n1)(n2)}{6}6n(n1)(n2)根据我们前面说的大O阶推导可以得出本题的时间复杂度为n3n^3n3。
