Time Complexity （时间复杂度）

There are different measurements of the speed of any given algorithm. Given an input size of N, they can be described as follows:

不同的算法，速度也会不一样。对于一个输入大小 N，它们可以如下描述：

Name	Speed	Description	Formula	Example
factorial time	slower	takes an amount of time proportional to N raised to the Nth power	N!	Brute force solution to Traveling Salesman Problem
exponential time	slow	takes an amount of time proportional to a constant raised to the Nth power	KN	Brute force solution to Rubik's Cube
polynomial time	fast	takes an amount of time proportional to N raised to some constant power	NK	Comparison sorts (bubble, insertion, selection sort)
linearithmic time	faster	takes an amount of time between linear and polynomial	N * log(N)	The Linear logarithmic sorts (quicksort, heapsort, mergesort)
linear time	even faster	takes an amount of time directly proportional to N	K * N	Iterating through an array
logarithmic time	much faster	takes an amount of time proportional to the logarithm of N	K * log(N)	Binary Search
constant time	fastest	takes a fixed amount of time, no matter how large the input is	K	Array index lookup

名称	速度	描述	公式	例子
factorial time	更慢	花费的时间与 N 的阶成成正比	N!	Brute force solution to Traveling Salesman Problem
exponential time	慢	花费的时间与某个常数的 N 次幂成正比	KN	Brute force solution to Rubik's Cube
polynomial time	快	花费的时间与 N 的某个常数幂成正比	NK	比较排序算法 (bubble, insertion, selection sort)
linearithmic time	更快	花费的时间介于 linear time 和 polynomial time 之间	N * log(N)	线性排序算法 (quicksort, heapsort, mergesort)
linear time	很快	花费的时间与 N 直接成正比	K * N	数组迭代
logarithmic time	非常快	花费的时间与 N 的对数成正比	K * log(N)	二分搜索
constant time	最快	花费因定时间，与输入大小无关	K	数组索引查询
更慢<慢<快<更快<很快<非常快<最快

Complexity Analysis （复杂度分析）

A given operation can have different time complexities with different orders/sets of input. The different methods of time complexity analysis are as follows:

一个给定的操作，如果输入的顺序/集合不同，那么它的时间复杂度也会不同。下面是一些时间复杂度分析的方法：

Name	Description	Example
best-case	A case where the operation executes as fast as it possibly can	Bubblesort has a best-case time complexity of N.
average-case	A case where the operation executes in a time comparable to the majority of possible cases	Quicksort has an average-case time complexity of N * log(N)
worst-case	A case where the operation executes as slowly as it possibly can	Quicksort has a worst-case time complexity of N2
amortized worst-case	The average worst-case taken over an infinite number of inputs	vector::push_back() has an amortized worst-case time complexity of K (constant time)

名称	描述	例子
best-case	操作可以尽快执行的情况	Bubblesort 有一个 N 时间复杂度的 best-case
average-case	大部分可能的操作所在的一个执行时间范围的情况	Quicksort 有一个 N * log(N) 时间复杂度的的 average-case
worst-case	操作会尽量慢执行的情况	Quicksort 有一个 N2 时间复杂度的 worst-case
amortized worst-case	无限次输入会发生 average worst-case 的情况	vector::push_back() 有一个 K (constant time) 时间复杂度的 amortized worst-case

Choosing the right algorithm depends upon which cases you expect your application to encounter. For example, an application that must protect itself from malicious input will avoid naive implementations of quicksort, which has a worst-case time complexity of N² despite having one of the fastest average-case time complexities compared to all other sorts.

选择正确的算法依赖于你的应用遇到的具体情况。例如，某个应用必须阻止无效输入来避免 quicksort 运行，因为它有一个 N² 时间复杂度的 worst-case，尽管相对其他排序，它的 average-case 时间复杂度是最快中的一个。