算法笔记

2019-12-28 6375

算法选修课自学笔记。

分治算法

线性时间选择

O(n)

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
27
28
29
30
31
32
33
//随机线性选择（伪代码），O(n)

int partition (Type a[], int p, int r) {
  int i = p, j = r+1
  Type x = a[p]    //第一个元素为基准
  while (true) {
    while (a[++i] < x && i < r)    //左标兵向右
    while (a[--j] > x)    //右标兵向左
    if (i >= j)
      break
    swap(a[i], a[j])    //交换位置
  }
  a[p] = a[j]    //第一个元素和最小数交换位置
  a[j] = x
  return j    //返回基准位置
}

int randomizedPartition (Type a[], int p, int r) {
  int i = random(p, r)
  swap(a[i], a[p])    //将随机元素作为基准（第一个元素）
  return partition(a, p, r)
}

Type randomizedSelect(Type a[], int p, int r, int k) {    //第k小个元素
  if (p == r)    //只有一个元素
    return a[p]
  int i = randomizedPartition(a, p ,r)    //i为随机基准位置
  j = i-p+1    //计算数组a[p:i]个数（左边）
  if (k <= j)
    return randomizedSelect(a, p, i, k)    //落在左边
  else
    return randomizedSelect(a, i+1, r, k-j)    //落在右边
}

动态规划

01背包问题

O(n)

参考：算法题之动态规划-01背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void knapsack(Type v, int w, int c, int n, Type **m) {     //价值，重量，容量，数量，矩阵
  int jMax = min(w[n]-1, c)
    for (int j = 0; j <= jMax; j++)
      m[n][j] = 0
    for (int j = w[n]; j <= c; j++)
      m[n][j] = v[n]
    for (int i = n-1; i > 1; i==) {
      jMax = min(w[i] - 1, c)
      for (int j = 0; j <= jMax; j++)
        m[i][j] = m[i+1][j]
      for (int j =w [i]; j <= c; j++)
        m[i][j] = max(m[1][c], m[2][c-w[1]]+v[i])
      m[1][c] = m[2][c]
      if (c >= w[1])
        m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1])
    }
}
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
27
28
29
// 01背包问题，动态规划，O(n)

var knapsack = {
  getMaxValue: function (weight, value, n, w) {    //各物品重量，各物品价值，物品数量，背包容量
    var table = new Array(n)
    for (var i = 0; i < table.length; i++) {
      table[i] = new Array(w)
      for (var j = 0; j < table[i].length; j++)
        table[i][j] = 0
    }
    for (var i = 1; i < n; i++) {    //物品数量
      for (var j = 1; j < w; j++) {    //背包容量
        if (weight[i] > j)
          table[i][j] = table[i - 1][j]    //装不下(物品价值大于背包容量)
        else
          table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i]] + value[i])    //装得下(max{装，不装})
      }
    }
    return table[n-1][w-1]
  },
  main: function () {
    var weight = new Array(6, 3, 5, 4, 6)
    var value = new Array(2, 2, 6, 5, 4)
    var n = 5,
      w = 10
    return this.getMaxValue(weight, value, n, w)
  }
}
console.log(knapsack.main())

回溯法

n皇后问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool place(int t) {
	for (int i; i < t; i++)
    if ((x[i] == x[t]) || (abs(t-i) == abs(x[t]-x[i])))
      return false
  return true
}

void backtrack(int t) {
  if (t > n)
    sum++
  else {
    for (int i; i < n; i++) {
      x[t] = i    //关键
      if (place(t))
        backtrack(t+1)
    }
  }
}
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
27
//n皇后问题，回溯法

var n = 4
var x = []
function place(t) {    //判断第t个皇后能否放在第i个位置
  var flag = true
  for (var j = 0; j < t; j++) {
    if (x[t] === x[j] || t - j === Math.abs(x[t] - x[j])) {    //判断与竖、撇捺是否有冲突
      flag = false
      break
    }
  }
  return flag
}
function backtrack(t) {
  if (t === n) {    //当前位置到了叶节点输出一个解
    console.log(x)
  } else {
    for (var i = 0; i < n; i++) {
      x[t] = i
      if (place(t)) {
        queen(t + 1)    //不冲突进行下一行搜索
      }
    }
  }
}
backtrack(0)

贪心算法

最小生成树

O(n^2)

MST性质（最小生成树定义）：假设G=(V, E)是一个连通网，U 是顶点集V的真子集。若(u, v )是一条具有最小权值的边，其中u∈U， v∈V-U，则必存在一棵包含边(u, v)的最小生成树。

