算法 - 大O复杂度表示法

2020/04/30

之前也看过一些讲解大O复杂度的文章,但一直模棱两可。
直到我看到了这两篇文章:复杂度分析(上)和(下), 才有了更深一步的理解。

首先来看下公式:

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

分别代表什么意思?

T(n):代表所有代码的执行时间。
f(n):代表每行代码的执行次数。

举个例子:

public void method(int n){
    int i = 0;   // line 1
    int j = 0;   // line 2
    for (; i < n; i++){            // line 3
        System.out.println(i);     // line 4
        for (; j < n; i++){        // line 5
            System.out.println(j); // line 6
        }
    }
}

我们来分析一下:

line 1和2分别执行1次。
line 3和4分别执行n次。
line 5和6分别执行n^2次。

所以f(n) = 2n^2 + 2n + 2。我们假设每行代码执行的时间相同,都是unit_time

那么T(n) = (2n^2 + 2n + 2) * unit_time

可以得出如下结论:所有代码的执行时间T(n)和每行代码的执行次数f(n)正比

这就是大O的由来,可以表示成: T(n) = O(2n^2 + 2n + 2)

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

当 n 很大时,你可以把它想象成 10000、100000。而公式中的系数低阶常量三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了。

因此,我们可以简化成T(n) = O(n^2)


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory