复杂度 Big-O Θ Ω little-o ω

前言

在描述复杂度时，通常采用大O符号作为表示方式。

然而，在一些其他文献中，读者或许也曾经接触过Θ、Ω、o、ω等符号的使用。

这些符号具体代表何种含义呢？

接下来，本节将对这一问题进行详细阐述。

读音

接下来我们对一些常见字母的发音进行更正：

O，发音为/əʊ/，代表大写Oh

o，同样发音为/əʊ/，对应小写oh

Θ，发音为/ˈθiːtə/，即theta

Ω，发音为/oʊˈmeɡə/，表示大写Omega

ω，发音为/oʊˈmeɡə/，对应小写omega

这些读音是否与老师教授的内容存在差异呢^^

数学理论解析

Θ

Θ描述了一种确切的渐近特性，具体该如何表述呢？

通过函数形式进行表达：

    对于f(n)，存在正数n0、c1、c2，使得当 n>=n0 时，始终存在 0 <= c1*g(n) <= f(n) <= c2*g(n)，则我们可以用 f(n)=Θ(g(n))表示。
    
    

采用图形化方式予以呈现：

Θ同时确立了上限与下限，f(n)处于这两个界限之间，并且包含等号。

例如，当f