摘要：最近在学习数据结构，使用的教材是《大话数据结构》，在这里分享自己所做的笔记，作为巩固所学和交流分享之用！
1.引子：计算数列和
现在来设计这样一个程序，计算1+2+3+…+100
C++语言实现：
int i=1,sum=0,n=100;
for(;i<=n;i++)
sum+=i;
cout<<sum;一种优化的方式：sum=(1+100)+(2+99)+…+(50+51)=101*50
int sum=0,n=100;
sum=(1+n)*n/2;
cout<<sum;2.算法
- 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作。
- 算法的特性
- 输入输出 ：算法有0个或者多个输入，至少有一个输出。
- 有穷性 ：算法在执行有限步骤之后，自动结束而不会出现无限循环，并且每一个步骤在有限的时间内完成。
- 确定性 ：算法的每一步都具有确定的含义，不会出现二义性。
- 可行性 ：算法的每一步都必须是可行的。
- 算法设计的要求
- 正确性 ：指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
- 可读性 ：算法设计的另一目的是为了便于阅读、理解和交流。
- 健壮性 ：当输入不合理时，算法也应该能做出相关处理，而不是产生异常或者莫名其妙的结果。
- 时间效率高和存储量低
- 算法效率的度量方法
- 事后统计方法：主要通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
- 事前分析估算法：在计算机程序编制前，依据统计方法对算法进行估算。
3.算法的时间复杂度
时间复杂度定义：在进行算法分析时，语句总的执行次数
T{n} 是关于问题规模n的函数，进而分析T{n}随n的变化情况并确定T{n}的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T{n}=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。称这样的表示方法为：大O记法。推导大O阶方法：
- 用常数1取代运行时间中的所有加项常数
- 保留修改后的最高阶项
- 若最高阶项系数不为1，则修改为1
常见的时间复杂度：
常数阶：O(1)
线性阶：O(n)
平方阶：O(
n2 )对数阶：O(logn)
nlogn阶：O(nlogn)
立方阶：O(
n3 )指数阶：O(
2n )基时间复杂度基本关系：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)