3.1 渐进记号

渐进记号 Θ, O, o, Ω, ω

Θ记号 渐进紧确界 =

O记号 渐进上界 ≤

Ω记号 渐进下界 ≥

o记号 非渐进紧确的上界 ＜

ω记号 非渐进紧确的下界 ＞

比较各种函数

传递性

自反性

对称性

转置对称性

类比两个函数f与g的渐进比较和两个实数a与b的比较

定理 3.1

3.2 标准记号与常用函数

单调性 【单调递增/减 严格递增/减】

向下取整与向上取整

模运算

多项式

指数

阶乘

多重函数

多重对数

斐波那契数

思考题

3-2 相对渐进增长

Indicate for each pair of expressions (A,B) in the table below, whether A is O, o, Ω, ω, or Θ of B. Assume that k≥1, ϵ>0, and c>1 are constants. Your answer should be in the form of the table with "yes" or "no" written in each box.

Solution

3-3 根据渐进增长率排序

Solution

指数

多项式

对数

3-4 渐进记号的性质

Let f(n) and g(n)by asymptotically positive functions. Prove or disprove each of the following conjectures.

Solution

a disaprove

b disprove

c prove

d disprove

3-？

考虑通过首先找到A的最大元素并将它与[n]中的元素进行交换来排序存储在数组A中的N个数。然后找到A的第二大元素，并将其与A[n-1]交换。以这种方式对A的所有n个元素继续。为此算法编写伪代码，并回答以下问题：

这个算法保持什么循环不变量？用渐近表示法给出选择排序的最佳和最坏情况运行时间。

Solution