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ɪɡ ˈθeɪtə/

例句 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) 记号。