算法图解笔记-递归和分治

1.利用递归来求和

recur_sum = function(list_v) {
  n <- length(list_v)
  if (n < 2)
    return(list_v[n]) #基线条件
  return(list_v[1] + recur_sum(list_v[2:n]))  # 递归条件
}

现在测试一下：

recur_sum(1:10)

## [1] 55

recur_sum(1)

## [1] 1

recur_sum(10)

## [1] 10

recur_sum(1:2000)

## [1] 2001000

递归理解起来，很好理解。但是执行起来，确实比较低效的。因为每次都要调用函数体，复制向量，占用内存开销非常大。递归会记录过程，通常保存在栈（stack）中，是一种经典的后进先出的策略。

2. 快速排序

快速排序的思想非常朴素，譬如对5,2,3,8,9,6,1数列进行排序，步骤如下：

• 1)随机选择1个数值作为基准值，譬如5；
• 2)将<5的数放在左边，2,3,1；
• 3)将>5的数放在右边，8,9,6；
• 4)利用递归，对左手边和右手边的数列分别实行步骤1)，2)，3)；
• 5)基线条件为，如果数列只有1个元素，返回该值。

这实际上也是一种分而治之的思想，把对大数列的排序，划分为对多个小数列的排序。

试着写出程序如下：

quick_sort = function(list_v) {
  n <- length(list_v)
  if (n < 2)
    return(list_v[n])
  pivot <- list_v[1]  #设置基准值
  less <- list_v[2:n][list_v[2:n] <= pivot] #小于基准值的数列
  greater <- list_v[2:n][list_v[2:n] > pivot] #大于基准值的数列
  return(c(quick_sort(less), pivot, quick_sort(greater)))
}

测试一下，成功。

quick_sort(c(5,2,3,8,3,9,6,1,1,6))

##  [1] 1 1 2 3 3 5 6 6 8 9

quick_sort(sample(1:100,30))

##  [1]   8   9  14  17  19  28  32  35  36  38  42  43  47  51  56  57  59  67  73
## [20]  74  75  76  82  84  85  87  90  92  98 100

快速排序的运行时间为\(O(n\log_{2}^{n})\)。如果你每次都选到中间值作为基准值，那么栈的高度是\(\log_{2}^{n}\)，每一个栈层，进行的比较次数都是n次，因此最好情况是\(n\log_{2}^{n}\)。

如果基准值选择的不好，每次都选到最小值或者最大值，那么就会导致栈的高度为n层，每一个栈层，进行的比较次数仍然为n次，那么最差情况为\(O(n^{2})\)。