Time Complexity

时间复杂度（Time Complexity） 是用于衡量算法随着数据规模而耗时增长的趋势。

不同算法在不同平台、架构的机器上运行速度会有差异，而实际测量又麻烦，所以我们通常衡量算法所需的基本操作数量。而 时间复杂度 就是不同输入规模下，算法所需的基本操作数量的斜率。

渐进符号

渐进符号是函数的阶的规范描述。用于表示算法时间复杂度的阶数、增长率或线性复杂度（linear complexity）。简单来说，渐进符号忽略了一个函数中增长较慢的部分以及各项的系数（在时间复杂度相关分析中，系数一般被称作「常数」），而保留了可以用来表明该函数增长趋势的重要部分。^[1]

算法研究中的常用渐进符号如下 ^[2]：

符号	英文名	描述	等效
$O$	Big Omicron	描述算法渐进上界	`<=`
$o$	Omicron	描述算法严格渐进上界	`<`
$Ω$	Big Omega	描述算法渐进下界	`>=`
$ω$	Omega	描述算法严格渐进下界	`>`
$Θ$	Big Theta	描述算法严格界限（渐进上下界）	`=`

最好、最差和平均时间复杂度，与

O

、

Ω

和

Θ

有什么关系？

没有关系。虽然为了简单起见，人们通常：

$O$ 表示最差情况
$Ω$ 表示最好情况
$Θ$ 表示平均情况

但每个渐进符号都可已有自己的最好、最差和平均情况。比如：

插入排序最差时间复杂度最多是 $O (n^{2})$
插入排序最差时间复杂度最少是 $Ω (n)$
插入排序最差时间复杂度就是 $Θ (n^{2})$

通常研究算法时间复杂度时会使用 $O$ 符号（ $O$ 实际上是希腊字母 Omicron 的缩写），因为我们关注的通常是程序用时的上界，而不关心其用时的下界。

$O$ 分布

参考链接：Know Thy Complexities!

What is Big O Notation?

Big O is a notation for measuring the complexity of an algorithm. Big O notation mathematically describes the complexity of an algorithm in terms of time and space. We don’t measure the speed of an algorithm in seconds (or minutes!). We measure the rate of growth of an algorithm in the number of operations it takes to complete.

The O is actually the Greek character Omicron and is shorthand for “Order of”. So, if we’re discussing an algorithm with O(n), we say its order of, or rate of growth, is n, or linear complexity.^[3]

渐进符号

O 分布

$O$ 分布