程序 = 数据结构 + 算法
口诀： 常对幂指阶 （从小到大）
数据结构是要处理的信息，算法是处理信息的步骤
-
算法的定义：
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操 作。 -
算法具有五个基本特性：
输入，输出，有穷性，确定性和可行性
输入输出：
算法具有零个或多个输入，至少有一个或多个输出。
有穷性：
指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
算法是有穷的，程序可以是无穷的。
确定性：
算法的每一步骤都具有确定的含义，不会出现二义性。
可行性：
算法的每一步骤都必须是可行的，也就是说每一步都能够通过执行有限次数来完成。
3.算法设计的五个要求：
正确性，可读性，健壮性，时间效率高，存储量低
正确性：
算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
可读性：
算法设计的另一目的是为了便于阅读、理解与交流。
健壮性：
当输入的数据不合法时，算法也能做出相应的处理，而不是产生异常或者莫名其妙的结果。
时间效率高、存储量低：
时间效率指的是算法的执行时间，存储量低指的是算法程序运行所占据的内存或外部硬盘存储空间低。
4 .算法效率的两种度量方法:
事后统计方法，事前统计方法
事后统计方法：
简单来说，就是先根据不同算法设计好对应的代码程序，用计算机运行一遍，从而确定算法效率的高低。
事前统计方法：
在计算机程序编制前，依据统计方法对算法进行评估。
程序在计算机上运行的时间的多少取决于如下四个因素：
（1）算法采用的策略、方法
（取决于算法的好坏）
（2）编译产生的代码质量
（取决于软件）
（3）问题的输入规模
（取决于问题的复杂程度以及输入量的多少）
（4）机器执行指令的速度
（取决于硬件性能）
5.描述算法执行次数的函数（事前估算方法的理论依据）
设输入规模为n，某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差与另一个算法。并且，判断一个算法的效率时，函数的常数和其他次要项常常可以忽略，应该关注函数的最高阶项的阶数。
6.算法的时间复杂度与空间复杂度基本概念
时间复杂度：
表示
代码执行时间
随着
数据规模
增长的变化趋势，也叫
渐进时间复杂度
。
空间复杂度：
全称
渐进空间复杂度
，表示算法的
存储空间
和
数据规模
之间的增长关系。
大O复杂度表示法 ：
Tn = O (f(n))
，
T(n)表示代码的
执行时间
，n表示
数据规模
的大小，f(n)表示
每行代码执行的次数总和
，
用来分析
算法的时间复杂度
。
大O复杂度表示法操作步骤：
（1）用常数1取代运行时间中的所有加法常数
（2）在修改后的运行次数函数中，只保留最高阶项
（3）如果最高阶项存在且不是1，则去除与这个项相乘的常数
（4）完成上述步骤后，检查一遍，如无误，得到的结果就是用大O复杂度表示的该算法的时间复杂度。
7.常见的时间复杂度
常见的时间复杂度
常用的时间复杂度所耗费的时间从小到大依次是:
8.算法的最坏、最好与平均时间复杂度
最坏时间复杂度：
最坏情况下的算法的时间复杂度
最好时间复杂度
：最好情况下算法的时间复杂度
平均时间复杂度：
所有输入示例等概率
出现的情况下，算法的期望运行时间算法的性能问题只有在n很大时才会暴露出来。
9.空间复杂度
【1】如何计算
普通程序处理步骤 （1）找到所占空间大小与问题规模相关的变量
（2）分析所占空间x与问题规模 n 的关系 x = f(n)
（3）x的数量级O(x)就是算法空间复杂度S(n)
递归程序处理步骤 （1）找到递归调用的深度 x 与问题规模相关的变量
（2）x的数量级O(x)就是算法空间复杂度S(n)
注意：有的算法各层函数所需的存储空间不同，分析方法略有区别
【2】常用技巧
加法原则：O(f(n)) + O(g(n)) = O(max(f(n),g(n)))
乘法原则：O(f(n)) * O(g(n)) = O(f(n) * g(n))