算法导论学习笔记一

 

算法简介：

      算法分析是关于计算机性能和资源利用的理论研究。在程序设计方面，个人认为比性能更重要的有正确性，简洁，可维护性，成本（时间成本，资金成本等），健壮性，特性，功能性，安全性，用户友好性等。

但关心性能主要因为：

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-1
			int 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++];
			else
				data[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个数字以下，可能插入排序快于归并排序

 

如果有不正确的地方，欢迎大家补充，互相学习。