toBeTheLight.github.io 荒原

阅读:《算法图解》(1)大O表示法,递归与D&C

2017-11-20
toBeTheLight

大O表示法,递归与D&C

第一章 算法简介

二分查找

  1. 前提:已排序
  2. 方式:在有序列表中逐次取中间项(或某一项)的值,获取与目标值的大小比较信息,做排除。
    def binary_search(list, item):
     low = 0
     haight = len(list) - 1
     while(low <= high):
         mid = (low + high)/2
         guess = list[mid]
         if guess < item:
             low = mid + 1
         elif guess > item:
             high = mid - 1
         elif guess == item:
             return mid
     return None
    

大O表示法

  • 大O表示法指出了算法运行时间(随元素数)的增速,可让你比较方便的比较达到目的的(所需的)操作(次)数。
  • 常见大O表示法运行时间:

注:log为log2

大O 算法 别称 备注
O(logn) 二分查找 对数时间 每一步都除以2,所以是对数
O(n) 简单查找 线性时间 从头数到尾,所以等于项数n
O(n*logn) 快速排序   拆logn次,每次比较n回
O(n^2) 选择排序   比较次数为(n-1)+…+1为(n^2)/2,省略常数1/2为n^2
O(n!) 旅行商问题   所有排列组合,阶乘

小结

  • 二分查找的速度比简单查找快得多。
  • O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快的多。
  • 算法运行时间并不以秒为单位。
  • 算法运行时间是从其增速的角度衡量的。
  • 算法运行时间用大O表示法表示。

第二章 选择排序

数组和链表

  1. 数组在内存中是连续的
  2. 链表中的元素可存储在内存的任何位置,链表中的每个元素都存储了下一个元素的地址。
  3. 数组的读取速度很快(因为可按索引直接取值,而链表要顺序查找)。
  4. 链表的插入和删除速度很快(因为链表只需要改两个指向的指针,而数组需要重新排改动元素后的所有元素的索引)。

选择排序

一个逐项遍历找当前最大值(或最小值)的排序算法,每次遍历时间为O(n),需遍历n次。(找出最大的,找出第二大的,找出第三大的…)

第三章 递归

基线条件和递归条件

  1. 基线条件:指函数不再调用自己的条件,即退出递归的条件。
  2. 递归条件:函数调用自己的条件。

  1. 递归的本质是压栈和出栈,当然函数的调用也是。
  2. 递归层深可能会占用大量内存,引起溢出。
  3. 使用尾递归,大部分语言都是有尾递归优化的。

小结

  • 递归指的是调用自己的函数。
  • 每个递归函数都有两个条件,基线条件和递归条件。
  • 栈有两种操作:压入和弹出。
  • 所有函数调用都进入调用栈。
  • 调用栈可能很长,这将占用大量内存。

第四章 快速排序

D&C分而治之

divide and conquer

步骤

  • 找出基线条件
  • 分解成子问题

特征

  • 通过分解到一定程度可以轻松解决
  • 分解为的子问题具有最优子结构性质
  • 分解出的子问题可以合并为该问题的解。
  • 分解出的子问题互斥

快排算法

找一项的值为基准值,将元素与基准值按大小关系分为左分区和右分区,并在左分区和右分区做重复操作,直至分区只有一项(分而治之),然后合并所有(单项)子分区。

  • 基线条件 length<2不需要排序
  • 将数组拆为一个个length<2的数组
  • 合并
function quickSort (arr) {
  if (arr.length < 2) {
    return arr
  }
  let baseValue = arr.splice(arr.index - 1, 1)
  let left = []
  let right = []
  arr.forEach(item => {
    if(item > baseValue) {
      right.push(item)
    } else {
      left.push(item)
    }
  })
  return quickSort(left).concat(baseValue, quickSort(right))
}

再谈大O表示法

最糟情况下,快排运行时间为O(n^2)(基准值选取最边缘值会导致无法进行拆分),平均情况下为O(nlogn)。 合并排序的运行时间总为O(nlogn)

合并排序(归并排序)

将待排序列逐层拆分,直到成为单个项,并逐层两两合并,合并时比较第一项的大小并放入新的数组(同样是分而治之)。

[0, 8, 1, 3, 4, 7]
         ↓        
[0, 8, 1] [3, 4, 7]
         ↓
[0] [8, 1] [3] [4, 7]
         ↓
[0] [8] [1] [3] [4] [7]
         ↓
[0, 8] [1, 3] [4, 7]
// 合并 [0, 8] [1, 3],每次取索引为0的值最小的项
// (1):[0] [8] [1, 3] [4, 7]
// (2):[0, 1] [8] [3] [4, 7]
// (3):[0, 1, 3] [8] [] [4, 7]
// (4):[0, 1, 3, 8] [4, 7]
         ↓
[0, 1, 3, 8] [4, 7]
// (1):[0] [1, 3, 8] [4, 7]
// (2):[0, 1] [3, 8] [4, 7]
// (3):[0, 1, 3] [8] [4, 7]
// (4): [0, 1, 3, 4] [8] [7]
// (5): [0, 1, 3, 4, 7] [8]
// (6): [0, 1, 3, 4, 7, 8]
         ↓
[0, 1, 3, 4, 7, 8]
Array.prototype.mergeSort = function() {
  function merge(left, right) {
    var final = []
    while (left.length && right.length)
      final.push(left[0] <= right[0] ? left.shift() : right.shift())
    return final.concat(left.concat(right))
  };
  var len = this.length
  if (len < 2) return this
  var mid = parseInt ( len / 2 )
  return merge(this.slice(0, mid).mergeSort(), this.slice(mid).mergeSort())
};

小结

  • D&C将问题逐步分解。使用D&C处理列表时,基线条件很可能是空数组或只包含一个元素的数组。
  • 实现快速排序时,请随机的选择用作基准值的元素。快速排序的平均运行时间为O(nlogn)。
  • 大O表示法中的常量有时候事关重大,这就是快速排序比合并排序快的原因。
  • 比较简单查找和二分查找时,常量几乎无关紧要,因为列表很长时,O(logn)的速度比O(n)快的多。

相关文章

上一篇 Object api

Content