Algorithms Fourth Edition

[ThomsonTang]

书名卡

• 书名：算法（第四版）
• 原名：Algorithms Fourth Edition
• 简介：全面讲述了算法和数据结构必备的相关知识。本书站在实用的角度出发，让读者不需要太复杂和高深的数学知识就可以理解和学习这些基础的算法。全书主要包括：Fundamentals、Sorting、Searching、Graphs、Strings和Context这几个部分。
• 出处：算法（第4版） (豆瓣)

作者卡

• 作者：Robert Sedgewick 、Kevin Wayne
• 简介：
  • Robert Sedgewick, 斯坦福大学博士，导师是著名人物 Donald Knuth - Wikipedia。担任普林斯顿大学计算机系的教授。其研究方向包括解析组合学、数据结构和算法的分析与设计、程序可视化等。
  • Kevin Wayne，康奈尔大学博士，普林斯顿大学计算机科学系的高级讲师，研究方向包括算法的设计、分析和实现。
• 出处：Robert Sedgewick (computer scientist) - Wikipedia

[ThomsonTang]

术语卡——Scientific method

• 术语：scientific method
• 印象：The very same approach that scientists use to understand the natural world is effective for studying the running time of programs:
  • Observe some feature of the nature world, generally with precise measurements.
  • Hypothesize a model that is consistent with the observation.
  • Predict events using the hypothesis.
  • Verify the predictions by making further observations.
  • Validate by repeating until the hypothesis and observation agree.
• 出处： 《Algorithms 4th》

术语卡——Mathematical models

• 术语： Mathematical models
• 印象：Knuth’s basic insight is simple: the total running of a program is determined by two primary factors:
  • The cost of executing each statement.
  • The frequency of execution of each statement.
• 例子： The former is a property of the computer, the Java compiler and the operating system; the latter is a property of the program and the input.
• 出处：Donald Knuth - Wikipedia

[ThomsonTang]

术语卡

• Tilde approximations
• Order-of-growth classifications

印象

• We use tilde approximations, where we throw away low-order terms that complicate formulas. We write ~f(N) to represent any function that when divided by f(N) approaches 1 as N grows. We write g(N) ~ f(N) to indicate that g(N)/f(N) approaches 1 as N grows.
• Most often, we work with tilde approximations of the form g(N) ~ a f(N) where f(N) = N^b log^c N and refer to f(N) as the The order of growth of g(N). We use just a few structural primitives (statements, conditions, loops, nesting, and method calls) to implement algorithms, so very often the order of growth of the cost is one of just a few functions of the problem size N.

例子

• Some functions with tilde approximation and order of growth:
• Common functions of the problem size N: