离散数学(10) 算法

今天我们来学算法,这是一种在有限重复步骤内完成某件事情的方法。

举个例子

问: 把大象放进冰箱分几步?

  1. 打开冰箱门
  2. 把大象放进冰箱
  3. 关上冰箱门

看,有限步骤(1,2,3)能解决某个问题。这就是一个算法。那为什么叫有限重复呢?那还要看这个问题有多大了。如果我们有两只大象,上面这三个步骤就要重复两次…

  1. 打开冰箱门
  2. 把大象放进冰箱
  3. 关上冰箱门
  4. 打开冰箱门
  5. 把大象放进冰箱
  6. 关上冰箱门

这些操作每一项都是必须的。你看,打开冰箱门才能把大象放进去,把冰箱门关上大象才能被关在里面。这些操作我们称之为基本操作

关于基本操作,我们再举一个例子。下面这个算法会计算1到100的总和

n = 100 #100
sum = 0 #0
1.upto(n){|i| sum+=i} #5050

在这个迭代器里面,sum += i的操作就是这个算法必须要执行的操作。

回到我们的塞大象进冰箱的问题,假设我们的冰箱很大很大,塞多少东西都没所谓。这时候我们面前有一条长队的大象。在这里,我们大象的数量就是我们问题的规模。通常来说,在做算法分析的时候,我们用n来表示问题的规模。

明白了问题规模和基本操作之后,我们就可以开始做算法分析啦~

笨方法

算法分析主要解决的问题是比较算法之间的效率。我们怎么知道两个算法中哪一个是最好的?听起来,哪个好哪个差直接放到电脑里面跑起来就知道了。哪一个算法在最短的时间内把问题解决了哪一个就快。仔细想一想,电脑的配置、老化程度都会对算法的表现有影响。而且问题规模大起来,总不能跑个十年八年来比较两个算法吧?

更好的办法

想想看,每头大象我们都要做3次操作(打开冰箱,把大象塞进去,关上冰箱)。那我们总共做的操作不就是3n嘛(n为大象的数量,既问题的规模)。

这种靠问题规模和基本操作两个参数来研究算法的效率不需要一个标准的计算机,直接算就好了。真棒!

正式来说,这个3n我们要写成O(3n)。这个叫大O符号,专门用来表示算法的复杂度。在本课中,它表示的是算法的时间复杂度

比较算法

两个算法谁好谁坏可以很直观的通过大O符号来表示。我举个例子:

有人发现上面算法有一个问题,我要塞100头大象,每次都要打开门把大象放进去再关上。这样很浪费时间呀,能不能一次过把门打开,100头大象塞进去,再关上门呢?这样一来我们的操作就变成了

  1. 打开冰箱门
  2. 塞一头大象
  3. 赛第二头大象
  4. 。。。
  5. 塞第n头大象
  6. 关上冰箱门

总共的基础操作是 1 + n + 1, 用 O(2 + n)表示。

现在我们有两个算法的时间复杂度

  1. O(3n)
  2. O(2 + n)

现在,我们来比较一下哪一个算法更好。想象这个问题的规模 – n 越来越大,趋近于无限。1号算法每增加一头大象就多3步操作;而2号算法每增加1头大象只增加1步操作(塞大象进冰箱)。如此看来,1号算法增长速度比2号算法快。这说明问题规模越大,1号需要越长的时间去完成。所以2号会比1号算法更好。

课后作业

  1. 弗洛伊德算法可以找传递闭包也可以找最短路径,下面是它的伪代码。分析一下这个算法的时间复杂度。
 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
 for each vertex v
    dist[v][v] ← 
 for each edge (u,v)
    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
 for k from  to |V|
    for i from  to |V|
       for j from  to |V|
          if dist[i][j] > dist[i][k] + dist[k][j] 
             dist[i][j] ← dist[i][k] + dist[k][j]
         end if
  1. 下面的算法是冒泡算法,冒泡算法是最粗暴简单的排序算法。分析它的时间复杂度
function bubbleSort(array) {
 var length = array.length,
     i,
     j,
     temp;
 for (i = length - 1; 0 < i; i--) {
     for (j = 0; j < i; j++) {
         if (array[j] > array[j + 1]) {
             temp = array[j];
             array[j] = array[j + 1];
             array[j + 1] = temp;
         }
     }
 }
 return array;
}
  1. 在网上找到归并排序的最坏时间复杂度,和上面的冒泡算法比较一下,告诉我哪一个算法更好并说明理由。
1 个赞