Theta Notation

Definition / 定义

Θ（Theta）记号：算法分析中表示渐近紧确界的符号，用来描述当输入规模 (n) 足够大时，某个函数（如运行时间或空间）与另一函数在增长速度上“同阶”。
若 (f(n)=\Theta(g(n)))，表示存在正常数 (c_1,c_2,n_0)，使得对所有 (n\ge n_0)，有 (c_1g(n)\le f(n)\le c_2g(n))。

Pronunciation / 发音

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

Examples / 例句

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

Although the constants differ, both implementations have Θ(n log n) time complexity in the average case.
尽管常数不同，这两种实现的平均时间复杂度都是 Θ(n log n)。

Etymology / 词源

“Theta”来自希腊字母 Θ（theta）；“notation”意为“记号/表示法”。在计算机科学的渐近分析中，Θ 用来表示比 O（大 O，上界） 更严格的量级关系：它同时给出上界与下界，因此称为“紧确界（tight bound）”。

Related Words / 相关词

• Asymptotic
• Big O
• Big Omega
• Complexity
• Lower Bound
• Upper Bound
• Order Of Growth

Literary Works / 文学作品

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：用 Θ 记号系统讲解算法时间/空间复杂度。
• The Art of Computer Programming（Donald E. Knuth）：在算法与数学分析语境中讨论渐近增长与记号体系。
• Concrete Mathematics（Graham, Knuth, Patashnik）：涵盖与渐近分析相关的数学工具与记号用法。