数据结构和算法复习资料.pdf

文档介绍：★ 考试知识点★ 1
复****br/>★ 考试知识点★ 2
考试方案
题型：
选择题（ 15*2 ）
填空（ 10*2 ）
简答题（ 6*5 ）
程序设计题 （ 10*2 ）
★ 考试知识点★ 3
重点问题讲解
时间复杂度
对于循环程序，一般看有几重循环
例 int fun(int n) {
int i=1, s=1;
while(s<n) s+=++i; // 时间复杂度为 O（ n）
return i; }
★ 考试知识点★ 4
for(i=1;i<=n;i=2*i)
printf( “ i=%d\n ” ,i); // 时间复杂度为 O（ log2 （n））
解释 : 设循环执行 x 次
i 的值 执行次数
i=2^0 1
i=2^1 2
i=2^2 3
... ...
i=2^x-1 x
i<=n 即为 2^(x-1) <= n 解得 x<= log2 （ n） -1 注意：是趋近！用大 O
Int x=n;
Int y=0;
While(x>=(y+1)*(y+1)) // 时间复杂度为 O（ n）
y++;
解释 : 设循环执行 a 次
y 的值 执行次数
y=0 1
y=1 2
y=2 3
... ...
y=x a
(y+1)(y+1)<=x 即为 (a+1)(a+1)<=x 解得 a <= n^(1/2)-1 注意：是趋近！用大 O
★ 考试知识点★ 5