时间的复杂性
一般来说，算法中基本操作语句的重复执行次数是具有问题规模n的函数，由t(n )表示，某个辅助函数f (n ) )，使得当n接近无限大时，t(n )/f (n )的极限值成为不等于零的常数标记为t(n )=o ) f(n )，o ) f(n )称为算法的渐进时间复杂度，简称为时间复杂度。
t(n )不同，但时间的复杂性可能相同。 例如，t(n )=n 7n 6和t ) n )=3n 2n 2是t ) n )不同，但是时间复杂度相同，都是o ) n。
计算时间复杂度的方法：用常数1替换运行时间中的所有加法常数t(n )=n7n6=t(n )=n 7n 1
在修正后的执行次数函数中，仅保持最高位项t(n )=n7n1=t ) n )=n
系数t(n )=n=t ) n )=n=o ) ) ) ) ) ) ) ) ) )
简言之，发现函数f[n]和t[n]对于复杂度的表示是等价的
当这个n接近无限大时
而且这个F(N )更容易计算，嗯
一般时间的复杂性
这敲了黑板，重点了
常数级o () (1) ) )。
对数阶数o(log2n ) )。
线性阶数o(n )
线性阶数o(nlog2n ) )。
平方阶数o(n^2) ) ) ) ) ) ) ) ) ) )。
步骤o(n )3)立方
次数ko(n^k ) ) ) )。
指数阶数o(2^n ) )。
留下高阶项和他的系数
说明：
常见算法的时间复杂度按从小到大的顺序依次为(1) )(log2n ) ) ) nlog2n ) ) n2 ) ) n3 ) ) 2n )，问题的规模变大
只要你的算法出现指数级数，你的算法一定很慢
常数阶是最稳定的
举个例子
常数级o () (1) ) )。
无论执行了多少代码，如果是没有循环等复杂结构，则该代码的时间复杂度为o(1)
int i=1；
int j=2；
I；
j；
int m=i j；
如果在运行时，消耗时间不会随着变量的增加而增加，则上述代码可以用o(1)表示时间的复杂性，无论这类代码有多长，有数万、几十万行。
对数阶数o(log2n ) )。
int i=1；
wile(I
{
i=i*2；
}
说明：在while循环中，每次I加倍，上车后，I逐渐接近n。 假设循环x次后，I大于2。 此时，该循环结束。 也就是说，2的x次方是n，x=log2n即循环log2n次后，此代码结束。 该代码的时间复杂度是o(log2n )。 o(log2n )的这两个小时随代码而变化，i=i * 3为o ) O(log3n )。
回头看看
线性阶数o(n )
for(I=1； i=n； I )
{
j=i；
j；
}
说明：
因为该代码执行n次for循环中的代码，所以消耗时间随着n的改变而改变，所以所有这样的代码可以由o(n )来表示时间复杂度
对数阶数为o(nlogn )
for(m=1； 米
{
i=1；
wile(I
i=i*2；
}
}
说明：线性对数阶o(nO(O(logn )其实非常容易理解，将时间复杂度为o ) logn的代码循环n次，其时间复杂度为n * o (logn )即nlogn )
平方步骤o(n )
for(x=1； I
{
for(I=1； i=n； I )
{
j=1；
j；
}
}
说明：平方阶数o(n )更容易理解。 o )如果将n )的代码再次嵌套循环，其时间复杂度为o ) n )。 这个代码实际上是嵌套了两层n环，其时间复杂度为o ) nn )。 也就是说，如果o ) n )将一个循环的n变为m，则其时间复杂度为o ) Mn )。
立方阶o(n )、k次幂阶o (n ^ k ) ) )。
说明：参考上面的o(n )来理解就好了。 o ) n )相当于三层n循环。 其他都很像
本作品采用《CC 协议》，转载时需注明作者与正文的链接
秋叶夏风