算法导论(原书第3版)的笔记(24)

>我来写笔记

按有用程度 按页码先后 最新笔记

  • GilGaMesh

    GilGaMesh

    想复习一下KMP,于是读了最新版的算法导论,发现翻译还是个大问题啊! 589页某句话是: 在最好的情况下,k=0,因此s'=s+q,并且立刻能得出偏移s+1,s+2,s+3,…s+q-1。 不明所以。而英文版是: In the best case, k=0,so that s‘=s+q, and we immediately rule out shifts s+1,s +2;...,s+q-1. 原来是可以排除掉那些无效偏移的意思。 该页另一句话是: 即π[q]是Pq的真后缀P的最长前缀长度。 又是不明所以的一句话。英文版原...   (6回应)

    2013-01-23 20:05   2人喜欢

  • 传奇之后

    传奇之后

    知乎写了个两万字总结,这本书值得这么做。 https://zhuanlan.zhihu.com/p/133236583

    2020-04-19 07:51

  • 功不唐捐菠萝头

    功不唐捐菠萝头 (上帝不响,像一切全由我定。)

    分析的有点太细了呀…… 原来就会的反而给绕进去 见仁见智叭

    2020-02-03 13:16

  • 上上谦

    上上谦

    第一章 算法在计算机中的作用 作为广告的一章,提到了很多耳熟能详的词语,先记录以下,假设真的能把这本书看完的话,到时候回来对着这个记录,一个一个看是不是都讲明白了: 1.路由算法 第24章 2.搜索引擎 第11章、第32章 3.加密算法 第31章 4.线性规划 第29章 5.图 第24章 6.动态规划 第十五章 7.拓扑 第22章 8.傅立叶变换 第30章 9.NP完全 第34章 话说作者上来就各种推荐靠后的章节,仿佛在说:一定要坚持下...

    2019-05-09 23:42

  • 丽拉先生

    丽拉先生 (必要时撒谎)

    我们把 表示一个数组或对象的变量 看做 指向数组或对象的数据 的一个指针。对于某个对象x的所有属性f,赋值 y=x 导致 y.f 等于 x.f。进一步,若现在置 x.f=3,则赋值后不但 x.f 等于3,而且 y.f 也等于3。换句话说,在赋值 y=x 后,x 和 y 指向相同的对象。 We treat a variable representing an array or object as a pointer to the data representing the array or object. For all attributes f of an object x, setting y ...

    2019-03-25 16:40

  • Chipmunk柴

    Chipmunk柴 (Start here, Go anywhere)

    练习题: Determine if a small string is a substring of another large string. Method 1: brute force. 2 loops, outer loop go through large string, inner loop go through small target substring, compare cur index. If does not match, return false. Time complexity: O(n^2) Space complexity: O(1) Method 2: Rabin-Carp Algorithm Hash the substring with hash function. Assumption: original string: T, lengt...

    2019-01-22 03:47

  • [已注销]

    [已注销]

    归并排序 def merge_sort(ls: list, start: int, end: int) -> list: """Merge sort a list, from index 'start' to 'end'.""" if start < end: b1 = (end + start) // 2 merge_sort(ls, start, b1) merge_sort(ls, b1 + 1, end) merge(ls, start, b1, end) return ls def merge(s, a1, b1, a2): """merge s[a1:b1+1] and s[b1+1:a2+1] into p[a1:a2+1]""" i = a1 j = b1 + 1 k = a1 p = [0] * (a2 + 1) # a helper list...

    2018-04-06 14:26

  • [已注销]

    [已注销]

    选择排序 def selection_sort(ls): if len(ls) < 2: return ls # loop invariant: every element is no bigger than all elements on its right for i in range(len(ls)): s = i for j in range(i, len(ls)): if ls[j] < ls[s]: s = j ls[i], ls[s] = ls[s], ls[i] return ls

    2018-04-05 12:15

  • [已注销]

    [已注销]

    def linear_search(A: list, v: "target value") -> int: """Search for v in list A and return index.""" for i in range(len(A)): if A[i] == v: return i return None 线性查找的循环不变式:对于n元列表,算法能够返回目标值第一次出现的位置,或者在目标值不存在时返回None。 初始:空列表,不含任何元素,返回None。不变式成立。 保持:假设算法对于n元列表正确,对于(n+1)元列表,有两种情况,1. 目标值在前n个元...

    2018-04-05 11:39

  • [已注销]

    [已注销]

    插入排序的逻辑:将输入分割为“已排序“和”未排序“两部分。”已排序“初始大小为1。每次迭代从“未排序”中取一个数,移动到“已排序”序列中的正确位置。“未排序”大小为0时停止迭代,“已排序”序列包含所有输入,算法终止。 插入排序的正确性: - 初始条件:“已排序”只有一个数,必然是已排序的,因为它右边没有比它小的数,它左边也没有比它大的数。 - 保持:在向“已排序”中插入新的数时,算法通过自右向左的对比,...

    2018-04-05 10:24

<前页 1 2 3 后页>

笔记是你写在书页留白边上的内容;是你阅读中的批注、摘抄及随感。

笔记必须是自己所写,不欢迎转载。摘抄原文的部分应该进行特殊标明。

算法导论(原书第3版)

>算法导论(原书第3版)