一.算法相关概念
1.基本概念
算法(algorithm)是一个（由人或机器进行）关于某种运算规则的集合。是对特定问题求解步骤的一种描述，是指令的有限序列。
确定性：清晰，无歧义
有限性：指令执行次数、时间
特点：
- 执行时，不能包含任何主观的决定；
- 不能有类似直觉/创造力等因素。
具有下列5个特性：
- 有穷性：算法有限步结束，指令有限时间完成
- 确定性：每条指令都是明确的、无二义的
- 可行性：每条指令都能够被执行
- 输入：有0个或多个输入量
- 输出：有1个或多个输出量
2.算法的衡量尺度
最初，用所需计算时间来衡量算法的好坏,但是，不同的机器相互之间无法比较。所以需要独立于具体计算机的客观衡量标准。如：问题的规模，基本运算，算法的计算量函数。也可以通过时间复杂度(基本运算执行次数)和空间复杂度(需要的存储空间大小)。
1.问题的规模
一个或多个整数，作为输入数据量的测度
数组的长度(数据项的个数)
- 矩阵的最大维数(阶数)
2.输入规模通常用n来表示
- 也可有两个以上的参数，如图中的顶点数和边数 (图论中的问题)
3.基本运算
- 解决给定问题时占支配地位的运算。
- 在一个表中寻找数据元素x
- 两个实矩阵的乘法
- 将一个数组进行排序
通常情况下，讨论一个算法的优劣时，我们只讨论基本运算的执行次数。因为他是占支配地位的，而其他的运算可以忽略不计。
4.算法的计算量函数
用输入规模的某个函数来表示算法的基本运算量，该函数称为算法的时间复杂性(度)，一般用T(n)或T(n,m)等表示。如：T(n) = 5n, T(n) = 3n*logn, T(n) = 4n3, T(n) = 2n, T(n,m) = 2(n+m).
最坏情况时间复杂性
规模为n的所有输入中，基本运算执行次数最多的时间复杂性。
如：在一个顺序表中寻找数据元素x。顺序查找：最坏情况为O(n); 二分查找：最坏情况为O(logn)。
平均情况时间复杂性
规模为n的所有输入的算法时间复杂度的平均值(一般均假设每种输入情况以等概率出现).
如：在一个顺序表中寻找数据元素x。顺序查找：评价情况仍为O(n); 二分查找：平均情况仍为O(logn)。