数据结构算法与算法分析
数据结构——算法与算法分析
1.算法的定义
严谨概念： 算法是解决待定问题求解步骤的描述，在计算机中表示为指令的有限序列，并且每条指令表示一个或多个操作
简单来说就是解决问题的方法和步骤，先干什么，后干什么
2.算法的描述
自然语言：中文，英文
流程图：传统流程图，NS流程图
伪代码，类语言
程序代码
3.算法的特性
- 输入：零个或多个输入
- 输出：至少一个输出
- 有穷性：算法在执行有限步骤后会自动结束，而不会无限循环，并且每步在可接受的时间内完成
- 确定性：算法的每一步都具有明确的含义，不会出现二义性
- 可行性：算法的每一步必须可行，都能通过执行有限次数完成
4.算法设计的要求
正确性 ：算法至少具有输入，输出，加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案
意思就是你写一个算法，至少得正确，而正确有以下几个层次
1.算法没语法错误
2.算法对于 合法和非法 输入数据能够产生满足要求的输出结果
3.算法对于精心选择的，甚至故意刁难的 测试数据 都有满足要求的输出结果
4.算法对于一切输入数据都有满足要求的结果
算法大部分情况下只能靠数学方法证明其正确性，而证明一个复杂算法在所有层次上完全正确的代价十分高昂，所以一般把 层次3 当作正确性判断的标准
可读性 ：便于阅读，理解，交流
健壮性 ：当有不合法的输入数据时，算法也能有相关的处理，而不是输出莫名其妙的结果
高效性 ：尽量满足时间效率高和存储量低
5.算法的效率及其度量方法
算法主要从时间和空间两个方面来度量效率，并且时间和空间效率在某种情况下有一定矛盾，所以我们需要综合平衡这两个方面来评估算法
5.1时间效率
就是看一个程序在计算机上执行所消耗的时间
有两种度量方法
事后统计方法
直接写出程序然后实验，这个方法缺陷较大不予考虑
事前分析估算
在写程序前用统计方法来对算法进行估算，经研究发现，一个程序所消耗的时间多少主要取决于
1.算法的策略，方法（算法本身的好坏）
2.编译产生的代码质量（软件）
3.问题输入的规模（我们主要研究的原因）
4.机器执行指令的速度（硬件
算法运行时间=一个简单操作所需时间（基本单位）*简单操作次数（数量）
我们引入一个叫算法的 时间复杂度 的概念来衡量算法的运行时间
算法的时间复杂度
是一个关于问题输入规模与运行时间的函数（一般是最坏时间复杂度），通常采用大O记法
大O记法下的时间复杂度推导十分简单，只需去其常数，取最高次项
常见的时间复杂度有
1.常数阶O(1),且不管常数具体是几，全部记作O(1)
2.线性阶O(n)
3.对数阶O(log2n)
4.平方阶 O(n^2)
如何计算时间复杂度
就是分析循环结构的运行情况，从代码中得到一个函数，可以用级数求和的方法求其复杂度
5.2空间效率
