算法 cheatsheet

T(n) = O(f(n))

• T(n) 代码执行的时间
• n 数据规模的大小
• f(n) 每行代码执行的次数总和

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

• 只关注循环执行次数最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

O(1)

只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度我们都记作O(1)

O(logn)、O(nlogn)

通过计算执行次数可以得出，例如：

i = 1
while (i < n) {
    i = i * 2
}
// 2 ** 0 -> 2 ** 1 ... 2 ** x

由 2 ** x = n 得 x = log2n，故为O(logn)的时间复杂度

平均情况时间复杂度

找到无序数组中x的位置

由于x的可能再1~n任一位置或不存在，由 n+1种可能：

 (1 + 2 + ... + n + n)       (n + 3) n     
---------------------- = ----------------
        n + 1                 2(n + 1)

这个简单推导的结果还是O(n)