We can easily make each of them run in time O using ordinary binary heaps. By using Fibonacci heaps, Prim’s algorithm runs in time O(E+VlgV ), improves over the binary-heap implementation if |V| is much smaller than |E|. (查看原文)
divide-and-conquer algorithms partition the problem into disjoint subproblems,
solve the subproblems recursively, and then combine their solutions to solve
the original problem. In contrast, dynamic programming applies when the subproblems
overlap—that is, when subproblems share subsubproblems. (查看原文)
For
most of this book, we shall assume a generic one-processor, random-access machine (RAM)
model of computation as our implementation technology and understand that our algorithms
will be implemented as computer programs. In the RAM model, instructions are executed one
after another, with no concurrent operations. (查看原文)
INSERTION-SORT(A) cost times
1 for j ← 2 to length[A] c1 n ##这个不是N-1吗？？？？？？？？？？？？？？？？？？
2 do key ← A[j] c2 n - 1
3 ▹ Insert A[j] into the sorted
sequence A[1 j - 1]. 0 n - 1
4 i ← j - 1 c4 n - 1
5 while i > 0 and A[i] > key c5
6 do A[i + 1] ← A[i] c6
7 i ← i - 1 c7
8 A[i + 1] ← key c8 n - 1 (查看原文)
The bug in the argument is that the "constant" hidden by the "big-oh" grows with n and thus is
not constant. We have not shown that the same constant works for all n. (查看原文)
The ratio of the (k + 1)st and kth terms in this series is k/(k + 1) < 1, but the series is not
bounded by a decreasing geometric series. To bound a series by a geometric series, one must
show that there is an r < 1, which is a constant, such that the ratio of all pairs of consecutive
terms never exceeds r. In the harmonic series, no such r exists because the ratio becomes
arbitrarily close to 1. (查看原文)
The total number of levels of the "recursion tree" in Figure 2.5 is lg n + 1. This fact is easily
seen by an informal inductive argument. The base case occurs when n = 1, in which case there
is only one level. Since lg 1 = 0, we have that lg n + 1 gives the correct number of levels.
Now assume as an inductive hypothesis that the number of levels of a recursion tree for 2i
nodes is lg 2i + 1 = i + 1 (since for any value of i, we have that lg 2i = i). Because we are
assuming that the original input size is a power of 2, the next input size to consider is 2i+1. A
tree with 2i+1 nodes has one more level than a tree of 2i nodes, and so the total number of
levels is (i + 1) + 1 = lg 2i+1 + 1. (查看原文)
