文档介绍：1,2 2算法分析
算法分析的两个主要方面是鼻法的时间复杂度和空间复杂度・英目的主要是考察尊法 的时间和空间效率，以求改进算法或对不同的境法琲行比较。一玻情况下’鉴于运算空间(内 存战为充足，所以把算法的时间复杂度作为分析的重点*
所谓++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解：当i=m, j=k的时候，内层循环的次数为k当i=m时,j可以取,所以这里最内 循环共进行了 0+1+...+m-1=(m-1)m/2次所以,i从0取到n,则循环共进行了 ： 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为 0("3).
我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 0("2)，但期望时间是O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即0("2)情况)的概率减小到几乎等于0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：
访问数组中的元素是常数时间操作，或说0(1)操作。
一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取O(logn)时间。
用strcmp比较两个具有n个字符的串需要O(n)时间。
常规的矩阵乘算法是0("3),因为算出每个元素都需要将n对元素相乘并加到一起，所 有元素的个数是"2。
指数时间算法通常来源于需要求出所有可能结果。
例如，n个元素的集合共有2n个子集，所以要求出所有子集的算法将是0(2n)的。
:-D指数算法一般说来是太复杂了，除非n的值非常小，因为，在这个问题中增加一个元 素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名的“巡回售货员问题” )，到目 前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果 的算法替代之。
常见的时间复杂度，按数量级递增排列依次为：常数阶0(1)、对数阶O(log2n)、线性阶O(n)、 线性对数阶O(nlog2n)、平方阶O(M2)、立方阶O(M3)、k次方阶O(nAk)＞指数阶0(25)。 下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。
1、设三个函数 f,g,h 分别为 f(n)=100nA3+nA2+1000 , g(n)=25nA3+5000nA2 ,
h(n)=+5000nlgn
请判断下列关系是否成立：
f(n)=O(g(n))
g(n)=O(f(n))
h(n)=0(")
( 4 ) h(n)=O(nlgn)
(1)成立。题中由于两个函数的最高次项都是nA3，因此当n—w时，两个函数的比值是一 个常数，所以这个关系式是成立的。
( 2)成立。与上同理。
( 3)成立。与上同理。
(4)不成立。由于当n—，所以h(n)与 nlgn的比值不是常数, 故不成立。
2、设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
i=1; k=0 while(i<n)
{ k=k+10*i;i++;
}
解答：T(n)=n-1， T(n)=O(n),这个函数是按线性阶递增的。
x=n;