分而治之

分而治之是算法设计中的一种方法，它将问题分为多个和原问题相似的小问题，递归解决小问题，再将解决方式合并以解决原来的问题。

算法步骤:
1.分解原问题为多个子问题
2.解决子问题，用返回解决子问题的方式的递归算法
3.组合这些子问题的解决方式，得到原问题的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 分而治之版本二分搜索

  const DOES_NOT_EXIST = -1
  // 分而治之版本的二分搜索法，主要利用递归
  function binarySearchRecursive (array, value, low, high, compareFn = defaultCompare) {
    if (low <= high) {
      const mid = Math.floor((low+high)/2)
      const element = array[mid]
      if (compareFn(element, value) === Compare.LESS_THAN) {
        return binarySearchRecursive(array, value, mid+1, high, compareFn = defaultCompare)
      } else if (compareFn(element, value) === Compare.BIGGER_THAN) {
        return binarySearchRecursive(array, value,low, mid-1, compareFn = defaultCompare)
      } else {
        return mid
      }
    }
    return DOES_NOT_EXIST;
  }


  export function binarySearch(array, value, compareFn = defaultCompare) {
    const sorted = quickSort(array) // 二分法需要是一个有序的升序数组
    const low = 0
    const high = sorted.length - 1
    return binarySearchRecursive(array, value, low, high, compareFn)
  }

动态规划(dynamic programming, DP)

也是一种将复杂问题分解成更小的子问题来解决的优化技术。在大型公司的编程题中非常常见。

算法步骤:
1.定义子问题
2.实现要反复执行来解决的子问题部分
3.识别并求出基线条件

背包问题

给出一组项，各自有值和容量，目标是找出总值最大的项的集合。这个问题的限制是，总容量必须小于等于“背包”的容量。

最长公共子序列

给出一组项，各自有值和容量，目标是找出总值最大的项的集合。这个问题的限制是，总容量必须小于等于“背包”的容量。

矩阵链相乘

给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法（计算次数尽可能少）。相乘运算不会进行，解决方案是找到这些矩阵各自相乘的顺序。

硬币找零

给出面额为d1, …, dn的一定数量的硬币和要找零的钱数，找出有多少种找零的方法。

图的全源最短路径

给出面额为d1, …, dn的一定数量的硬币和要找零的钱数，找出有多少种找零的方法。

分而治之和动态规划的区别

分而治之:把问题分解成互相独立的子问题，然后组合起来

动态规划:将问题分解成互相依赖的子问题

贪心算法

回溯算法

函数式编程(FP)

比如打印一个数组中的值,以下是命令式编程和函数式编程的区别

  • 命令式编程
    1
    2
    3
    4
    5
    6
    const printArray = function (array) {
        for (var i = 0; i < array.length; i++) {
            console.log(array[i])
        }   
    }
    printArray([1,2,3,4,5])
  • 函数式编程
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 一个负责迭代，一个负责打印
    const forEach = (array, action) => {
        for (var i = 0; i < array.length; i++) {
            action(array[i])
        }
    }

    const logItem = (item) => {
        console.log(item)
    }
    forEach([1,2,3,4,5],logItem)
    函数式编程需要注意的几点
  • 函数和数据集合是函数式编程得核心
  • 函数式编程可以滥用函数，命令式编程中，使用循环，赋值，条件和函数
  • 函数式编程中避免副作用和可变数据，不会修改传入函数得数据，如果需要修改也会拷贝一个副本再修改

寻找数组中的最小值

1
2
const min = arr => Math.min(...arr)
console.log(min([1,2,3,4,5,6]))

大O表示法

  • O(1)-常数级
  • O(log(n))-对数级别
  • O(log(n)c)-对数多项式
  • O(n)-线性的
  • O(n²)-二次的
  • O(n的c次方)-多项式的
  • O(c的n次方)-指数级别
    image

衡量算法效率一般是考虑CPU时间占用，内存占用，硬盘占用，网络占用。当讨论大O表示法时候，说的是CPU的时间占用

O(1)

1
2
3
4
5
function increment(num) {
    return ++num
}

increment(1) //运行函数，执行时间为x，用不用的参数依然是x，和参数无关，因此，以上函数复杂度为O(1)(常数)

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
function sequentialSearch(array,value){
    for (let i = 0; i < array.length; i++) {
        if (value === array[i]) {
            return i
        }
    }
    return -1
}
// 如果要传递给数组是([1,...,10]),寻找1的话，第一次就可以找到，开销是1。如果要搜索元素11，就会迭代10次，开销就是10。如果传入1000个，开销就是1000

所以时间复杂度就是O(n),n是输入数组的大小。

O(n²)

1
2
3
4
5
6
7
8
9
10
function bubbleSort(array){
    for (let i = 0; i < array.length; i++){
        for (let j = 0; j < length - 1; j++){
            if (array[j]===array[j+1]){
                swap(array,j,j+1)
            }
        }
    }
}
时间复杂度O(n)只有一层循环，而O(n²)的代码有双层嵌套循环，如果算法有三层，那么时间复杂度就是O(n³)

排序算法时间复杂度

image

数据结构时间复杂度

image