1. 算法的定义 当设计一个算法时，需要考虑下下面三点： * 明确要实现的目标是什么 * 分析它的正确性 * 分析它的效率(时间，内存消耗) 2. 算法度量Big O "On the basis of the issues discussed here, I propose that members of SIGACT, and editors of computer science and mathematics journals, adopt O, Ω, and Θ notations as defined above, unless a better alternative can be found reasonable soon." -D.E. Knuth, "Big Omicron and Big Omega and Big Theta", SIGACT News, 1976. Reprinted in "Selected Papers on Analysis of Algorithms." * T(n) = O(f(n)) (读作big-oh)，表示T(n)的增长率渐近的小于或者等于f(n)的增长率。 * T(n) = Ω(f(n)) (读作omega)，表示T(n)的增长率渐近的大于或者等于f(n)的增长率。 * T(n) = Θ(f(n)) (读作theta)，表示T(n)的增长率渐近的等于f(n)的增长率。 因此，如果T(n) = n^2 + 5n，则下面的判断为true. T(n) = Ω(n) T(n) = Θ(n^2) T(n) = O(n^3) 简单来说，这三个符号表示： Big O --- 算法最坏情况的度量； Big Omega - 算法最好情况的度量； Big Theta - 算法的区间，不会好于某某，也不会坏于某某。 3. 数据结构 为何数据结构这么重要？因为我们需要优化数据使得能更快的访问以及使用。数据结构有多种形式，因为需要支持不同的操作。换言之，每种数据结构适用于不同类型的任务。常用的数据结构类型如下： 链表(Linked Lists) 栈(Stacks)和队列(Queues) 二叉搜索树(Binary Search Trees) B树(B-Trees) 红黑树(Red-Black Trees) 平衡二叉树(AVL Trees) 哈希表(Hash Tables) 堆(Heap) 后面的几个章节，会分别对每种类型进行说明。 4. 排序算法 n: 需要排序的元素个数 k: 每个key的大小 d: 位数大小 以上的这几种排序算法，会在后续的文章中逐渐说明。
京公网安备 11010802041100号