Big-Theta Notation 发音

定义 Definition

Big-Theta 记号（大 Theta 记号）用于描述算法时间或空间复杂度的渐近紧确界：当输入规模 \(n\) 足够大时，函数 \(f(n)\) 在常数因子范围内同时被上界和下界夹住。若 \(f(n) \in \Theta(g(n))\)，表示 \(f(n)\) 的增长速度与 \(g(n)\) 同阶（忽略常数与低阶项）。

发音 Pronunciation (IPA)

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

例句 Examples

The running time is big-Theta of n squared.
运行时间是 \( \Theta(n^2) \)。

Using big-Theta notation, we can state that the algorithm runs in \( \Theta(n \log n) \) time in the average case, which is more precise than only giving an upper bound.
用 Big-Theta 记号，我们可以说明该算法在平均情况下运行时间为 \( \Theta(n \log n) \)，这比只给出上界更精确。

词源 Etymology

“Theta”来自希腊字母 Θ/θ（theta）。在算法分析中，人们用希腊字母来命名一组“增长率分类”的记号体系：如 Big-O（上界）、Big-Ω（下界）与 Big-Θ（紧确界）。其中 Big-Theta 强调“上下都卡住”，因此表达的是同阶而非仅“不会超过”。

相关词 Related Words

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

文学与经典作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常简称 CLRS）——系统讲解 \(O\)、\(\Omega\)、\(\Theta\) 及其在算法分析中的用法。
• The Art of Computer Programming（Donald E. Knuth）——大量使用渐近记号讨论算法与数值增长。
• Algorithms（Robert Sedgewick & Kevin Wayne）——在排序、查找等主题中用 Big-Theta 给出复杂度的同阶结论。
• Concrete Mathematics（Graham, Knuth, Patashnik）——在渐近分析与数学推导中涉及相关记号与思想。