文档介绍：
算法分析的两个主要方面姑算法的时反复杂度和空间复杂度，其目的主要是考察算法 的时间和空间效率，，星于运算空间(内 存)较为充足，所以把将法的时间复杂度作为分析的重点•
所谓一个语句的频度， 度之和记做T(n),它是该算法所求解问题规模n的函数，当阿题的规模n趋向无穷大时，T(n) 的数量级称为渐近时间轻杂度，简称为时间复杂度，记作T(n)9(Rn)).
上述表达式中“0”的含义是T(n)的数鼠级，其严格的数学定义是：若T(n)和Rn) 是定义在正整数羹合上的两个函数，则存在正的常数C和财,使得当nNno时，总是满足 OWT(n) WC・Rn)。但是我们总是考虑在最坏情况下的时间复杂度，以保证算法的运行时 间不会比它更长.
Function Name
(SPUOQ<X)S=E) 6ucuncr
5040
30
20
o
60
90
8070
c
Constant
log"
Logarithmic
log27V
Log-squared
N
Linear
NlcgN
N'ogN
N2
Quadratic
N3
Cubic
2村
Exponential
Input Size (N)
(spuooas)oluHgcuncc
Input Size (N)
(5 ) ▲若 Ti(n)-nlog2n+10001og2n , T2(n)-nlog23-1000log2n . T3(n)=n--10001og2n T4(n)=2nlog2n-10001og2n中，则其中渐进时间最小的是T2(n).
提示：Ti(n)=nlog2n+1000log2n=0(nlog2n)，T2(n)=iilog23-10001og2n=0(n).
T3(n)^n2-10001ogin=0(n2), T4(n)=2nlog2n-1000log2n=0(nlog2n).
【练习12】 ▲下述函数中渐近时间最小的是哪些？
T1 (n)=nlog2n+1 OOOlogin
T2(n)=nlogj3-!OOOIog2n
T3(n>n2-1000log2n
(4 ) T4(n)-2nlog2nT OOOlo&n
【解】T, (n>O(nlog2n), T2(n)=O( n10*33). T3(n)=O(n2), T4(n)0(nlog2n).从中看到, Tt(n)> TJn)最小。但Ti(n)TnT000)log2n, T4(n)=(2n- 1000)log2n,显然，n足够大时， Ti(n)<T4(n).所以，渐近时间最小的是T,(n)»
。⑴
Temp=i;i=j ;j=temp;
以上二条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算 法的时间复杂度为常数阶，记作T(n)=O(l)o如果算法的执行时间不随着问题规模n的增加 而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间 复杂度是O(l)o
交换i和j的内容
sum=O； (一次)
fbr(i=l;iv=n;i++) (n 次)
for(j=l;jv=n