¶ 基本概念
程序=数据结构＋算法
计算机的两大应用领域：
- 数值计算
- 非数值计算（主要）
¶ 基本术语
¶ 数据
计算机处理的数值、字符等符号的总称
¶ 数据元素
数据结构中讨论的基本单位
一个数据元素也可以由一个或若干个数据项组成，数据项是有意义的数据的最小原子单位。
¶ 数据对象
性质相同的数据元素的一个集合
¶ 数据结构
带结构的数据元素的集合/带结构的数据对象
- 逻辑结构
- 集合结构（元素之间无逻辑关系）
- 线性结构
- 非线性结构
- 树状结构
- 图状结构
- 物理结构
- 顺序存储
- 链接存储
- 索引存储
- 散列存储
¶ 抽象数据类型ADT
数据类型：高级程序设计语言所定义的某类数据的集合和定义在该集合上的一组操作的总称。
¶ 算法和算法分析
- 伪代码：介于自然语言和计算机语言之间的文字和符号（包括数学符号）来描述算法。
- 算法和程序的区别
- 算法必须满足有穷性，程序可无穷循环执行
- 算法是运算步骤的模型，程序指令必须可执行
- 算法的定义
- 一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。
- 算法的特征
- 算法的评价标准：
- 正确
- 健壮
- 可读
- 效率
¶ 算法的分析
¶ 时间复杂度
算法所花费的时间代价。
问题的规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由f(1)增至f(n)。此时称该算法的时间复杂度为f(n)。
同一个算法，视面对的数据不同，会导致时间代价不同：
- 最好情况下的时间代价
- 平均情况下的时间代价
- 最坏情况下的时间代价（最常用），用大O法表示
- 关注复杂性的数量级，忽略数量级的系数
- 关注上升最快的一项
- 循环的时间复杂度等于该循环体的复杂度乘以循环的次数
¶ 空间复杂度
所需占用的空间代价
和时间复杂度类似，最坏情况下用O(f(n))表示
- 是为解决问题所需要的辅助存储空间
- 只有完成同一功能的几个算法之间才具有可比性
- 忽略零星变量的存储空间
- 没有时间复杂度那么重要
¶ 常见复杂度排序
¶ 作业
¶ 1
分析递归函数的时间复杂度。简要说明分析过程。
int factorial(int n)
{
if(n<=0)return 1;
return n*factorial(n-1);
}
设时间复杂度为T(n)，则T(n)=O(1)+T(n-1)，其中O(1)对应的是if判断和n乘以factorial(n-1)的操作步骤，factorial(n-1)的时间复杂度为T(n-1)，所以T(n)=O(1)+T(n-1)=2*O(1)+T(n-2)=……=n*O(1)+T(0)=O(n)
解题方法：循环的时间复杂度等于该循环体的复杂度乘以循环的次数
¶ 2
设n是描述问题规模的非负整数，下列程序段的时间复杂度是多少？简要说明分析过程。
x=0;
while(n>=(x+1)*(x+1))
x++;
设时间复杂度为T(n)，1行的时间复杂度为O(1)，2-3行为while循环，当(x+1)*(x+1)大于n时，结束循环，其时间复杂度为,所以T(n)=O(1)+=
解题思路：同上
¶ 3
设n是描述问题规模的非负整数，下列程序段的时间复杂度是多少？简要说明分析过程。
count=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)count++;
设时间复杂度为T(n)，1行的时间复杂度为O(1)，2行为外层for循环，时间复杂度为，3行为内循环，时间复杂度为O(n)，所以T(n)= O(1)+ * O(n)=
解题思路：同上