aiwiki.page
中文
计算机 / 算法与理论 / big-theta-notation

大Θ记号

大Θ记号描述函数增长的渐近紧确界,忽略常数因子及输入规模较小时的行为。

20 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
计算机科学算法函数(数学)大 O 记号大Ω记号多项式计算复杂性时间复杂度大Θ记号

大Θ记号写作 Θ\Theta,用于描述当自变量足够大时,增长速率仅相差正常数因子的函数。在计算机科学中,它用于表示算法所需资源的紧确界,尤其是运行时间和内存。例如,T(n)=Θ(n2)T(n)=\Theta(n^2) 表示,输入规模超过某个阈值后,T(n)T(n) 的上界和下界都可由 n2n^2 的正常数倍给出。它既不指定确切的运行时间,也不要求比值 T(n)/n2T(n)/n^2 趋于某个极限。

形式化定义

设 ff 和 gg 是以正整数 nn 为自变量的实值函数,且当 nn 足够大时,两个函数均非负。集合 Θ(g(n))\Theta(g(n)) 由满足以下条件的所有函数 ff 组成:存在常数 c1>0c_1>0、c2>0c_2>0 和 n0n_0,使得

0≤c1g(n)≤f(n)≤c2g(n)for every n≥n0.0\leq c_1g(n)\leq f(n)\leq c_2g(n) \qquad\text{for every }n\geq n_0.

这些常数必须与 nn 无关,但可以取决于所比较的具体函数。

左侧的不等式保证 ff 相对于 gg 不会变得任意小;右侧的不等式保证它相对于 gg 不会变得任意大。两个不等式必须对所有足够大的自变量值成立,而不只是对无穷多个自变量值成立。

严格来说,这一记号表达的是一个函数属于某个集合:

f∈Θ(g).f\in\Theta(g).

通常采用的形式

f(n)=Θ(g(n))f(n)=\Theta(g(n))

以等号作为这种隶属关系的简写,不应将其理解为函数与集合之间的普通相等关系。

对于可能取负值的函数,也会采用绝对值形式的定义:

c1∣g(n)∣≤∣f(n)∣≤c2∣g(n)∣c_1|g(n)|\leq |f(n)|\leq c_2|g(n)|

该不等式需对所有足够大的 nn 成立。在算法分析中,资源计数通常非负,因此非负形式的定义一般已经足够。

与其他渐近记号的关系

大Θ记号属于渐近分析的范畴。渐近分析研究极限行为,而非每个自变量值处的精确取值。

定义中的两个界分别对应另外两种记号:

  • 大O记号,f(n)=O(g(n))f(n)=O(g(n)),给出渐近上界。
  • 大Ω记号,f(n)=Ω(g(n))f(n)=\Omega(g(n)),给出渐近下界。

在相同的非负性假设下,

f(n)=Θ(g(n))⟺f(n)=O(g(n)) and f(n)=Ω(g(n)).f(n)=\Theta(g(n)) \quad\Longleftrightarrow\quad f(n)=O(g(n)) \ \text{and}\ f(n)=\Omega(g(n)).

因此,Θ界是渐近紧确的:它的上界和下界仅相差常数因子。

例如,n2=O(n3)n^2=O(n^3) 是正确的,但这个界并不紧确。n2=Θ(n3)n^2=\Theta(n^3) 则是错误的,因为不存在 n3n^3 的某个正常数倍,使其对所有足够大的 nn 都不超过 n2n^2。

Θ关系与渐近等价

渐近等价写作 f(n)∼g(n)f(n)\sim g(n),通常表示

lim⁡n→∞f(n)g(n)=1.\lim_{n\to\infty}\frac{f(n)}{g(n)}=1.

这是比Θ关系更强的条件。例如,

3n2∼3n2+n,3n^2\sim 3n^2+n,

但 3n2≁n23n^2\not\sim n^2,尽管 3n2=Θ(n2)3n^2=\Theta(n^2)。

更一般地,若

lim⁡n→∞f(n)g(n)=L,0<L<∞,\lim_{n\to\infty}\frac{f(n)}{g(n)}=L, \qquad 0<L<\infty,

则 f(n)=Θ(g(n))f(n)=\Theta(g(n))。不过,这样的极限存在只是充分条件,而非必要条件。两者的比值可以在正常数之间振荡。

示例与证明方法

多项式增长

考虑

f(n)=3n2+5n+7.f(n)=3n^2+5n+7.

当 n≥1n\geq1 时,n≤n2n\leq n^2 和 1≤n21\leq n^2 均成立,因此

3n2≤3n2+5n+7≤15n2.3n^2\leq 3n^2+5n+7\leq15n^2.

取 c1=3c_1=3、c2=15c_2=15、n0=1n_0=1,即可证明

3n2+5n+7=Θ(n2).3n^2+5n+7=\Theta(n^2).

一般来说,首项系数为正的多项式与其最高次项具有相同的渐近阶。低次项和固定的乘法常数不会改变它所属的Θ类。

重复操作的计数

假设某个算法在外层循环的第 ii 次迭代中,将一个常数时间操作执行 ii 次,其中 i=1,…,ni=1,\ldots,n。操作总次数为

∑i=1ni=n(n+1)2=Θ(n2).\sum_{i=1}^{n}i=\frac{n(n+1)}{2}=\Theta(n^2).

这说明,即使内层循环在各次外层迭代中的执行次数不同,嵌套循环仍可呈现平方级增长。关键在于操作的总次数。

对数增长

