算法和算法分析
- 逻辑结构—研究对象的特性及其相互之间的关系
- 存储结构—有效地组织计算机存储
- 算法–有效地实现对象之间 ”运算“关系
算法的定义
对特定问题求解方法和步骤的一种描述，他是指令的有限序列。其中每个指令表示一个或多个操作
简而言之，算法就是解决问题的方法和步骤
算法的描述
- 自然语言：英语、中文
- 流程图：传统流程图、NS流程图
- 伪代码：类语言
- 程序代码：python go
算法和程序
算法
算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法
程序
程序是某种程序设计语言对算法的具体实现
程序=数据结构+算法
数据结构通过算法实现操作
算法根据数据结构设计程序
算法的特性
一个算法必须具备以下五个重要特性
一个算法必须总是在执行有穷步之后结束，且每一步都在又穷时间内完成
算法中的每一条指令必须有确定的含义，没有二义性，在任何条件下。只有唯一的一条执行路径，及对于相同的输入只能得到相同的输出。
算法是可执行的，算法描述的操作可以通过已经实现的借本操作执行有限次来实现
一个算法有零个或多个输入
一个算法有一个或多个输出
算法设计的要求
-
正确性
正确性：算法满足问题要求，能正确解决问题
算法转化为程序后要注意：
- 程序中不含有语法错误
- 程序对于几组输入数据能偶得出满足要求的结果
- 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果
- 程序对于一切合法的输入数据都能得出满足要求的结果
通常一第三层意义上的正确性作为衡量一个算法是否合格的标准
-
可读性
可读性：
- 算法住哟啊是为了人的阅读和交流，其次才是计算机执行，因此算法应该抑郁人的理解；
- 另一方面，晦涩难读的算法易于隐藏较多错误而难以调试
健壮性：
- 指当输入非法数据时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果
- 处理出错的方法，不应是中断程序执的行，二应该是返回一个表示错误或 错误性质的执行，而应是返回一个表示错误性质的值，以便在更高的抽象层次上进行处理
高效性：
- 要求花费尽量少的时间和尽量低的存储要求
、
算法效率
对于同一个问题，可以有许多不同的算法。究竟如何来评价这些算法的优劣程度呢？
一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来批判不同算法的优劣程度。
算法效率以下两个方面来考虑
时间效率：
指的是算法所消耗的时间
空间效率：
算法执行过程中所消耗的存储空间
时间效率和空间效率有时候是矛盾的，提升效率可能要消费时间，提升时间可能要消费空间，也就是我们常说的一种像以时间换空间，以空间换时间，
算法时间效率的度量
算法时间复杂度定义
算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作T(n)=O(f(n))
基本语句
问题规模
- n越大算法的执行时间越长
- 排序：n为记录数
- 矩阵：n为矩阵的阶数
- 多项式：n为多项式的项数
- 集合：n为元素的个数
- 树：n为树的结点个数
- 图：n为图的订单或者边数
看例子
i = 1;
while(i<=n):
i = i * 2
若循环执行1次 i = 1*2
若循环执行2次 i = 2*2
若循环执行3次 i = 4*2
若循环执行4次 i = 8*2
....
若循环执行x次 i = 2^x
i<=n,所以 2^x<=n 所以 x<log2n
也可以不再区分以什么为底数 直接是log级别也就是 lgN
算法时间复杂度计算
请注意
：有的情况下，算法中基本操作执行的次数还随问题的 数据集不同而不同
顺序查找
顺序查找，在数组list1中查找值等于e的元素，返回其所在的位置。
for i in list1:
if i == e:
return i
- 最坏时间复杂度：旨在最坏的情况下，算法的时间复杂度。
- 平均时间复杂度：只在所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
- 最好时间复杂度：只在最好的情况下，算法的时间复杂度
- 一般总是考虑在最坏的情况下的时间复杂度，以保证算法的运行时间不会比他更长
对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度：
a) 加法规则
T(n)=T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))
b)乘法规则
T(n)=T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(max(f(n)*g(n)))
时间复杂度T(n)按数量及递增顺序为
复杂度低：常数阶(O(1))>对数阶(O(log2n))>线性对数阶(O(nlog2n))>平方阶(O(n2))>立方阶(O(n3))>K次方阶(O(nk))>指数阶O(2n) 复杂度高
渐进空间复杂度
空间复杂度：算法所需要存储空间的度量，
? 记作 S(n)=O(f(n))
? 其中n为问题的规模(或大小)
算法要占据的空间
- ? 算法本身要占据的空间。输入/输出，指令，常数，变量等
- 算法要使用的辅助空间
例：将一堆数组a中的n个数逆序存放在原数组中
算法一
package main
import "fmt"
func main() {
a := [...]int{1, 2, 3, 4, 5, 6, 7, 8, 89, 321, 32, 3, 1, 31, 23, 12, 312, 31, 241, 2}
fmt.Println(a)
n := 7
for i := 0; i < n/2; i++ {
t := a[i]
a[i] = a[n-i-1]
a[n-i-1] = t
}
fmt.Println(a)
}
[1 2 3 4 5 6 7 8 89 321 32 3 1 31 23 12 312 31 241 2]
[7 6 5 4 3 2 1 8 89 321 32 3 1 31 23 12 312 31 241 2]
S(n) = O(1)
原地工作 只需要t这一个变量
算法二
package main
import "fmt"
func main() {
a := [...]int{1, 2, 3, 4, 5, 6, 7, 8, 89, 321, 32, 3, 1, 31, 23, 12, 312, 31, 241, 2}
b := make([]int, len(a), len(a))
n := len(a)
fmt.Println(a)
for i := 0; i < n; i++ {
b[i] = a[n-i-1]
}
for i := 0; i < n; i++ {
a[i] = b[i]
}
fmt.Println(b)
fmt.Println(a)
}
[1 2 3 4 5 6 7 8 89 321 32 3 1 31 23 12 312 31 241 2]
[7 6 5 4 5 6 7 8 89 321 32 3 1 31 23 12 312 31 241 2]
S(n) = O(n)
需要创建一个等长切片 有n个元素就需要开辟n个辅助空间
设计好算法的过程
抽象数据类型=数据的逻辑结构+抽象运算（运算的功能描述）
数据的逻辑结构-----数据的结构存储1 … 数据的存储结构n
|