认识时间复杂度.md

认识时间复杂度

常数时间的操作

一个操作如果和数据量没有关系, 每次都是固定时间内完成的操作, 叫做常数操作.
如: 数组寻址操作、位运算符、加减乘除运算等

时间复杂度

时间复杂度为一个算法流程中, 常数操作数量的指标, 常用 O(读作 big O) 来表示.
具体来说, 在常数操作数量的表达式中, 只要高阶项, 不要低阶项, 也不要高阶项的系数, 剩下的部分记为 f(N),
那么时间复杂度为 O(f(N))

如何评价一个算法流程的好坏

先看时间复杂度的指标, 再分析不同数据样本下的实际运行时间, 也就是常数项时间.

一个理解时间复杂度的例子

一个有序数组A(长度为N), 另一个无序数组B(长度为M), 请打印B中所有在A中的数

算法1: 对于数组B中的每一个数, 都在A中通过遍历的方式找一下

算法2: 对于数组B中的每一个数, 都在A中通过二分的方式找一下

算法3: 先把数组B排序, 再用类似外排的方式打印所有在A中出现的数

三个算法的时间复杂度各是多少, 如何分析好坏?

# 算法1
时间复杂度: O(M*N)

# 算法2
二分查找的时间复杂度是O(logN), logN是以2为底(省略2), 所以算法2时间复杂度: O(M*logN)

# 算法3
算法3的流程是: 假如A数组是 [1, 2, 4, 6, 7], B数组是 [3, 6, 9], 用两个指针p1和p2分别指向A、B数组下标为0的元素
[1, 2, 4, 6, 7] [3, 6, 9]
 ^               ^
 p1              p2
比较p1和p2
    p1 < p2 : p1右移
    p1 = p2 : 打印, p1和p2右移
    p1 > p2 : p2右移
算法3的时间复杂度: O(M*logM) => 数组B排序 + O(N+M) => 两个数组右移指针

# 3个算法的比较
算法1的时间复杂度比算法2和算法3的时间复杂度要高.
对于算法2和算法3, 不能直接看出哪个的时间复杂度高, 需要根据样本量来确定,
如果M远大于N, 则算法3的时间复杂度(可简化为O(M*logM))要比算法2高
如果M远小于N, 则算法3的时间复杂度(可简化为O(N+M))无法和算法2比较, 要根据具体的样本量来确定.

求时间复杂度

for (i = 0; i < n; i++) {
    for (j = i; j < n; j++) {
        // TODO
    }
}

分析时间复杂度

i = 0时, 内循环执行n次
i = 1时, 内循环执行n-1次
...
f(N) = n + (n-1) + (n-2) + ... + 2 + 1 = n*(n+1)/2 = n^2/2 + n/2

根据 只要高阶项, 不要低阶项, 也不要高阶项的系数
得到时间复杂度为: O(n^2)