Acwing算法基础课：杂项

时间复杂度：渐近分析

见《算法导论》第三章

算法运行时间影响因素

算法运行时间受多因素的影响：

机器性能（指令执行速度 = IPC * 时钟频率）、编程语言效率、数据规模、数据特点，以及算法本身。

对算法竞赛来说，如果不考虑卡常，主要考虑后三者。

根据数据特点分

考虑数据的不同特点，可以考虑最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度。

渐近记号

只考虑数据规模和算法本身，可以用渐近记法来描述：

公式	名称	通俗理解
$T(n) = O(f(n))$	渐近上界	$f(n)>=T(n)$
$T(n) = \Omega(f(n))$	渐近下界	$T(n)>=f(n)$
$T(n) = \Theta(f(n))$	渐近确界	$T(n)=f(n)$
$T(n) = o(f(n))$	非渐近上界	$f(n)>T(n)$（比值极限为0）
$T(n) = \omega(f(n))$	非渐近下界	$T(n)>f(n)$（比值极限为0）

从定义看，$T(n) = O(f(n))$：$\exists c, n_0 …$；$T(n) = o(f(n))$：$\forall c, \exists n_0 …$：后者条件比前者更强。

前者允许$T(n)$和$f(n)$同阶，而后者不允许，因此一般更习惯用前者描述算法的时间复杂度。

一般地，可用最坏情况下的渐近上界来描述一个算法的最坏情况。

常见函数阶的关系

$O(1)<O(\log n)<O(n)<O(n \log n)<O ( n^2 ) < O ( 2^n ) < O ( n ! ) < O ( n^n )$