1、
算法的复杂性出现在《数据结构》这门课的第一章。 因为涉及到一点数学题，很多学生感到很难。 另外，这个概念也不是很具体，所以很多学生都顾不上复习。 以下就此问题对考生进行分析。
首先理解几个概念。 一个是时间的复杂性，另一个是渐近时间的复杂性。 前者是某一算法的时间消耗，它是该算法求解问题规模n的函数，后者是当问题规模趋向无限大时，该算法的时间复杂度的量级。
评估算法的时间性能时，主要标准是算法的渐近时间复杂度。 因此，在分析算法时往往不区分两者，渐近时间复杂度t(n )=o ) (f ) )常简称为时间复杂度，其中f ) n )一般是算法中频率最高的句子频率。
另外，算法中的句子频率不仅与问题的规模有关，还与输入事例中各要素的取值有关。 但是，我们总是想到最坏情况下的时间复杂性。 避免算法的执行时间变得更长。
典型时间复杂度为常数阶o(1)、对数阶o ) O(log2n )、线性阶o ) n )、线性对数阶o ) nlog2n )、平方阶o(n^2)、立方阶o ) n^3)、k次方阶o ) n^k )
我们通过例子说明，让大家知道遇到问题时怎么解决。
1、将三个函数f、g、h分别设定为f(n )=100n ) 3n )2) 1000，g ) n )=25n ) 35000n ) 2，h ) n )=n ) 1.55000nlgn
请判断以下关系是否成立。
(1) f ) n )=o ) g ) n ) )
)2) g(n )=o ) f ) n ) )
((3) h ) n )=o(n^1.5 ) ) ) ) ) ) ) ) ) ) ) h ) h ) h ) n ) n ) n ) n ) n ) ) n ) ) n ) ) ) n ) n ) ) n ) n ) ) 652 )
(4) h ) n )=o ) nlgn ) )。
现在我们来复习一下渐近时间复杂度的表示法t(n )=o (f ) )。 这里的) o )是数学符号，严格的定义是(t ) n )和f ) n )如果是正整数集合中定义的两个函数，那么t(n )=o ) f ) n )存在正整数c和n0。 '通俗地说，这两个函数在整数自变量n趋向无限大时，两者之比是不等于0的常数。 这样比较容易计算吧。
(1)成立。 在问题中，由于两个函数的最高次项都是n^3，当n时，两个函数的比为常数，因此该关系式成立。
)2)成立。 和上面一样。
)3)成立。 和上面一样。
)4)不成立。 当n时，由于n￣1.5比nlgn增加得快，h(n )与nlgn之比不是常数，因此不成立。
2、假设n是正整数，并且使用大的' o '符号将以下块的执行时间表示为n的函数：
(1) i=1； k=0
wile(I
{ k=k 10*i； I；
}
答案： t(n )=n-1，t ) n )=o ) n )此函数以线性阶数增加。
)2) x=n； //n1
while(x=(y1 ) * (y1 ) )
y；
解答：如果t(n )=n1/2，t ) n )=o ) n1/2，最坏的情况下y=0，则循环的次数为n1/2次，是在平方根步骤中增加的函数。
)3) x=91； y=100；
wile(y0 ) )。
是if(x100 )
{x=x-10； y----； }
else x；
答案： t(n )=o ) 1、这个程序看起来有点可怕。 总共循环了1000次，你看到没有n了吗？ 不。 这个程序的执行与n无关。 即使它被回收利用了一万年，我们也和他无关，只是常数阶的函数。
一条经验法则
有以下复杂的关系
c log2N n n * Log2N n^2 n^3 2^n 3^n n！
其中，c是常数。 在某算法复杂度为c、log2N、n、n*log2N的情况下，该算法时间效率高。 2^n的话，3^n，n！ 于是，稍微大一点的n就不能动这个算法了，中间的几个人没有很强的意思。
2、
学习算法的学生如果不知道该如何计算计算一个算法的时间复杂度，其实是一件很尴尬的事情。 最近选了高级算法这门课，因为时间紧，本来想混着算，没想到考试的时候有40%的试题计算了时间的复杂性，所以干脆就总结了。
概念也不说。 大家都知道。 重要的是如何计算。
求解算法时间复杂度的具体步骤如下。
找出算法中的基本语句
算法中执行次数最多的句子是基本句子，通常是最内层循环的循环体。
计算基本语句执行次数的数量级
只需计算基本语句执行次数的数量级。 这意味着只要保证基本语句执行次数函数中的最高次幂是正确的即可，低次幂和最高次幂的所有系数都可以忽略。 这简化了算法分析，使我们可以将注意力集中在增长率这一最重要的点上。
用大符号表示算法的时间性能。
将基本语句的执行次数的命令放入大符号。
如果算法包含嵌套循环，则基本语句通常为最内层循环体，如果算法包含并行循环，则添加并行循环的时间复杂度。 例如：
for(I=1； i=n； I )
x；
for(I=1； i=n； I )
for(j=1； j=n； j )
x；
第一个for循环的时间复杂度为(n )，第二个for循环的时间复杂度为) ) n2 )，算法整体的时间复杂度为) ) n2 )=) n2 )。
一般算法的时间复杂度从小到大如下。
(1) ) ((log2n ) () ) ) (nlog2n ) ) ) ) ) ) 2n ) ) ) 2n ) ) 652 )
)1)表示基本语句的执行次数为常数，一般来说，只要算法中不存在线性语句，则其时间复杂度为) )1)。 (log2n )、) n )、) nlog2n )、) n2 )和) n3 )称为多项式时间，) 2n )和) n！ 被称为指数时间。 计算机科学家一般认为前者是一种有效的算法，这类问题称为p类问题，后者称为NP问题。
这只是基本计算时间的复杂性，具体的执行也与硬件有关。