MIT算法导论一 简介

本系列文章根据MIT公开课程:算法导论,并结合《算法导论》进行整理。

Analysis of algorithm 算法分析

关于计算机程序在效率资源利用方面的理论研究

首先提出几个问题?
– 有比效率更重要的吗?
其实有很多,例如:正确性、可维护性、时间成本、健壮性、用户友好(user-friendly)等等
– 既然如此,为什么还要进行算法的效率分析呢?
一个很有意思的比方,你认为钱重要还是水和饭重要?当然是水和饭,但是钱却可以换来水和饭。在算法分析中的“效率”,就是用来支持其他东西的基础,比如用户体验、安全等等。


这里举个例子:排序问题
Input:一些列的数字集合 seq<a1, a2, a3… an>
Output:重新排序的数字集合seq<a1′, a2′, a3’… an’>,并且a1′<a2′<a3’…<an’

插入排序实现(伪代码):

insertion sort(A[1...n])
  for j <- 2 to n
    do key <- A[j]
      i <- j-1
      while i>0 and A[i]>key
        do A[i+1] <- A[i]
          i <- i-1
      A[i+1] <- key

对于每一个A[i],考虑A[1…i-1]中它的合适的插入位置k,然后将A[k…i-1]依次后移一个位置,把A[i]插入到A[k]的位置即可

归并排序实现(伪代码):

merge sort(A[1...n])
  1. if n=1 done
  2. recursively sort A[1...n/2] and A[n/2+1...n]
  3. merge 2 sorted lists

将一个表分成两部分递归排序,递归处理的两个表已经有序了后进行合并


关注运行时间,依赖于
-数据的输入情况,数据是否有序
-数据的规模
-找到运行时间上界。一般情况下,我们需要找到这个程序对于最坏的输入数据的情况下,运行时间是多长。As a guarantee to the user

几种分析运行时间的方法
Worst-case:(usually)
用T(n)来表示算法在输入规模为n时的最大运行时间
Average-case:(sometimes)
用T(n)来表示算法在所有输入规模为n的序列的运行时间的一个期望值
基于假设:输入的统计分布,一种常见的假设就是均匀分布,所有输入都以相同可能的方式出现。
Best-case:(bogus)
用一组极好的数据在一个效率极低的算法上跑,没有说服力。

那么插入排序的Worst-case时间是多少?
首先取决于运行的机器,所以当比较算法时,通常比较的是相对速度(在同一台机器上)

Big Idea——引入渐近分析
忽略那些依赖于机器的常量
关注当n趋近于无限大时,T(n)的增长

渐进符号(Asymptotic notation)
θ-notation:忽略所有的低阶项和常数因子,只分析最高阶项

3n^3^ + 2n^2^ + 4n + 1=θ(n^3^)

如果算法A的渐近时间复杂度是θ(n^3^),算法B的是θ(n^2^),那么一定存在一个足够大的n,算法B的运行时间要小于A


对于插入排序的分析
T(n)分析
T(n)=Σθ(j)=θ(n^2^)

所以插入排序够快吗?

当n比较小的时候比较快,但是当n变大时效率会很糟糕

对于归并排序的分析
T(n)分析
T(n)=2T(n/2)+θ(n)=2T(n/2)+cn=θ(nlg^n^) | constant c > 0

归并排序能够在效率上当输入规模n增大的时候渐近的超过插入排序,在最坏的情况下。实际上,当n>30以及以上的时候,归并排序的效率就比插入排序的效率要高了

文中图片来源:http://www.cnblogs.com/beautiful-code/p/4923632.html

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

14 + 15 =