欢迎关注我的微信公众号【万能的小江江】
抽象数据类型ADT(Abstract Data Type)：指一个数学模型及定义在该模型上的一组操作
结构
逻辑结构
- 集合结构
- 线性结构
- 树形结构
- 图形结构
物理结构
- 顺序存储结构
- 链接存储结构
tips：如果你中途放弃了，之前所有的努力和付出都会变得没有价值
算法
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
数据结构与算法的关系
在学习数据结构的过程中，算法是为了帮助更好地理解数据结构
两种算法的比较
现在我们要写出计算从1加到100结果的程序，正常可能会这样写：
int i,sum = 0,n = 100;
for(i = 1 ;i <= n;i++)
{
sum = sum + 1;
}
printf("%d",sum); 用高斯的方法：
int i,sum = 0,n = 100;//数据比较大的话需要更改整型变量为长整型，否则会溢出
sum=(1 + n) * n/2;
print("%d",sum);算法的定义
算法（Alogorithm）在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
这里提到的指令，能被人或机器等计算装置执行，可以是计算机中的指令，也可以是我们平时的语言和文字
为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，，每一个操作都完成特定的功能，就是算法
算法的特性
算法的五个基本特征：输入、输出、有穷性、可行性
输入、输出
算法具有零个或多个输入，但是一定需要输出，输出的形式可以是打印输出，也可以是返回一个或多个值
有穷性
指算法在执行完有限的步骤后，自动结束，不会出现无限循环，且每个步骤在可接受的时间内完成
确定性
算法的每一个步骤都有确定的含义，不会出现二义性，每个步骤被精确定义而无歧义
可行性
算法的每一步必须都是可行的，每一步都能通过执行有限次数完成
算法设计的要求
正确性
算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案
正确性层次
- 算法程序没有语法错误
- 算法程序对于合法的输入数据能够产生满足要求的输出结果
- 算法程序对于非法的输入数据能够得到满足规格说明的结果（正常情况下，以此为正确性标准）
- 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果
可读性
写代码的目的，一方面是为了让计算机执行，还有就是为了便于他人阅读，让人理解和交流，也为自己之后阅读代码提供便利
可读性是算法和实现它的代码好坏很重要的标志
健壮性
当输入数据不合法时，算法也能做出相关的处理，而不是产生异常或莫名其妙的结果
时间效率高和存储量低
尽量用最短的时间，最少的资源，办最大的事
算法效率的度量方法
事后统计方法
通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序运行时间进行比较，从而确定算法效率的高低
缺陷
- 必须依照算法事先编好程序，需要花费大量时间和精力
- 时间的比较容易受到计算机硬件和软件等环境因素的影响，不同的电脑不一样
- 算法的测试数据设计困难，程序的运行时间与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到什么体现
事前分析估算法
在计算机程序编制前，依据统计方法对算法进行估算
正常情况下影响运行消耗时间的因素
算法的策略、方法
编译产生的代码质量（需要软件的支持）
问题的输入规模
机器执行指令的速度（看硬件性能）
所以正常情况下，主要是取决于算法的好坏和问题的输入规模
举例
第一种算法：
int i,sum = 0,n = 100;//执行1次
for(i = 1;i < n;i++)//执行n+1次
{
sum = sum + 1;//执行n次
}
printf("%d",sum);//执行1次 总计执行2n+3次
第二种算法：
int i,sum = 0,n = 100;//执行1次
sum=(1 + n) * n/2;//执行1次
print("%d",sum);//执行1次 总计执行3次
延展：
int i,j,x = 0,sum = 0,n = 100;//执行1次
for(i = 1;i <= n;i++)
{
for(j = 1;j <= n;j++)
{
x++; //执行n x n次
sum = sum + x;
}
}
printf("%d",sum); //执行1次 总计执行n²+2次
由此可看出，虽然三种算法结果一样，但是耗费的时间差很多，在分析程序运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤
函数的渐近增长
给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有n>N,f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于g(n)
判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，应该更关注主项的阶次
某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差于另一算法
算法的时间复杂度
算法时间复杂度定义
时间复杂度就是一个程序需要执行的次数多少？
推到大O阶方法
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大O阶
常数阶
int i,sum = 0,n = 100;//执行1次
sum=(1 + n) * n/2;//执行1次
print("%d",sum);//执行1次 为什么时间复杂度是O(3)，不是O(1)?
这个算法的运行此时函数f(n)=3，根据我推导大O阶的方法，第一步是把常数项3改为1。之后在保留最高次项的时候发现，它没有最高次项，所以这个算法的时间复杂度是O(1)
int i,sum = 0,n = 100;//执行1次
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;//共执行10次
print("%d",sum);//执行1次 如这个代码，无关n是多少，两段代码就是3次和12次执行次数的差异。执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶
不管常数是多少，我们都记作O(1)，不能是其他数字
对于分支结构，无论是真或假，执行的次数都是恒定的，不会随着n的变大而发生变化， 所以单纯的分支结构（不包含在循环结构中），时间复杂度也是O(1)
线性阶
要确定某个算法的阶次，我们常常需要确定某个特定语句或者某个语句集运行的次数。因此，如果要分析算法的复杂度，关键就是要分析循环结构的运行情况
int i;
for(i = 0; i < n;i++)
{
//时间复杂度为O(1)的程序步骤序列
}
//时间复杂度为O(n)对数阶
int count = 1;
while(count < n)
{
count = count * 2;
//时间复杂度为O(1)的程序步骤序列
} 每次count乘以2之后，就距离n更近了一分。有多少个2相乘后大于n，就会退出循环。由2的x次方=n，得到x=log2n，所以这个循环的时间复杂度为O(logn)
平方阶
int i,j;
for(i = 0;i < n;i++)
{
for(j = 0;j < n;j++)
{
//时间复杂度为O(1)的程序步骤序列
}
} 对外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次，所以这段代码的时间复杂度为O(n²)
如果外循环次数改为m，时间复杂度就变为O(m*n)
int i,j;
for(i = 0;i < m;i++)
{
for(j = 0;j < n;j++)
{
//时间复杂度为O(1)的程序步骤序列
}
} 循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数
int i,j;
for(i = 0;i < n;i++)
{
for(j = i;j < n;j++)//注意是j=i
{
//时间复杂度为O(1)的程序步骤序列
}
} i=0，内循环执行了n次；i=n-1，内循环执行了n-1次…当i=n-1时，执行了1次，内循环总的执行次数为：
n+(n-1)+(n-2)+...+1=n(n+1)/2=n²/2+n/2
步骤1：没有加法常数，不予考虑
步骤2：只保留最高阶项，只保留n²/2
步骤3：去除这个项相乘的常数，所以时间复杂度是O(n²)
例子1
int i,j;
for(i = 0;i < n;i++)
{
function(i);
}
void function(int count)
{
printf(count);
} function函数的时间复杂度是O(1)，所以整体的时间复杂度是O(n)
如果function是这样：
void function(int count)
{
int j;
for(j = count;j < n;j++)
{
//时间复杂度为O(1)的程序步骤程序
}
} 这和前面的例子一样，只不过是把嵌套内循环放到了函数中，所以最终的时间复杂度为O(n²)
例子2
n++;//执行次数为1
function(n);//执行次数为n
int i,j;
for(i = 0;i < n;i++)//执行次数为n²
{
function(i);
}
for(i = 0;i < n;i++)//执行次数为n(n+1)/2
{
for(j = i;j < n;j++)
{
//时间复杂度为O(1)的程序步骤程序
}
}
执行次数总计：
由前面推导大O阶的方法，这段代码的时间复杂度也是O(n²)
常见的时间复杂度
所耗费的时间，从小到大
过大的n会使结果变得不现实，一般不讨论
最坏情况与平均情况
我们查找一个有n个随机数字数组中的某一个数字，最好的情况就是第一个数字就是，算法的时间复杂度为O(1)，最坏的情况是最后一个数字是，算法的时间复杂度为O(n)
从概率上说，数字在每一个位置上的概率是相同的，所以平均查找时间为n/2次后发现这个目标元素
平均运行时间是所有情况中最有意义的，它是期望的运行时间，但是在现实中，平均运行时间很难通过分析得到，需要通过运行一定数量的实验数据后估算出来
对于算法的分析，一种方法是计算所有情况的平均值，这种方法称为平均时间复杂度；另外一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般如果不特别说明，都是指最坏时间复杂度
算法空间复杂度
写代码时，完全可以用空间来换取时间
比如，我们写一个算法来判断是否是闰年。通过算法得出结果，则每次运行都需要运算。如果我们把所有年份都列出来，给闰年做标记，那这样虽然耗费了空间，但是节省了时间
算法的空间复杂度通过计算算法所需的存储空间来实现，算法空间复杂度的计算公式：
其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数
输入数据所占空间只取决于问题本身，与算法无关。若算法执行时候所需要的辅助空间相对于输入数据量而言是个常数，则称算法为原地工作，空间复杂度为O(1)
正常情况下说”复杂度“都是指的时间复杂度
总结
算法的定义：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
算法的特性：输入、输出、有穷性、确定性、可行性
算法的设计的要求：正确性、可读性、健壮性、高效率和低存储量需求
算法特性与算法的设计容易弄混，需要对比记忆
算法的度量方法：事后统计法（不科学、不准确）、事前分析估算法
在讲解事前分析估算法之前，要先了解函数渐近增长的定义
函数的渐近增长：
之后，给出了算法时间复杂度的定义和推导大O阶的步骤：
推导大O阶：
用常数1取代运行时间中所有的加法常数
修改后的运行次数函数，只保留最高阶项
如果最高项存在且不是1，则去除它前面的常数
这样得到的结果就是大O阶
其实推导大O阶很容易，如何得到运行次数的表达式需要数学功底
常见的时间复杂度所耗费时间大小排列：
最后，了解了关于算法最坏情况和平均情况的概念，以及空间复杂度的概念
