时间复杂度 - Time Complexity

• 为什么数据结构也有期中
• , , ,

Notations

大O

if there are positive constants and such that when

简单理解为 无限大时 是 的上界 (渐近上界)

大Ω

if there are positive constants and such that when

简单理解为 无限大时 是 的下界 (渐近下界)

大Θ

if and only if and

简单理解为 无限大时 相等 (渐近紧确界)

小o

if, for all positive constants , there exists an such that when . Less formally, if and

简单理解为 无限大时 严格大于 （非渐近紧确上界）

Proof by induction

通常采用数学归纳法证明，我们只需要找出一个 以及对应的 即可。证伪时，我们采用反证法，通常证明极限情况下（） 不存在 （）

证明

例如证明 is
首先观察得 ，我们令
随后由 Inductive Hypothesis： such that
那么对于 n+1 的情况


因为 , 所以
因此假设对于 成立，即

证伪

另一个证伪的例子是 is not
我们假设 成立

那么当 时

因为极限不存在，因此 不存在，与假设矛盾，所以命题不成立，即