九至十二年级Computation计划中
Algorithms, correctness and efficiency
Searching and sorting, proving algorithms correct with loop invariants, counting steps, and comparing growth rates such as logarithmic, linear and quadratic time.
math.comp.algorithms-and-efficiency
本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。
前置知识
15 项必需的前置知识（一直追溯到底）
你将学会
- Implement linear search, binary search and a simple sort, and trace them on examples.
- Prove an algorithm correct using a loop invariant, for example binary search or Euclid's algorithm.
- Count the steps of simple algorithms and compare growth rates n, n log n and n².
定义
- A loop invariant is a statement that holds before the first iteration of a loop and is preserved by every iteration.
- The running time of an algorithm is the number of basic steps it takes, as a function of the size of its input.
定理
- Binary search on a sorted list of n items uses at most ⌊log₂ n⌋ + 1 comparisons.
- Every comparison-based sorting algorithm needs at least log₂(n!) comparisons in the worst case, which grows like n log n.
- An algorithm is correct if, for every valid input, it terminates and produces the specified output.
常见误解
- Thinking that testing on a few inputs proves an algorithm correct.
- Believing faster computers make algorithmic efficiency irrelevant.
通向
可选发现
- Computational complexity Some problems seem to require far more time than others; whether P equals NP is a famous open problem.
- ← Divisibility, Euclid's algorithm and unique factorisation
- ← Recurrences and generating functions
学习路径
延伸阅读
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms