Alexunder Hacking Blog Technology Notes

《算法导论》研习笔记 1

2012-07-06

内容简介

  • 算法分析基础.
  • 递归算法
  • 概率分析与随机化算法

算法分析基础

为了精确衡量一段程序在计算设备中的运行性能,前人们发明了一种数学方法,即时间复杂度于空间复杂度。通常,如果一段程序或者一个算法有被衡量的价值,她必须有循环元素。因为非循环的程序段或者算法的运行时间是完全可以预料的,通常我们称作”常量时间”。一旦有了循环元素,我们分析性能的时候就有了一个神秘的变量:n,也就是问题的规模,再通俗点说就是循环的次数。

例如,《算法导论》中第二章对插入排序的分析里,我们先粗略的得到了一个变量为n的函数,所以我们对算法的分析,从某种意义上来说是对这个函数 f(n) 的分析:即当n逐渐增大,f(n) 的增长趋势。为了方便分析 f(n) 的增长趋势,先人们发明了几种基于 f(n) 的函数集合,也叫Asymptotic notation,即渐近表达式,常用的有三种:O标记,\(\Theta\)标记,以及\(\Omega\)标记,我们一一来看:

  1. O标记是我们最常见的标记,简称Big-O-notation,他定义如下:

    \(O[g(n)] = \{f(n)\): 存在正整数c和n0使得\(0 \leq f(n) \leq cg(n)\)对于所有的\(n \geq n0 \)都成立}.

    从定义中可看出,O标记定义了f(n)的上界,也就是说算法真正的时间复杂度函数永远不会超过O[g(n)],这也是O标记如此常用的原因,因为我们大多是在分析算法在最坏情况下的性能。

  2. \(\Omega[g(n)] = \{f(n)\):存在正整数c和n0使得\(0 \leq cg(n) \leq f(n)\)对于所有的\(n \geq n0 \)都成立}.

    这个很明显是定义了性能函数的下界,通俗的说就是最好,最理想的状况。

  3. \(\Theta[g(n)] = \{f(n)\):存在正整数c1,c2和n0使得\(c1g(n) \leq f(n) \leq c2g(n)\)对于所有的\(n \geq n0 \)都成立}.

递归算法

说到递归算法,很多人不陌生,都知道是一个函数在他自己里面调用自己。这样会发生一些比较有趣的数学现象。在这里,我们不用去纠结如何设计递归,我们只是去分析递归算法,《算法导论》中提到一个公式:

公式中的字母各有意义:

  1. b的意义是将问题的规模(n)分解为规模是 n/b 的子问题,但怎么处理规模是 n/b 的子问题?我们可以在一次调用里只处理一次子问题,每一次都将子问题的规模减少到之前的 1/b,直到n等于1,递归调用结束。

  2. 我们亦可以在一次调用中处理多次子问题,这个处理的次数即是参数a的意义。举个例子,对于a等于1的情况。二分查找就是典型的例子:

int bin_search(int a[],int start,int end,int key)
{
	if(start < end) return -1;     
      
	int middle = (start + end)/2;     
	
	if(a[middle]==key)     
		return middle;     
				    
	if(a[middle] > key)     
		return bin_search(a, start, middle-1,key);     
	else     
		return bin_search(a, middle+1, end, key);     
}    

他的性能公式应为:\(T(n) = T(\frac{n}{2}) + \Theta(1)\)

接下来我们看看怎么解决递归式,《算法导论》里提供了三种方法来解决:

  1. 置换法。
  2. 递归树法。
  3. 主方法。

我们一般都使用主方法,因为主方法可以套用一定的范式。而前两种方法一般是结合使用,因为用递归树方法可以得到一个猜想,然后用置换法去验证猜想是否正确。具体细节就不在这里介绍了,相关的习题有很多。

关于主方法,还是先回到那个递归通用公式:

\[ T(n) = aT(\frac{n}{b}) + f(n) ,a\geq 1 , b>1 \]

n/b不一定是整数,所以n/b可以是\(\lceil \frac{n}{b} \rceil \)或者\(\lfloor \frac{n}{b} \rfloor\)。我们将用\(f(n)\)\(n^{\log_b a}\)比较的结果来推测T(n)。

  1. \(f(n) = O(n^{\log_b a - \varepsilon}), \varepsilon > 0\)可得\(T(n) = \Theta(n^{\log_b a})\).
  2. \(f(n) = \Theta(n^{log_b a})\), 则\(T(n) = \Theta(n^{log_b a}\lg n)\).
  3. \(f(n) = \Omega(n^{\log_b a + \varepsilon}), \varepsilon > 0\),并且如果\(a f(\frac{n}{b}) \leq cf(n)\),且\(c < 1\),以及n可以是足够大,则\(T(n) = \Theta(f(n))\).

当然这三种情况没有覆盖所有的可能,即类似下图这个样子:

case graph

Case1和Case2以及Case2和Case3之间都有缝隙。我们先来看看第一个缝隙,在Case1的情況下,

\(f(n) = O(n^{\log_b a - \varepsilon})\)

从前面O-notation的定义推得:

\(f(n) \leq Kn^{log_b a}\)

又因为Case2是:\(f(n) = \Theta(n^{log_b a})\),可以得到不等式:

\(K_1 n^{log_b a} \leq f(n) \leq K_2 n^{log_b a}\)

由此可知 \(f(n) = O(n^{\log_b a - \varepsilon})\) 表示\(f(n)\)必須乘以\(n^{\varepsilon}\)才能和Case2的\(n^{log_b a}\)相提并论,其他类似但是不属于以上集合的情况均落在缝隙中,使主方法失效。比如:

\(f(n) = O(\frac{n^{log_b a}}{c})\)

当然,Case2与Case3之间也有类似的指数级别的相乘量,不仅如此,Case3还有一些不等式上的限制,如果不满足这些条件,亦会落入缝隙中。处在缝隙中,主方法无能为力。其实,这三种情况已能覆盖绝大部分递归求解的情况,所以我们不用在缝隙中纠结了。

概率分析与随机化算法

随机变量指示器(Indicator random variables)

如果有一类算法,他的输入数据是不确定的,随机的。我们若要分析他的时间性能,必须借助概率工具来处理随机变量,叫做随机变量指示器(Indicator random variables)。他提供一种方法,可以方便的在随机变量的期望与概率之间转换。假设我有一个样本空间S,事件A,我们定义一个Indicator random variables:

\[ I\{A\} = \cases{1, & for if A happens \cr 0, & if A dones not happen.} \]

CLRS中5.2节中的引理5.1中证明了随机变量指示器表示的随机事件A的期望与他的概率是相等的关系:

\[ E(X_A) = P(A) \]

随机化算法

隨機化算法是用來產生某種隨機出現的數據。隨機數據一般都服從某一種概率分佈,比如應用廣泛的正態分佈,而CLRS中這一章里的隨機化算法里生成的都是均勻分佈。例如,輸入n個不同的數據,要求其順序是隨機的,而且要求產生任何一種順序的概率相同。應用組合數學中排列的概念,n個不同的數,一共有n!種排列,所以產生一種排列的概率為 1/n!,這就是均勻分佈。

Latex show

\[ e^x = \sum_{n=0}^\infty \frac{x^n}{n!} = \lim_{n\rightarrow\infty} (1+x/n)^n \]

\[ P(E) = {n \choose k} p^k (1-p)^{ n-k} \]

feedsky
抓虾
google reader
bloglines
鲜果
哪吒
--> Fork me on GitHub