数据结构与算法分析数学和文本部份
星海
posted @ 2011年11月16日 12:39
in 数据结构与算法分析
, 1289 阅读
一，归纳法证明：
1，证明基准情形(base case)。就是确定定理对于某个小的（通常是退化的）值的正确性。
2，归纳假设(inductive hypothesis)。假设定理对直到某个有限数k的所有情况都是成立的，然后使用这个假设证明定理对下一个值(k + 1)也是成立的。
二，递归：
1，基准情形(base case)。
2，不断推进(make progress)。对于需要递归求解的情形，递归调用必须总能够朝着产生基准情形的方向推进。
3，设计法则(design rule)。假设所有的递归调用都能运行。
4，合成效益法则(compound interest rule）。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。
三，
O(N)的一些排序算法：
基数排序(radix sort)，也称卡式排序(card sort)
桶式排序(bucket sort)，该排序运行时间为O(P(N+B))，P是排序趟数，N是元素个数，B是桶数。
评论 (0)