关于算法时间复杂度的计算
我们常需要描述特定算法相对于 n(输入元素的个数 )需要做的工作量。在一组未排序的数据中检索,所需的时间与 n
成正比;如果是对排序数据用二分检索,花费的时间正比于 logn。排序时间可能正比于 n2 或者 nlogn。
我们希望能够比较算法的运行时间和空间要求,并使这种比较能与程序设计语言、编译系统、机器结构、处理器的
速度及系统的负载等复杂因素无关。
为了这个目的,人们提出了一种标准的记法,称为“大 O 记法”.在这种描述中使用的基本参数是 n,即问题实例的规
模,把复杂性或运行时间表达为 n 的函数 。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是
说 它需要“通过 logn 量级的步骤去检索一个规模为 n 的数组”记法 O ( f(n) )表示当 n 增大时,运行时间至多将以正
比于 f(n)的速度增长。这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差
异。例如,一个低附加代价的 O(n2)算法在 n 较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当
然,随着 n 足够大以后,具有较慢上升函数的算法必然工作得更快。
Temp=i;
i=j;
j=temp;
以上三条单个语句的频度均为 1,该程序段的执行时间是一个与问题规模 n 无关的常数。算法的时
间复杂度为常数阶,记作 T(n)=O(1)。如果算法的执行时 间不随着问题规模 n 的增加而增长,即使算法中有上千条
语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是 O(1)。
例 2.1.交换 i 和 j 的内容
1) sum=0; (一次)
2) for(i=1;i<=n;i++)(n 次 )
3) for(j=1;j<=n;j++)(n^2 次 )
4) sum++; (n^2 次 )
解:T(n)=2n^2+n+1=O(n^2)
例 2.2.
for(i=1;i<n;i++)
{
y=y+1;①