（1）一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析 T(n)的数量级。算法中基本运算(最深层循环中的语句)的频度与T(n)同数量级，因此通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度。于是，算法的时间复杂度记为T(n)= O(f(n))
式中，0的含义是 T(n)的数量级，其严格的数学定义是：若(n)和n)是定义在正整数集合上的两个函数，则存在正常数C和 n0，使得当 n≥n0时，都满足 0≤ T(n)< Cf(n)。

（2）算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质(如输入数据元素的初始状态)。例如，在数组A[0...n-1]中，查找给定值k的算法大致如下:


(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3) i--;
(4)return i;

该算法中语句3(基本运算)的频度不仅与问题规模n有关，而且与下列因素有关:

① 若A中没有与k相等的元素，则语句3的频度f(n)=n。

②若A的最后一个元素等于k，则语句3的频度f(n)是常数 0。

最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度是指在最好情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长在分析一个程序的时间复杂性时，有以下两条规则:

1)加法规则:T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

2)乘法规则:T(n)=T1(n)xT2(n)=O(f(n))xO(g(n))=O(f(n)xg(n))

例如，设 a{}、b{}、c{}三个语句块的时间复杂度分别为 O(1)、0(n)、O(n)，则


① a{
     b{ }
          c{ }
  }       //时间复杂度为O(n方),满足加法规则
 
 
② a{
     b{
          c{ }
      }
 }       //时间复杂度为O(n的3次方)，满足乘法规则

渐近时间复杂度为
O(1)< O( $log_{2}n$ )< O(n)< O( $nlog_{2}n$ )<O( $n^{2}$ )< О( $n^{3}$ )< О( $2^{n}$ ) < O(n!)< O( $n^{n}$ )

3.算法的空间性能分析

3.1空间复杂度

（1）算法的空间复杂度S(n)定义为该算法所需的存储空间，它是问题规模n的函数S(n)=O(g(n))
（2）一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需一个程序在执行时除需要存储空间来存放为实现计算所需信息的辅助空间。若输入数据所占要一些对数据进行操作的工作单元和存储一些分析除输入和程序之外的额外空间。例如，若算法空间只取决于问题本身，和算法无关，则只需中新建了几个与输入数据规模n相同的辅助组，则空间复杂度为 O(n)。算法原地工作是指算法所需的辅助空间为常量，即 O(1)。

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