时间复杂度

前言

我们在程序开发过程中为了衡量一个算法的好坏制定了两个标准时间复杂度和空间复杂度，因为程序运行的时间长短和占用内存的大小直接影响到程序的执行效率。

但我们需要注意程序运行的时间长短不仅仅取决于代码，还有运行环境、硬件、数据量等因素影响，什么意思呢？

• 硬件：当一段相同的代码同时在2C4G和4C8G上的机器运行因为机器计算力不一样，所以程序运行时间大概率不同（特别是代码计算量大时）。
• 运行时环境：当一台机器上大部分资源被其它服务所占用，另外一台机器上面没有其它服务，那么一段相同的代码在两个硬件相同机器上执行时间长短会不一样。
• 数据量：一段相同的代码定义入参为n（或输入规模），代码片段会循环n次，那么n=1和n=1w执行时间长度上肯定不一样。

所以说时间复杂度并不能直接等于代码运行的时间长短，这里的时间复杂度指的是代码基本操作执行的次数。

基本操作执行次数

所有案例只考虑主要流程的执行次数

案例一

如存在一个面包长10cm，每2分钟只能吃1cm，那么吃完这个面包需要多长时间呢？

很明显答案为10*2=20分钟，所以当吃面包的速度不变的情况下面包长n cm那么就需要花费2n的时间才能吃完面包，这里可以记作T(n) = 2n。

public void method1(int n){
    for (int i = 0; i < n; i++) {
        System.out.println("吃一口面包");
        System.out.println("吃完了~");
    }
}

案例二

假设再存在一个面包长16cm，每过5分钟吃掉该面包的一半，那么面包变为1cm需要花费多长时间？

这个计算稍微复杂点，第五分钟吃掉8cm、第十分钟吃掉4cm、第十五分钟吃掉2cm、第二十分钟吃掉第1cm，还剩1cm，就是将面包长度不断的做等分，这就是数学中的对数，这里答案就是5 * log2(16) = 20，当面包长度为n时这里可以记作T(n) = 5logn。

public void method2(int n){
    for (int i = n; i > 1; i=i/2) {
        System.out.println("吃一口面包");
        System.out.println("吃一口面包中2");
        System.out.println("吃一口面包中3");
        System.out.println("吃一口面包中4");
        System.out.println("吃完了~");
    }
}

案例三

假设存在一个面包长10cm，吃掉第一个1cm需要1分钟，吃掉第二个1cm需要2分钟，吃掉第三个1cm需要3分钟，那么一个面包吃完需要多少分钟呢？

这其实就是1到10的累加，所以当面包长度为n时需要的时间就可以记作T(n) = (n / 2) * (1+n) ，变化为T(n) = 0.5n + 0.5n^2^。

public void method3(int n){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <i ; j++) {
            System.out.println("吃一口面包中"+(j+1));
        }
        System.out.println("吃完了~");
    }
}

案例四

假设存在一个鸡腿，吃一个鸡腿需要两分钟那么吃完整个鸡腿需要多长时间。

这个答案就太简单了两分钟，需要的时间简单记为T(n) = 2。

渐进时间复杂度

到这里我们知道了程序基本操作执行的次数，那是不是就直接等于时间复杂度了呢？显然也不是，我们看到除案例四外其余三个都是受输入数字n的影响，所以这里需要引进渐进时间复杂度，也称为大O表示法，来简化时间复杂度的表示，大O表示法有如下原则

1. 如果运行时间也就是T(n)是常数量级，那么用数字1表示。
2. 只保留时间函数中的最高阶项。
3. 如果最高阶项存在，那么省略最高阶项前面的系数。

根据这个原则就可以得出前面案例的时间复杂度

• 案例一：运行时间表示为T(n) = 2n，按照原则3省略最高阶项前面的系数，时间复杂度为O(n)。
• 案例二：运行时间表示为T(n) = 5logn，按照原则3省略最高阶项前面的系数，时间复杂度为O(logn)。
• 案例三：运行时间表示为T(n) = 0.5n + 0.5n^2^，按照原则2和原则3只取最高阶项和省略最高阶项前面的系数，时间复杂度为O(n^2^)。
• 案例四：运行时间表示为T(n) = 2，按照原则1所有常数用数字1表示，时间复杂度为O(1)。

不难看出这些时间复杂度有如下排序

**O(1) < O(logn) < O(n) < O(n^2^) **