Theta-Notation

定义 Definition

Theta-notation（Θ 记号）用于描述算法时间或空间复杂度的渐近紧确界：如果函数 (f(n)) 在足够大的 (n) 上同时被某个 (g(n)) 的常数倍上界与下界夹住，则记为
[ f(n)=\Theta(g(n)). ]
它表示 (f(n)) 与 (g(n)) 的增长速度在数量级上“同阶”，比只给上界的 Big-O 更精确。（在复杂度分析里也常写作“Big-Theta”。）

发音 Pronunciation (IPA)

/ˈθiːtə noʊˈteɪʃən/

例句 Examples

The running time of binary search is Θ(log n).
二分查找的运行时间是 Θ(log n)。

Because the inner loop runs n times for each of n iterations, the algorithm’s total work is Θ(n²) in the worst and average cases.
由于内层循环在每次外层迭代中运行 n 次，而外层也迭代 n 次，所以该算法在最坏与平均情况下的总工作量是 Θ(n²)。

词源 Etymology

Theta 来自希腊字母 Θ/θ（theta），在数学与计算机科学中常用希腊字母做符号记法；notation 意为“记号、表示法”。“Θ 记号”之所以用 theta，源于渐近分析中用不同符号区分上界（O）、下界（Ω）与紧确界（Θ）的传统。

相关词 Related Words

• Asymptotic
• Complexity
• Big-O
• Big-Omega
• Upper-Bound
• Lower-Bound
• Growth-Rate
• Tight-Bound

文学与名著用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）中系统使用 Θ 记号描述算法复杂度。
• The Art of Computer Programming（Donald E. Knuth）在渐近分析与算法讨论中广泛采用 Θ 等记号。
• Algorithms（Robert Sedgewick & Kevin Wayne）在性能分析章节中频繁出现 Θ 表达式。