Big-Theta

定义 Definition

Big-Theta（Θ 记号）是算法分析中的渐近符号，表示函数的紧确界：如果存在正常数 \(c_1, c_2, n_0\)，使得对所有 \(n \ge n_0\)，都有
\[ c_1 g(n) \le f(n) \le c_2 g(n), \] 则记作 \(f(n)=\Theta(g(n))\)。它常用来描述算法的时间复杂度或空间复杂度在数量级上“既不更快也不更慢”的增长趋势。（另有 Big-O、Big-Ω 等相关记号。）

发音 Pronunciation (IPA)

/b θet/

例句 Examples

For merge sort, the running time is Big-Theta of n log n.
对归并排序来说，其运行时间是 \( \Theta(n \log n) \)。

If the inner loop runs n times and the outer loop runs n times, the total work is Big-Theta of n squared, assuming constant-time operations.
如果内层循环运行 \(n\) 次、外层循环也运行 \(n\) 次，并假设每次操作是常数时间，那么总工作量是 \( \Theta(n^2) \)。

词源 Etymology

“Big-Theta”来自希腊字母 Theta（Θ）。在计算机科学的渐近分析中，人们借用 Θ 来表示“上下界同阶”的紧确增长级别；“Big-”这一说法与 Big-O、Big-Ω 等同一命名传统，用来指代一类渐近记号。

相关词 Related Words

• Asymptotic
• Big-O
• Big-Omega
• Complexity
• Growth
• Runtime
• Theta

文学/经典著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：系统使用 \(O\)、\(\Omega\)、\(\Theta\) 描述算法复杂度。
• The Art of Computer Programming（Donald Knuth）：在算法与分析章节中使用渐近记号（包括 \(\Theta\)）讨论增长率。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在复杂度分析与排序/查找等主题中频繁出现 \(\Theta\) 记号。