一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

T(n)不同，但是时间复杂度可能相同。如： $T(n)=n^{2}+5n+6$ 与 $T(n)=3n^{2}+3n+2$ 它们的T(n)不同，但是时间复杂度相同，都为 $O(n^{2})$ 。

2、常见的时间复杂度：

常用O()列表以及它们与不同大小输入数据的性能比较

O（）	计算10个元素	计算100个元素	计算1000个元素
O(1)	1	1	1
O(log N)	3	6	9
O(N)	10	100	1000
O(N log N)	30	600	9000
O(N^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301
O(N!)	3628800	9.3e+157	4.02e+2567

常数阶 $O(1)$ ：只要是常数，不管执行多少次，没有复杂结构循环等。

对数阶 $O(log2n)$ ：


int i = 1; //语句执行一次
while(i<n)    //语句执行log n次
{
    i = i * 2;    //语句执行log n次
}

上面的算法中，i 每次都放大两倍，我们假设这个循环体执行了m次，那么2^m = n即m = logn，所以整段代码执行次数为1 + 2*logn，则f(n) = logn，时间复杂度为O(logn)。

线性阶 $O(n)$ ：


for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

线性对数阶 $O(nlog2n)$ ：

这个就是将对数阶代码循环n次。

平方阶 $O(n^{2})$ ：

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

立方阶 $O(n^{3})$ ：

O(n³)相当于三层n循环

k次方阶 $O(n^{k})$ ：

这就是k层n循环

指数阶 $O(2^{n})$ ：

n层2循环

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

3、计算时间复杂度：

（1）了解自己的算法，计算出T(n)

（2）用常数1代替运行时间中的所有加法常数

（3）修改后的运行次数函数中，只保留最高阶项

（4）去除最高阶项的系数

4、平均时间复杂度和最坏时间复杂度：

平均时间复杂度：是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

最坏时间复杂度：一般讨论的时间复杂度均是最坏情况下的时间复杂度，最坏情况下时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏还长了。

三、空间复杂度

1、概念

对一个算法在运行过程中临时占用存储空间的大小，一个算法在计算机存储器上所占用的存储空间，包括算法本身、算数、输入输出临时占用存储空间几个部分。

2、常见空间复杂度

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

用的比较少。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/759757