编程珠玑笔记(10)-算法设计技术

  在这一章中,作者对同一个问题依次介绍了4种不同时间复杂度的算法,算法的执行速度依次变得更快。据此阐述了作者的(其实也是被普遍认同的)一个观点:复杂深奥的算法有时可以极大地提高程序性能。(纵然在体系结构领域结论往往是相反的。)

  • 问题

  来自一维模式识别的问题。问题的输入是具有n个浮[……]

Read more

编程珠玑笔记(4)-啊哈!算法(III)

  • 问题C
  • 给定一个英语字典,找出其中的所有变位词集合。例如,“pots”、“stop”和“tops”互为变位词,因为每一个单词都可以通过改变其他单词中字母的顺序来得到。

  • 解答
  •   我们获得的啊哈!灵光一现就是标识字典中的每一个词,使得在相同变位词类中的单词具有相同的标识。然后,将所有相同标识的[……]

    Read more

    编程珠玑笔记(3)-啊哈!算法(II)

  • 问题B
  •   将一个n元一维向量向左循环移位i个位置。简单的代码使用一个n元的中间向量在n步内完成该工作。你能够仅使用数十个额外字节的存储空间,在正比于n的时间内完成向量的旋转?
      可以通过如下方式解决该问题:首先将x的前i个元素复制到一个临时数组中,然后将余下的n-i个元素向左移动i个位置,最[……]

    Read more

    编程珠玑笔记(2)–啊哈!算法(I)

  • 问题A
  •   给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数(在文件中至少缺失一个这样的整数)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,但是仅有几百字节的内存,又该如何解决该问题?

  • 解答
  •   我们从表示每个整数的32[……]

    Read more

    编程珠玑笔记(1)–开篇

  • 作者在书中经过与友人的讨论后对问题的准确描述
    • 输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。
      输出:按升序排列的输入整数的列表。
      约束:最多有(大约)1MB的内存空间可用,有充足的磁盘[……]

    Read more