大Θ记号写作 Θ,用于描述当自变量足够大时,增长速率仅相差正常数因子的函数。在计算机科学中,它用于表示算法所需资源的紧确界,尤其是运行时间和内存。例如,T(n)=Θ(n2) 表示,输入规模超过某个阈值后,T(n) 的上界和下界都可由 n2 的正常数倍给出。它既不指定确切的运行时间,也不要求比值 T(n)/n2 趋于某个极限。
形式化定义
设 f 和 g 是以正整数 n 为自变量的实值函数,且当 n 足够大时,两个函数均非负。集合 Θ(g(n)) 由满足以下条件的所有函数 f 组成:存在常数 c1>0、c2>0 和 n0,使得
0≤c1g(n)≤f(n)≤c2g(n)for every n≥n0.
这些常数必须与 n 无关,但可以取决于所比较的具体函数。
左侧的不等式保证 f 相对于 g 不会变得任意小;右侧的不等式保证它相对于 g 不会变得任意大。两个不等式必须对所有足够大的自变量值成立,而不只是对无穷多个自变量值成立。
严格来说,这一记号表达的是一个函数属于某个集合:
f∈Θ(g).
通常采用的形式
f(n)=Θ(g(n))
以等号作为这种隶属关系的简写,不应将其理解为函数与集合之间的普通相等关系。
对于可能取负值的函数,也会采用绝对值形式的定义:
c1∣g(n)∣≤∣f(n)∣≤c2∣g(n)∣
该不等式需对所有足够大的 n 成立。在算法分析中,资源计数通常非负,因此非负形式的定义一般已经足够。
与其他渐近记号的关系
大Θ记号属于渐近分析的范畴。渐近分析研究极限行为,而非每个自变量值处的精确取值。
定义中的两个界分别对应另外两种记号:
- 大O记号,f(n)=O(g(n)),给出渐近上界。
- 大Ω记号,f(n)=Ω(g(n)),给出渐近下界。
在相同的非负性假设下,
f(n)=Θ(g(n))⟺f(n)=O(g(n)) and f(n)=Ω(g(n)).
因此,Θ界是渐近紧确的:它的上界和下界仅相差常数因子。
例如,n2=O(n3) 是正确的,但这个界并不紧确。n2=Θ(n3) 则是错误的,因为不存在 n3 的某个正常数倍,使其对所有足够大的 n 都不超过 n2。
Θ关系与渐近等价
渐近等价写作 f(n)∼g(n),通常表示
n→∞limg(n)f(n)=1.
这是比Θ关系更强的条件。例如,
3n2∼3n2+n,
但 3n2∼n2,尽管 3n2=Θ(n2)。
更一般地,若
n→∞limg(n)f(n)=L,0<L<∞,
则 f(n)=Θ(g(n))。不过,这样的极限存在只是充分条件,而非必要条件。两者的比值可以在正常数之间振荡。
示例与证明方法
多项式增长
考虑
f(n)=3n2+5n+7.
当 n≥1 时,n≤n2 和 1≤n2 均成立,因此
3n2≤3n2+5n+7≤15n2.
取 c1=3、c2=15、n0=1,即可证明
3n2+5n+7=Θ(n2).
一般来说,首项系数为正的多项式与其最高次项具有相同的渐近阶。低次项和固定的乘法常数不会改变它所属的Θ类。
重复操作的计数
假设某个算法在外层循环的第 i 次迭代中,将一个常数时间操作执行 i 次,其中 i=1,…,n。操作总次数为
i=1∑ni=2n(n+1)=Θ(n2).
这说明,即使内层循环在各次外层迭代中的执行次数不同,嵌套循环仍可呈现平方级增长。关键在于操作的总次数。
对数增长
对于固定的底数 a,b>1,
logan=logbalogbn.
由于换底因子是正常数,
logan=Θ(logbn).
因此,在资源用量的渐近界中,常常省略对数的底数。这种简化不适用于指数函数的底数:2n 和 3n 并不具有Θ等价关系。
振荡
对于正整数 n,令
f(n)=n(2+(−1)n).
其值为 n 或 3n,因此
n≤f(n)≤3n.
所以 f(n)=Θ(n),尽管 f(n)/n 没有极限。Θ记号描述的是相对增长幅度有界,而不是比值收敛到某个固定值。
在算法分析中的应用
在计算复杂性研究中,Θ记号常用于描述作为输入规模函数的时间复杂度和空间复杂度。
典型示例如下:
| 算法或操作 |
紧确界 |
假设条件 |
| 按索引访问[[array-data-structure |
数组(数据结构)]]中的元素 |
Θ(1) |
| [[binary-search |
二分查找]] |
最坏情况下的比较次数为 Θ(logn) |
| [[merge-sort |
归并排序]] |
最坏情况下的时间为 Θ(nlogn) |
| [[insertion-sort |
插入排序]] |
最坏情况下的时间为 Θ(n2) |
所考察的资源和采用的计算模型都很重要。对固定长度机器字进行的算术运算可以视为常数时间操作,而对任意大整数进行的算术运算通常取决于所涉及的位数。
最坏情况、平均情况与摊还代价
Θ记号本身并不指明所分析的是哪些输入或执行过程。
若算法在输入 x 上的运行时间为 T(x),则可将最坏情况函数定义为
Tworst(n)=∣x∣=nmaxT(x).
Tworst(n)=Θ(g(n)) 给出的是这一最大值的紧确界,并不意味着每个规模为 n 的输入都需要 Θ(g(n)) 的时间。
平均情况界针对的是指定输入分布下的期望值。对于随机化算法,期望界也可能针对算法内部的随机选择。这是两种不同的随机性来源,必须加以明确。
在摊还分析中,界所描述的是一串操作的代价,而不一定是每个操作单独的代价。对于容量按几何级数增长的动态数组,如果扩容时需要复制已有的 n 个元素,那么一次追加操作可能耗时 Θ(n),但每次追加的摊还代价仍为 Θ(1)。
代数性质
对于自变量充分大时取正值的函数,属于同一Θ类是一种等价关系:
- 自反性:f=Θ(f)。
- **对称性:**若 f=Θ(g),则 g=Θ(f)。
- **传递性:**若 f=Θ(g) 且 g=Θ(h),则 f=Θ(h)。
以下是一些实用的计算规则。
对于正常数 a,
af=Θ(f).
对于自变量充分大时非负的 f 和 g,
f+g=Θ(max{f,g}).
若 f1=Θ(g1) 且 f2=Θ(g2),并且所有函数在自变量充分大时均为正,则
f1f2=Θ(g1g2),
且
f2f1=Θ(g2g1).
减法需要谨慎处理,因为相消可能消去主导项。仅知道 f=Θ(n2) 和 g=Θ(n2),无法确定 f−g 的阶。例如,若 f(n)=n2+n 且 g(n)=n2,则 f(n)−g(n)=n。
适用范围与局限
Θ记号有意忽略常数因子,以及自变量较小时有限范围内的行为。即使两种实现属于同一Θ类,其实际运行时间也可能因内存访问模式、硬件、编译器优化或较大的隐含常数而相差甚远。在实际关注的某个输入规模范围内,渐近增长更快、因而渐近性能较差的算法,反而可能表现更好。
Θ界也不能证明算法是最优的。运行时间为 Θ(n2) 的算法,只是其自身的增长速度得到了紧确描述;要证明最优性,还需要在指定模型中,为解决该问题的所有算法建立适当的下界。
必须谨慎定义输入规模。若一个整数的数值为 N,则其二进制表示的长度为 Θ(logN)。因此,相对于 N 呈线性增长的运行时间,相对于该表示的长度却呈指数增长。
对于多变量函数,还必须明确其定义域和量词。在 Θ(n+m) 这样的界中,乘法常数必须在所声明的 n 和 m 的整个取值范围内统一适用。将一个参数视为固定值,与允许两个参数独立变化,可能会得到不同的结论。