Algorithms

Problem 2.md

(a)

• ExtractMin: 堆顶元素依然是最小值，取出后Heapify一次。时间复杂度：O(logdn*d（注意logdn中d是底数）
• DecreaseKey：减少一个节点的值可能使这个值比它的父亲更小，需要递归的与它当前的父亲比较和交换，直到当前父亲的值更小。时间复杂度O(logdn)
• Heapify：比较当前子堆的堆顶是否比它的儿子小，若不是就将它最小的儿子交换，递归下去。时间复杂度:O(logdn*d)

Problem 3.md

Problem 3

易见，所有点的最短距离处于[0, T(n-1)]范围内。

改良后的Dijkstra：

维护数组T，T[x]表示在当前，与起点距离为x的有哪些点。

1. 初始时x = 0。
2. 每次迭代时，我们只需要从当前位置开始找到一个最近的x并且T[x]不为空。这个点就是当前的最短距离点。

function Dijkstra(Graph, source):
  for each i in [0, T(n-1)]
    T[i]  := []
  x := 0
  dist[source]  := 0                   // Distance from source to source
  add source to T[0]
  for each vertex v in Graph:          // Initializations
    if v ≠ source
      dist[v]  := infinity             // Unknown distance function from source to v
      previous[v]  := undefined        // Previous node in optimal path from source
    end if
    add v to Q                         // All nodes initially in Q (unvisited nodes)
    visited[v]  := false
  end for
  visited[source]  := true
  while Q is not empty:                // The main loop
    while T[x] == []:
      x++
    end while
    u  := T[x][0]
    if visited[u]:
      continue
    end if
    visited[u]  := false
    remove u from T[x]
    remove u from Q 
    for each neighbor v of u:          // where v has not yet been removed from Q.
      alt := dist[u] + length(u, v)
      if alt < dist[v]:                // A shorter path to v has been found        
        dist[v]  := alt 
        previous[v]  := u
        add v to T[alt] 
      end if
    end for
  end while
  return dist[], previous[]
end function

Problem 4.md

Problem 4

设x的长度为m，y的长度为n。 令 f[i][j] 为 x的第i个前缀(x[1..i])和y的第j个前缀之间(y[1..j])的编辑距离（字符串索引从1开始），显然 f[m][n] 为 x 与 y 之间的编辑距离。

可以得到

1. 对 0 <= i <= m，有 f[i][0] = i

2. 对 0 <= i <= n，有 f[0][i] = i

3. 对 1 <= i <= m，1 <= j <= n，

   • 考虑修改：
     • 若 x[i] != y[j]，则 f[i][j] = f[i - 1][j - 1] + 1;
     • 若 x[i] == y[j]，则 f[i][j] = f[i - 1][j - 1];
   • 考虑在x末尾添加字符，有 f[i][j] = f[i][j - 1] + 1
   • 考虑在x末尾删除字符，有 f[i][j] = f[i - 1][j] + 1

   上述三种情况取最小

时间复杂度为O(nm)。