《算法导论(原书第3版)》的原文摘录

  • 动态规划算法的设计可以分为如下四个步骤: 1 描述最优解的结构。 2 递归定义最优解的值。 3 按自底向上的方式计算最优解的值。 4 由计算出的结果构造一个最优解。 (查看原文)
    silentsongs 1回复 4赞 2012-11-13 18:32:29
    —— 引自第192页
  • 在最好的情况下,k=0,因此s'=s+q,并且立刻能得出偏移s+1,s+2,s+3,…s+q-1。 (查看原文)
    GilGaMesh 6回复 2赞 2013-01-23 20:05:10
    —— 引自第589页
  • In the best case, k=0,so that s‘=s+q, and we immediately rule out shifts s+1,s +2;...,s+q-1. (查看原文)
    GilGaMesh 6回复 2赞 2013-01-23 20:05:10
    —— 引自第589页
  • 即π[q]是Pq的真后缀P的最长前缀长度。 (查看原文)
    GilGaMesh 6回复 2赞 2013-01-23 20:05:10
    —— 引自第589页
  • π[q] is the length of the longest prefix of P that is a proper suffix of Pq. (查看原文)
    GilGaMesh 6回复 2赞 2013-01-23 20:05:10
    —— 引自第589页
  • 考虑对数组A中的n个数进行排序:首先找出A中的最小元素,并将其与A[1]中的元素进行交换。接着找出A中的次小元素,并将其与A[2]中的元素进行交换。对A中头n-1个元素继续这一过程。写出这个算法的伪代码,该算法称为选择排序(selection sort)。对这个算法来说,循环不变式是什么?为什么它仅需要在头n-1个元素上运行,而不是在所有n个元素上运行?以Θ形式写出选择排序的最佳和最坏情况下的运行时间。 (查看原文)
    龙三 2013-01-30 11:02:26
    —— 引自第24页
  • 如果一个节点是红的,则它的两个儿子都是黑的。 (查看原文)
    栗子先生 1赞 2013-04-21 16:40:10
    —— 引自第164页
  • 如果一个节点是红的,那它的父亲一定是黑的 (查看原文)
    栗子先生 1赞 2013-04-21 16:40:10
    —— 引自第164页
  • 红黑树的节点至少是红黑相间 (查看原文)
    栗子先生 1赞 2013-04-21 16:40:10
    —— 引自第164页
  • 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|. (查看原文)
    丽娃河畔 2019-12-05 22:45:52
    —— 引自第624页
  • HEAPSORT(A) 1 BUILD-MAX-HEAP(A) 2 fori=A. length downto 2 3 exchange A[1] with A[i] 4 A.heap-size= A.heap-size-1 5 MAX-HEAPIFY(A, 1) 图6-4给出了一个在 HIEAPSORT的第1行建立初始最大堆之后,堆排序操作的一个例子图6-4显示了第2~5行for循环第一次迭代开始前最大堆的情况和每一次送代之后最大堆的情况HEAPSORT过程的时间复杂度是O(nlgn),因为每次调用 BUILD-MAX- HEAP的时间复杂度是O(n),而nー1次调用MAX- HIEAPIEY,每次的时间为O(lgn)。 (查看原文)
    丽娃河畔 2019-12-17 00:40:41
    —— 引自第89页
  • 在程序的每一步中,从A[i]、 A[LEFT(i)和A[RIGHT(i)]中选出最大的,并将其下标存储在largest中。如果A[i]是最大,那么以i为结点的子树已经是最大堆,程序结束。否则,最大元素是的某个孩子结点,则交换[i]和原来的A[largest]的值。从而使i及其孩子都满足最大堆的性质。在交換,下标为 largest的结点的值是原来的A[i],于是以该结点为根的子树又有可能会违反最大堆的性质。因此,需要对该子递归调用MAX- HEAPIFY。 (查看原文)
    丽娃河畔 2019-12-17 00:40:41
    —— 引自第86页
  • 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. (查看原文)
    ?.. 2012-03-19 21:22:18
    —— 引自第23页
  • 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 (查看原文)
    ?.. 2012-03-20 20:02:01
    —— 引自第25页
  • 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. (查看原文)
    ?.. 2012-03-20 20:05:55
    —— 引自第925页
  • 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. (查看原文)
    ?.. 2012-03-20 20:09:37
    —— 引自第926页
  • 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. (查看原文)
    ?.. 2012-03-21 20:29:20
    —— 引自第35页
  • As an example, consider any quadratic function f .n/ D an2 C bn C c, where a, b, and c are constants and a > 0. Throwing away the lower-order terms and ignoring the constant yields f .n/ D ‚.n2/. Formally, to show the same thing, we take the constants c1 D a=4, c2 D 7a=4, and n0 D 2 max.jbj =a; p jcj =a/. (查看原文)
    ?.. 2012-03-22 22:18:23
    —— 引自第46页
  • 1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort? (查看原文)
    ?.. 2012-03-26 20:35:17
    —— 引自第14页
  • Describe a‚.nlgn/-time algorithm that, given a setSofnintegers and another integer x, determines whether or not there exist two elements in Swhose sum is exactly x. (查看原文)
    邻家の打工人 2回复 2012-06-04 10:32:56
    —— 引自第39页
<前页 1 2 3 4 后页>