概念

通过事前预估算法时间开销T(n)问题规模n的关系(T 表示 time)函数,来描述该算法的运行时间。

示例1

// 逐步递增型爱你		
public static void main(String[] args) { // n 为问题规模
    loveYou(3000);
}

private static void loveYou(int n) {
    int i = 1; // ------------------------------------- (1)
    while (i <= n) { // ------------------------------- (2)
        i++; // --------------------------------------- (3)
        System.out.println("I Love You " + i); // ----- (4)
    }
    System.out.println("I Love You More Than " + n); // (5)
}

结果

I Love You 2995
I Love You 2996
I Love You 2997
I Love You 2998
I Love You 2999
I Love You 3000
I Love You 3001
I Love You More Than 3000

语句频度:
(1) 执行1次
(2) 执行3001次
(3)(4) 执行3000次
(5) 执行1次

T(3000) = 1+3001+2*3000+1
时间开销与问题规模n的关系:
T(n) = 3n+3 ≈ 3n

时间复杂度表达式可以只考虑阶数高的部分

上述表达式可以简化为 T(n) = O(n)
大O表示"同阶",同等数量级。即:当n→∞时,二者之比为常数

计算技巧

(a)加法规则
T(n) = T1(n)+T2(n) = O(f(n))+O(g(n)) = O(max(f(n),g(n)))
↓---↓---↓---↓
多项相加,只保留最高阶的项,且系数变为1

(b)乘法规则
T(n) = T1(n)*T2(n) = O(f(n))*O(g(n)) = O(f(n)*g(n))
↓---↓---↓---↓
多项相乘,都保留

时间复杂度大小关系

示例2

// 嵌套循环型爱你
public static void loveYou(int n) {
    int i = 1;
    while (i <= n) {
        i++;
        System.out.println("I Love You " + i);
        for (int j=1; j<=n; j++) {
            System.out.println("I'm Iron Man");
        }
    }
    System.out.println("I Love You More Than " + n);
}

时间开销与问题规模n的关系:
T(n) = O(n)+O(n2) = O(n2)

示例3

// 指数递增型爱你
public static void loveYou(int n) {
    int i = 1;
    while (i <= n) {
        i = i*2; // 每次翻倍
        System.out.println("I Love You " + i);
    }
    System.out.println("I Love You More Than " + n);
}

结果

I Love You 2
I Love You 4
I Love You 8
I Love You 16
I Love You 32
I Love You 64
I Love You 128
I Love You 256
I Love You 512
I Love You 1024
I Love You 2048
I Love You 4096
I Love You More Than 3000

计算上述算法的时间复杂度T(n):
设最深层循环的语句频度(总共循环次数)为x,则由循环条件可知,循环结束时刚好满足2x>n
x = log2n+1
T(n) = O(x) = O(log2n)+O(1) = O(log2n)

示例4

// flag 数组中乱序存放了 1~n 这些数
int[] flag = {1...n};
loveYou(flag, 3000);

public static void loveYou(int[] flag, int n) {
    System.out.println("I'm Iron Man");
    for (int i=0; i<n; i++) { // 从第一个元素开始查找
        if (flag[i] == n) { // 找到元素n
            System.out.println("I Love You " + n);
            break; // 跳出循环
        }
    }
}
	

计算上述算法的时间复杂度T(n):
最好情况: 元素n在第一个位置 => T(n) = O(1)
最坏情况: 元素n在最后一个位置 => T(n) = O(n)
平均情况: 假设元素n在任意位置的概率相同为 1/n => T(n) = O(n)

总结

参考资料

2020 王道考研 数据结构【算法的时间复杂度】

Q.E.D.


The best thing you can do at work hard.