对于固定的底数 a,b>1a,b>1,

log⁡an=log⁡bnlog⁡ba.\log_a n=\frac{\log_b n}{\log_b a}.

由于换底因子是正常数,

log⁡an=Θ(log⁡bn).\log_a n=\Theta(\log_b n).

因此,在资源用量的渐近界中,常常省略对数的底数。这种简化不适用于指数函数的底数:2n2^n 和 3n3^n 并不具有Θ等价关系。

振荡

对于正整数 nn,令

f(n)=n(2+(−1)n).f(n)=n\bigl(2+(-1)^n\bigr).

其值为 nn 或 3n3n,因此

n≤f(n)≤3n.n\leq f(n)\leq3n.

所以 f(n)=Θ(n)f(n)=\Theta(n),尽管 f(n)/nf(n)/n 没有极限。Θ记号描述的是相对增长幅度有界,而不是比值收敛到某个固定值。

在算法分析中的应用

在计算复杂性研究中,Θ记号常用于描述作为输入规模函数的时间复杂度和空间复杂度。

典型示例如下:

算法或操作 紧确界 假设条件
按索引访问[[array-data-structure 数组(数据结构)]]中的元素 Θ(1)\Theta(1)
[[binary-search 二分查找]] 最坏情况下的比较次数为 Θ(log⁡n)\Theta(\log n)
[[merge-sort 归并排序]] 最坏情况下的时间为 Θ(nlog⁡n)\Theta(n\log n)
[[insertion-sort 插入排序]] 最坏情况下的时间为 Θ(n2)\Theta(n^2)

所考察的资源和采用的计算模型都很重要。对固定长度机器字进行的算术运算可以视为常数时间操作,而对任意大整数进行的算术运算通常取决于所涉及的位数。

最坏情况、平均情况与摊还代价

Θ记号本身并不指明所分析的是哪些输入或执行过程。

若算法在输入 xx 上的运行时间为 T(x)T(x),则可将最坏情况函数定义为

Tworst(n)=max⁡∣x∣=nT(x).T_{\mathrm{worst}}(n)=\max_{|x|=n}T(x).

Tworst(n)=Θ(g(n))T_{\mathrm{worst}}(n)=\Theta(g(n)) 给出的是这一最大值的紧确界,并不意味着每个规模为 nn 的输入都需要 Θ(g(n))\Theta(g(n)) 的时间。

平均情况界针对的是指定输入分布下的期望值。对于随机化算法,期望界也可能针对算法内部的随机选择。这是两种不同的随机性来源,必须加以明确。

在摊还分析中,界所描述的是一串操作的代价,而不一定是每个操作单独的代价。对于容量按几何级数增长的动态数组,如果扩容时需要复制已有的 nn 个元素,那么一次追加操作可能耗时 Θ(n)\Theta(n),但每次追加的摊还代价仍为 Θ(1)\Theta(1)。

代数性质

对于自变量充分大时取正值的函数,属于同一Θ类是一种等价关系:

  • 自反性:f=Θ(f)f=\Theta(f)。
  • **对称性:**若 f=Θ(g)f=\Theta(g),则 g=Θ(f)g=\Theta(f)。
  • **传递性:**若 f=Θ(g)f=\Theta(g) 且 g=Θ(h)g=\Theta(h),则 f=Θ(h)f=\Theta(h)。

以下是一些实用的计算规则。

对于正常数 aa,

af=Θ(f).af=\Theta(f).

对于自变量充分大时非负的 ff 和 gg,

f+g=Θ(max⁡{f,g}).f+g=\Theta(\max\{f,g\}).

若 f1=Θ(g1)f_1=\Theta(g_1) 且 f2=Θ(g2)f_2=\Theta(g_2),并且所有函数在自变量充分大时均为正,则

f1f2=Θ(g1g2),f_1f_2=\Theta(g_1g_2),

且

f1f2=Θ ⁣(g1g2).\frac{f_1}{f_2}=\Theta\!\left(\frac{g_1}{g_2}\right).

减法需要谨慎处理,因为相消可能消去主导项。仅知道 f=Θ(n2)f=\Theta(n^2) 和 g=Θ(n2)g=\Theta(n^2),无法确定 f−gf-g 的阶。例如,若 f(n)=n2+nf(n)=n^2+n 且 g(n)=n2g(n)=n^2,则 f(n)−g(n)=nf(n)-g(n)=n。

适用范围与局限

Θ记号有意忽略常数因子,以及自变量较小时有限范围内的行为。即使两种实现属于同一Θ类,其实际运行时间也可能因内存访问模式、硬件、编译器优化或较大的隐含常数而相差甚远。在实际关注的某个输入规模范围内,渐近增长更快、因而渐近性能较差的算法,反而可能表现更好。

Θ界也不能证明算法是最优的。运行时间为 Θ(n2)\Theta(n^2) 的算法,只是其自身的增长速度得到了紧确描述;要证明最优性,还需要在指定模型中,为解决该问题的所有算法建立适当的下界。

必须谨慎定义输入规模。若一个整数的数值为 NN,则其二进制表示的长度为 Θ(log⁡N)\Theta(\log N)。因此,相对于 NN 呈线性增长的运行时间,相对于该表示的长度却呈指数增长。

对于多变量函数,还必须明确其定义域和量词。在 Θ(n+m)\Theta(n+m) 这样的界中,乘法常数必须在所声明的 nn 和 mm 的整个取值范围内统一适用。将一个参数视为固定值,与允许两个参数独立变化,可能会得到不同的结论。