算法导论学习笔记一
?
算法简介：
? ? ? 算法分析是关于计算机性能和资源利用的理论研究。在程序设计方面，个人认为比性能更重要的有正确性，简洁，可维护性，成本（时间成本，资金成本等），健壮性，特性，功能性，安全性，用户友好性等。
但关心性能主要因为：
1.性能直接决定着软件开发的可行还是不可行，例如，对于实时的需求，程序不够快，表示着不可行，如果占用太多内存，也只能说不可行，所以算法总是处于解决问题的最前沿。
2.算法是一种描述程序行为的语言，计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法=?程序》，可见算法在计算机科学界与计算机应用界的地位。
那么算法在程序设计中扮演的角色，打个比方，它所扮演的角色就如同经济中的货币一般，在这基础上，你才能买你的生活所需用品比如水，食物。同理，有了算法，你才能在性能良好上基础上，构建软件的扩展性，用户友好性等等。
?
算法运行多长时间往往取决于：
1.输入值本身决定（比如已经排序好的，运行比较快）
2.输入值数量的多少
3.计算机运行速度
?
但是，接下来讨论的，在同等的输入值，输入数量和计算机运行速度上，一个算法的评价主要从时间复杂度和空间复杂度来考虑。
?
时间复杂度
算法的时间复杂度是指执行算法所需要的时间。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做
T(n)=Ο(f(n))
因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
空间复杂度
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
?
?
以下举例说明不同算法间的时间复杂度影响效率，分别用直接插入法和归并排序给大家做个试验，代码如下：
?
import java.util.Random;/* * Author by Deepin * 2012-1-7 */public class Algorithm {/* * 插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 * 时间复杂度：T(n)=O(n^2) * 在规模较小的情况下，都使用插入排序法来进行排序 */public static void insertSort(int[] sort) {int j; // 定为比较得元素for (int i = 1; i < sort.length; i++) { // 扫描次数为sort.length-1int temp; // temp用来暂存数据temp = sort[i];j = i - 1;while (j >= 0 && temp < sort[j]) { // 如果第二个元素小于第一个元素sort[j + 1] = sort[j]; // 把所有的元素往后推一个位置sort[j] = temp; // 最小的元素放到第一个位置j--;}}}/* * 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件 * T(n)=2T(n/2)+O(n), if(n>1) */public static void mergeSort(int[] data) {int[] temp = new int[data.length];merge(data, temp, 0, data.length - 1);}private static void merge(int[] data, int[] temp, int l, int r) {int mid = (l + r) / 2;if (l == r)return;merge(data, temp, l, mid);merge(data, temp, mid + 1, r);for (int i = l; i <= r; i++) {temp[i] = data[i];}int i1 = l;int i2 = mid + 1;for (int cur = l; cur <= r; cur++) {if (i1 == mid + 1)data[cur] = temp[i2++];else if (i2 > r)data[cur] = temp[i1++];else if (temp[i1] < temp[i2])data[cur] = temp[i1++];elsedata[cur] = temp[i2++];}}public static void main(String[] args) {Random random = new Random();for (int sortSize = 100; sortSize < 100001; sortSize *= 10) {int[] sort = new int[sortSize];for (int i = 0; i < sortSize; i++) {sort[i] = random.nextInt(100001);}long startTime = System.currentTimeMillis();Algorithm.insertSort(sort);long endTime = System.currentTimeMillis();System.out.println("插入算法：sortSize为" + sortSize + "排序总共运行了："+ (endTime - startTime) + "毫秒");startTime = System.currentTimeMillis();Algorithm.mergeSort(sort);endTime = System.currentTimeMillis();System.out.println("排序算法：sortSize为" + sortSize + "排序总共运行了："+ (endTime - startTime) + "毫秒");System.out.println("----------------------------------------");}}}?运行结果：
?
插入算法：sortSize为100排序总共运行了：0毫秒排序算法：sortSize为100排序总共运行了：0毫秒----------------------------------------插入算法：sortSize为1000排序总共运行了：3毫秒排序算法：sortSize为1000排序总共运行了：0毫秒----------------------------------------插入算法：sortSize为10000排序总共运行了：53毫秒排序算法：sortSize为10000排序总共运行了：1毫秒----------------------------------------插入算法：sortSize为100000排序总共运行了：5632毫秒排序算法：sortSize为100000排序总共运行了：14毫秒----------------------------------------
?
得出结论：归并排序在一个充分大的输入规模下将优于插入排序，因为T(n)=2T(n/2)+O(n)<T(n)=O(n^2)
但在小输入规模下，比如30个数字以下，可能插入排序快于归并排序
?
如果有不正确的地方，欢迎大家补充，互相学习。