时间复杂度与空间复杂度

1 时间复杂度估算

1.1 原理

模拟程序的运行次数

1.2 习题演示

public static void test1(int n) {
    // O(1)
    // 1
    if (n > 10) { 
        System.out.println("n > 10");
    } else if (n > 5) { // 2
        System.out.println("n > 5");
    } else {
        System.out.println("n <= 5"); 
    }
    // 1 + 4 + 4 + 4
    for (int i = 0; i < 4; i++) {
        System.out.println("test");
    }
}
public static void test2(int n) {
    // O(n)
    // 1 + 3n(i<n/i++/System...)
    for (int i = 0; i < n; i++) {
        System.out.println("test");
    }
}
public static void test3(int n) {
    // 1 + 2n + n * (1 + 3n)
    // 1 + 2n + n + 3n^2
    // 3n^2 + 3n + 1
    // O(n^2)
    // O(n)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println("test");
        }
    }
}
public static void test4(int n) {
    // 1 + 2n + n * (1 + 45)
    // 1 + 2n + 46n
    // 48n + 1
    // O(n)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 15; j++) {
            System.out.println("test");
        }
    }
}
public static void test5(int n) {
    // 8 = 2^3
    // 16 = 2^4
    // 3 = log2(8)
    // 4 = log2(16)
    // 执行次数 = log2(n)
    // O(logn)
    while ((n = n / 2) > 0) {
        System.out.println("test");
    }
}
public static void test6(int n) {
    // log5(n)
    // O(logn)
    while ((n = n / 5) > 0) {
        System.out.println("test");
    }
}
public static void test7(int n) {
    // 1 + 2*log2(n) + log2(n) * (1 + 3n)
    // 1 + 3*log2(n) + 2 * nlog2(n)
    // O(nlogn)
    for (int i = 1; i < n; i = i * 2) {
        // 1 + 3n
        for (int j = 0; j < n; j++) {
            System.out.println("test");
        }
    }
}
public static void test10(int n) {
    // O(n)
    int a = 10;
    int b = 20;
    int c = a + b;
    int[] array = new int[n];
    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i] + c);
    }
}

2 大O表示法

2.1 大O表示法特点

忽略常数、系数、低阶。
对数阶一般省略底数。

2.2 大O表示法示例

• 9 >> O(1)
• 2n + 3 >> O(n)
• n2 + 2n + 6 >> O(n2)
• 4n3 + 3n2 + 22n + 100 >> O(n3 )

• log2n = log29 ∗ log9n

  2.3 大O表示法排序

  O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

  3 针对斐波那契数列算法的时间复杂度分析

  3.1 代码

  斐波那契数列求和

  3.2 方案一

  代码

  public static long basicFibonacci(int num) {
    if (num <= 1) {
        return num;
    }
    return basicFibonacci(num - 1) + basicFibonacci(num - 2);
  }

  示例图

  

  讲解

  运行次数上：

• T(0) = 1

• T(1) = 1
• T(N) = T(N-1) + T(N-2) + 1，1指代累加计算

斐波那契数列通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。
所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。

参考资料

https://zhuanlan.zhihu.com/p/256344121

方案二

代码

public static long improvedFibonacci(int num) {
    if (num <= 1) {
        return num;
    }
    long first = 0;
    long second = 1;
    long sum = num;
    for (int i = 0; i < num - 1; i ++) {
        sum = first + second;
        first = second;
        second = sum;
    }
    return sum;
}

讲解

因为记录了子元素的值和对应的和，所以时间复杂度只需要计算for循环。根据大O表示法忽略常数，最终结果是 O(N) 。