王道数据结构总结1
需积分: 0 156 浏览量
2022-08-04
14:09:34
上传
评论 1
收藏 770KB PDF 举报
第一章 绪论
1.1 时间复杂度的求法
（一）循环主体中的变量参与循环条件的判断
a) 找出基本操作
b) 设基本操作执行次数为 T(n)，根据初始条件和基本操作语句确定变量与次数的关系式
c) 带回循环条件，求出 T(n)，确定 O(n)
（二）循环主体中的变量与循环条件无关
（1） 递归程序
a) 确定递推关系（注意这里确定的是基本操作次数的递推关系）
b) 推出递推关系与执行次数的表达式
c) 令低级递推关系中的次数为常数（0 或 1），整理式子
d) 推导出 T(n)
（2） 非递归程序
等比、等差数列求和
1.2 实例
王道单科 P8，综合第二题
1） 归类：循环主体中的变量参与循环条件的判断
基本操作：i++(注意不是 k 参与循环条件的判断)
初始条件 i=1,执行一次 i 加一，值为 2;执行第二次，i 再加一，值为 3；…；执行 T(n)
次，i 的值为 T(n)+1;
带回循环变量：i<n-1,终止条件为 i=n-1;既 T(n)+1=n-1
推出 T(n)=n-2,所以 T(n)=O(n)
2） 归类：循环主体中的变量参与循环条件的判断
基本操作：y=y+1
初始条件 y=0;执行一次 y 加一,执行 T(n)次后值 y=T(n);
带回循环变量：(T(n)+1)*(T(n)+1)>n
剩余25页未读，继续阅读
评论0