算法与算法分析
一、算法
在计算机环境下研究数据结构，应该将数据的逻辑结构、数据的存储结构和数据的运算看成一个整体，只有对这三个方面都清楚了，才能真正了解这个数据结构。
其中，数据的运算或者说对数据的操作步骤就是算法，算法是解决特定问题的求解步骤的描述，在计算机中表现为指令的有限序列，每条指令表示一个或多个操作。
一个算法必须满足以下五个重要特性：
①有穷性。
②确定性。
③可行性。
④输入。
⑤输出。
二、算法优劣的衡量
算法的评价：正确性、可读性、健壮性、高效性。
三、算法效率分析
算法效率分析是为了看算法实际是否可行，并且在同一问题有多种算法时，可以进行时间和空间的性能上的比较，从而挑选更优秀的算法。
衡量算法效率的方法主要有事后统计法和事前分析估算法。由于事后统计法必须先将算法实现出来，另外对于算法的测算结果依赖于软硬件等环境因素，因此通常采用的是事前分析估算法，通过计算算法的渐近复杂度来衡量其效率，所以它仍然并非是精确统计的算法执行所需时间，而是通过估算来得到算法执行时间的信息。
一个算法的执行时间大致上等于所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行的次数乘以单次执行所需的时间。
语句的重复执行次数称为语句频度
问题规模是算法求解问题输入量的多少，一般用整数n表示
四、时间复杂度
以f(n)表示基本语句的频度之和的函数，假如一个算法的频度和为：
f(n) = 2n^3 + n + 1
当n趋近于无穷大时，n+1对于整个函数值的影响可以忽略，f(n)和n3之比为2，是一个不等于0的常数，可称f(n)和n3是同阶的，或者说它们的数量级相同。
使用大写字母"O"来表述数量级，以大写字母"T"来表示算法执行时间的增长率，则记作：
T(n) = O(f(n)) = O(n^3)
一般情况下，算法中的基本语句重复执行次数是问题规模n的某个函数f(n)，算法的时间量度记作：
T(n) = O(f(n))
它表示随着问题规模n的增大，算法执行时间的增长率和函数f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。这种使用O(f(n))来体现算法时间复杂度的记法称之为大O记法。
一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
推导大O阶示例（以f(n) = 2n^3+n+5为例）
可得出示例的时间复杂度为T(n) = O(f(n)) = O(n3)。
常见的时间复杂度
| 常见时间复杂度 | 频度函数示例 | 阶 |
|---|---|---|
| 常数阶 | 10 | O(1) |
| 线性阶 | 3n + 1 | O(n) |
| 平方阶 | 3 n^2 + 2n + 1 | O(n^2) |
| 立方阶 | 4 n^3 + 3 n^2 + 2n + 1 | O(n^3) |
| 指数阶 | 2n | O(2n) |
| 对数阶 | 2 log2 n + 12 | O(log2 n) |
| nlogn阶 | 3n log2 n + n + 1 | O(n log2 n) |
常见的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
在对某些算法进行评价时，有些算法的基本语句的执行次数不仅仅于问题规模有关，还依赖于其他的因素。例如：
在n个学生信息中查找指定学号的学生信息，并返回其位置。
最好、最坏、平均时间复杂度
五、空间复杂度
类似于时间复杂度，算法的空间复杂度指的是算法所需的存储空间的量度。记作：
S(n) = O(f(n))
一般情况下，一个程序在机器上运行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据进行操作的存储单元。
若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。
空间复杂度的研究往往不如时间复杂度那么重要，同时空间复杂度和时间复杂度往往是相互影响的，因此在说到如”算法的复杂度“这样不加限定词时，通常情况下都是指时间复杂度，后面的算法学习中更多关心的也是算法的时间复杂度。