时间复杂度

时间复杂度通过增长量级简单地对算法效率进行了刻画,是一类衡量算法优劣的指标之一

渐进符号

渐进记号是一类可以运用于函数的符号,例如我们可以将插入排序的复杂度刻画为一个函数 $T(n)=an^2+bn+c$ ,在渐进意义下,可以将其描述为 $Theta(n^2)$ ,在后文中我们将更加深刻的了解其含义
下文中, $:$ 意为“使得”, $exists$ 意为“存在”, $forall$ 意为“任意”

$Theta$ 记号

我们先来定义这个记号,对于一个给定的函数 $g(n)$ ,用 $Theta(g(n))$ 来表示一下函数的集合

即 $Theta$ 记号给出一个上界和下界,若函数 $f(n)$ 能够在 $c_1g(n)$ 与 $c_2g(n)$ 之间,则 $f(n)inTheta(g(n))$ ,表示 $f(n)$ 为 $Theta(g(n))$ 的一个成员,也可以用 $f(n)=Theta(g(n))$ 表示这个概念
$Theta$ 记号常用于描述均摊复杂度

$O$ 记号

这个记号被定义为

即 $O$ 记号给定函数一个渐进的上界,用于描述复杂度的最坏情况

$o$ 记号

常规 $O$ 记号描述的渐进上界可能不是渐进紧确的,如 $2n^2=O(n^2)$ 的紧确的但 $2n=O(n^2)$ 不是,于是定义 $o$ 记号为

$Omega$ 记号

这个记号被定义为

即 $O$ 记号给定函数一个渐进的下界,用于描述复杂度的最优情况

$omega$ 记号

与 $o$ 记号类似, $omega$ 记号也用于描述非紧确渐进的关系,定义为

渐进记号的性质

传递性

自反性

渐进复杂度的级别

在 $OI$ 中,我们通常使用 $O$ 记号来描述时间复杂度,通常的,可以分为一下几个等级,并标注了在 $1000ms$ 的时限内稳定通过的数据范围

主定理

$Master$ 定理,又名主定理,他的内容可以被描述为:我们将一个规模为 $n$ 的问题,通过分治得到 $a$ 个规模为 $frac{n}{b}$ 的子问题,每次分治带来额外的 $f(n)$ 的计算量,那么会得到以下关系式

我们定义一个 $p$ ,它满足

( 1 ) 当 $f(n)=O(n^c)$ 且 $c<p$ 时,有

( 2 ) 对于一个等式

若 $k>-1$ ,则

若 $k=-1$ ,则

若 $k<-1$ ,则

( 3 ) 对于

若 $c>p$ ,则

复杂度分析实例

例题一
已知某算法的计算时间表达式为

则该算法的时间复杂度为

根据主定理,易得

当 $k=0$ 时

所以该算法时间复杂度为

例题二
已知某算法的计算时间表达式为

则该算法的时间复杂度为

根据主定理,可得

因为

所以该算法的时间复杂度为

例题三
已知某算法的计算时间表达式为

则该算法的时间复杂度为

根据主定理,可得

因为

则该算法时间复杂度为