MST性质证明：假设G的任何一颗最小生成树都不含边(u, v)。将边(u, v)添加到G的一颗最小生成树上，将产生含有边(u, v)的圈，并且在这个圈上有一条不同于(u, v)的边(u’, v’)，使得u’∈U，v’∈V-U。将这条边(u’, v’)删去，得到G的另一颗生成树T’。因为c[u][v]<=c[u’][v’]，所以T’的耗费<=T的耗费。于是T’是一颗含有边(u, v)的最小生成树，与原假设矛盾，即证明MST成立。

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
27
28
void prim(int n, Type **c) {
  Type lowcost[maxint]
  int closet[maxint]
  bool s[maxint]
  s[1] = true
  for (int i = 2; i <= n; i++) {
    lowcost[i] = c[1][i]
    closet[i] = 1
    s[i] = false
  }
  for (int i = 1; i < n; i++) {
    Type min = INF
    int j = 1
    for (int k = 2; k <= n; k++) {
      if ((lowcost[k] < min) && (!s[k])) {
        min = lowcost[k]
        j = k
      }
    }
    s[j] = true
    for (int k = 2; k <= n; k++) {
      if ((c[j][k] < lowcost(k)) && (!s[k])) {
        lowcost[k] = c[j][k]
        closet[k] = j
      }
    }
  }
}
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
27
28
29
30
31
32
33
34
35
36
//最小生成树，prim算法（伪代码）

function prim(int n, int u0, int c[N][N]) {
  s[u0] = true    //第一个点在U内
  //初始化
  for (int i; i < n; i++) {
    if (i !== u0) {
      lowcost[i] = c[u0][i]    //最近权为到u0的权
      closet[i] = u0    //最近点为u0
      s[i] = false    //不在U内
    } else {
      lowcost[i] = 0
    }
  }
  for (int i = 1; i < n; i++) {
    int temp = INF    //权
    int t = u0
    for (int j = 1; j < n; j++) {
      if ((!s[j]) && (lowcost[j] < temp)) {    //不在U内且权更小
        t = j
        temp = lowcost[j]
      }
    }
    if (t === u0)    //找不到最小路径点
      break
    s[t] = true    //加入U
    //更新lowcost和closet
    for (int j = 1; j <= n; j++) {
      if ((!s[j]) && (c[t][j] < lowcost[j])) {    //不在U内且t到j的权小于最短权
        lowcost[j] = c[t][j]
        closest[j] = t
      }
    }
  }
  //最小费用为lowcost之和
}

排序算法比较

排序方式 平均情况 辅助空间 稳定性
冒泡排序 O(n2) O(1) 稳定
选择排序 O(n2) O(1) 不稳定
插入排序 O(n2) O(1) 稳定
希尔排序 O(nlogn) O(1) 不稳定
快速排序 O(nlogn) O(nlogn) 不稳定
归并排序 O(nlogn) O(n) 稳定
堆排序 O(nlogn) O(1) 不稳定
桶排序 O(n+c) O(1) 不稳定
基数排序 O(nlog(r)m) O(r) 稳定

渐进复杂度

3n2+10n n2/10+2n 21+1/n logn3 10log3n
O(n2) O(2n) O(1) O(logn) O(n)

2 < logn <n2/3 < 20n < 4n2 < 3n < n!

  • f(n)的阶 <= g(n)的阶 => f(n)=O(g(n))
  • f(n)的阶 >= g(n)的阶 => f(n)=Ω(g(n))
  • f(n) == g(n) => f(n)=θ(g(n))

基本概念

算法特性
  • 有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止。
  • 确定性：算法的每一步骤必须有确切的定义。
  • 可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。
  • 输入输出：有0个或多个输入，有1个或多个输出。
好算法标准

高效率，低存储。

正确性、易读性、健壮性、高效性、低存储性

分支限界法

分支限界法与回溯法的区别

  • 二者都是在问题的解空间数上搜索问题解的算法。

  • 分支限界法采用广度优先或最小耗费优先方式生成解空间；回溯法采用深度优先方式生成解空间。

  • 分支界限法一般用于求最优解；回溯法一般用于求全部解。

  • 分支界限法需要额外辅助空间；回溯法不需要。

队列式与优先队列式的区别
  • 队列式：将活结点组织成一个队列，按先进先出原则选取下一个节点。
  • 优先队列式：将活结点组织成一个优先队列，按优先级最高原则选取下一个节点。
查看评论