算法（1）前言

文章目录

1. 算法（1）前言

研一下开始上“算法设计与分析”的课程，正好最近自己刚开博客，记一下老师上课的内容，相当于笔记，期末复习的时候也有据可查。博文的内容基本都是上课提到的内容，所以会有点意识流，但是也会写一些详细的专题介绍。

算法设计

基本方法

列表、树、图的算法

分治

主定理

递归

高级话题

动态规划

贪心算法

线性规划

近似算法

随机算法

课程中主要涉及了贪心算法、线性规划和近似算法。

算法分析

算法分析就是用来评判算法的效率。

大O表示法

高级评判方法

概率分析（Probability Analysis）

摊销分析（Amortized Analysis）

竞争分析（Competition Analysis）

概率分析就是指实现了一个算法，但是复杂度很高的情况出现的概率很低，比如随机给出一个数是质数。

摊销分析就是指某些算法在算第一次的时候花费的时间会特别长，但是在之后的计算过程中会越来越好，比如不相交子集（disjoint set）。

高级评判分析这一块老师只是略微的提了一下，记得不是特别清楚，可能会在以后的课程中会详细展开。

标准算法

排序

搜索和哈希

强连通部件

在图中寻找最短路径

最小生成树

找二分图（bipartite graph）的匹配

网络中的最大流

排序

那么我们接下来，来讲讲排序。常见的排序有插入排序、冒泡排序、堆排序、快排序和归并排序（MergeSort）。主要来讲讲MergeSort。

下面是它的伪代码：

MergeSort(a[1...n])
Input: an array of numbers a[1...n];
If n > 1 then
	Merge( MergeSort(a[1...n/2]), MergeSort(a[n/2]...n) );
Else
	return a;
End
Merge(x[1...k], y[1...l])
if k==0 then return y[1...l];
if l==0 then return x[1...k];
temp[1,k+l];
for i in [1:min(k,l)]
	if(x[i] <= y[i])
		temp[i] = x[i];
	else
		temp[i] = y[i];
	end
end
temp[i..k+l] = rest(x,y);
return temp[1,k+l];
END

归并排序是先大快朵颐通过递归二分，将一个大小为n的列表分成n份，接着再1个和1个比较，得到长度为2的有序列表，再2个和2个比较，得到长度为4的有序列表······最终得到长度为n的有序列表。

那么这里还有个问题？怎么将上面的递归算法改成迭代的版本呢？老师的版本挺不错的，所以就和大家分享一下。

Iterative-MergeSort(a[1...n])
Input: An array of numbers a[1...n];
	Q = empty queue;
	for i = 1 to n:
		Inject(Q,a[i]);
	while(size of Q > 1)
		Inject(Q,Merge(Q.pop().Q.pop()));
	End
	return Q.top();

那么这个算法如何计算复杂度呢？

假设对长度为n的列表进行归并排序的时间为T(n)，那么在MergeSort中做了2次时间为T(n/2)的MergeSort，Merge的操作需要花费O(n)，所以算法花费的时间T(n) = 2T(n/2) + O(n)。那么我们现在就要化简这个多项式，这里我直接使用主定理得到,

T(n) = O(nlogn)

那么基于比较的排序的算法复杂度能否低至线性的呢？

答案是不能的，那么怎么来证明呢？

任何基于比较的排序算法都可以描述成决策树（decision tree），两两比较的二叉树，如下图：

那么这样的二叉树的就会有n!个叶子，每次都是二分的来查找，那么找到排序的结果所花费的时间就是O(log(n!))

O(log(n!)) = Θ(n·log(n)) （它的证明）

所以基于比较的排序算法复杂度不能低至线性。

最短路径和编辑距离

课上还提到了最短路径（通过广度优先搜索引入）和编辑距离的问题，我觉得这两个问题都可以单独来分析一下，所以今天就写这么多了。

算法（1） 前言

算法设计

算法分析

标准算法

排序

最短路径和编辑距离

算法（1）前言