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 solvethe original problem. In contrast, dynamic programming applies when the subproblemsoverlap—that is, when subproblems share subsubproblems. (查看原文)
Formost 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 algorithmswill be implemented as computer programs. In the RAM model, instructions are executed oneafter another, with no concurrent operations. (查看原文)
INSERTION-SORT(A) cost times1 for j ← 2 to length[A] c1 n ##这个不是N-1吗？？？？？？？？？？？？？？？？？？2 do key ← A[j] c2 n - 13 ▹ Insert A[j] into the sortedsequence A[1 j - 1]. 0 n - 14 i ← j - 1 c4 n - 15 while i > 0 and A[i] > key c56 do A[i + 1] ← A[i] c67 i ← i - 1 c78 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 isnot 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 notbounded by a decreasing geometric series. To bound a series by a geometric series, one mustshow that there is an r < 1, which is a constant, such that the ratio of all pairs of consecutiveterms never exceeds r. In the harmonic series, no such r exists because the ratio becomesarbitrarily close to 1. (查看原文)
The total number of levels of the "recursion tree" in Figure 2.5 is lg n + 1. This fact is easilyseen by an informal inductive argument. The base case occurs when n = 1, in which case thereis 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 2inodes is lg 2i + 1 = i + 1 (since for any value of i, we have that lg 2i = i). Because we areassuming that the original input size is a power of 2, the next input size to consider is 2i+1. Atree with 2i+1 nodes has one more level than a tree of 2i nodes, and so the total number oflevels is (i + 1) + 1 = lg 2i+1 + 1. (查看原文)
