算法时间复杂度学习

1. 算法

算法：是用于解决特定问题的一系列的执行步骤。

举例：

//计算 a + b的和
public static int add( int a, int b){
    return  a + b;
}

//计算 1 + 2 + 3 + 4 + ... n 之和
public static int sum( int n){
    int sum = 0;
    for (int i = 0; i <= n; i ++ ){
        sum += i;
    }
    return sum;
}

简单的求两数之和，以及求n个数之和，都是算法。

但是，相同的结果，不同的方法效率天差地别。

示例：

//计算 1 + 2 + 3 + 4 + ... n 之和
public static int sum1( int n){
    int sum = 0;
    for (int i = 0; i <= n; i ++ ){
        sum += i;
    }
    return sum;
}

//计算 1 + 2 + 3 + 4 + ... n 之和
public static int sum2( int n){
    return n * (n + 1) / 2;
}

由以上示例可以发现，1 + 2 + 3 + 4 + ... n：

• 使用sum1方法使用for循环累加；
• 使用sum2数学归纳的公式：n * (n + 1) / 2；

两种实现方式，在 n 较小时可能看不出太大差别，但是当n足够大时，sum2 执行的步骤明显少于sum1方法，效率也更高。

1.1 如何判断一个算法的好坏

如果单从执行效率上进行评估，可能会想到这么一种方案：比较不同算法对同一种输入的执行处理时间，这种方法叫做 事后评估法；

一般从以下几个维度来评估算法的优劣：

• 正确性，可读性，健壮性（对不合理输入的反应能力和处理能力）
• 时间复杂度（time complexity）：估算程序指令的执行次数 （执行时间）
• 空间复杂度（space complexity）：估算所需占用的存储空间

2. 时间复杂度

对于我们常说的时间和空间复杂度，都是估算；

因为当我们的数据规模极大的时候，估算更为合适；

示例：

public static void test1(int n) {
        // 执行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"); 
        }
        
        //执行 4 次
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }
        //总执行： 1 + 4 = 5次
    }

    public static void test2(int n) {
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }
        // 总执行 1 + n + n + n = 3n + 1次
    }

    public static void test3(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
        // 1 + 2n + n * (1 + 3n)
        // 1 + 2n + n + 3n^2
        // 总执行：3n^2 + 3n + 1次
    }

    public static void test4(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 15; j++) {
                System.out.println("test");
            }
        }
        // 1 + 2n + n * (1 + 45)
        // 1 + 2n + 46n
        // 总执行：48n + 1次
    }

    public static void test5(int n) {
        while ((n = n / 2) > 0) {
            System.out.println("test");
        }
        // 8 = 2^3
        // 16 = 2^4
        
        // 3 = log2(8)
        // 4 = log2(16)
        // 执行次数 = log2(n)
    }

    public static void test6(int n) {
        while ((n = n / 5) > 0) {
            System.out.println("test");
        }
        // 执行次数 =log5(n)
    }

    public static void test7(int n) {
        for (int i = 1; i < n; i = i * 2) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
        // 1 + 2*log2(n) + log2(n) * (1 + 3n)
        
        //总执行次数： 1 + 3*log2(n) + 2 * nlog2(n)
    }

对于n阶for循环，初始化i = 1 执行1次；i < n，执行n次；i ++执行n次；print执行n次，所以一般for循环执行的次数：3n + 1

2.1 大O表示法

一般用大O表示法来表示时间或空间复杂度，它表示数据规模对应的复杂度；

大O表示法特点：

• 忽略常数，系数，低阶

  • 9 >> O(1)
  • 2n + 3 >> O(n)
  • log2(n)、log3(n) >> O(log(n))
  • nlog2(n) + 5 >> O(nlog(n))
  • n^2 + 2n + 6 >> O(n^2)
  • n^3 + 4 * n^2 + 2n + 6 >> O(n^3)

所以对应test1-test7示例的复杂度：

• test1 >> O(1)
• test2 >> O(n)
• test3 >> O(n^2)
• test4 >> O(n)
• test5 >> O(log(n))
• test6 >> O(log(n))
• test7 >> O(nlog(n)

注意：大O估算法仅仅是一种粗略的估算模型，能短时间内了解一个算法的估算效率。

复杂度-摘自小码哥课件

3. 斐波那契数

简单算法示例： 求第n个斐波那契数 （第一个数为0，第二个数为1 ，第n个数为前两个数n-1 和 n-2之和 ）

方法1：迭代实现

    /**
     * 0 1 2 3 4 5 6 7 .....n
     * 0 1 1 2 3 5 8 13 ....?
     * 
     * */
    public static int fib(int n){
        if (n <=1) return n;
        return fib(n -2) + fib( n -1);
    }
    

方法2：for循环实现

    /*
     *for循环执行n-1次  
     * 
     * **/
    public static int fib2(int n){
        if(n <= 1) return n;
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }

方法3： while循环

    public static int fib3(int n){
        if(n <= 1) return n;
        int first = 0;
        int second = 1;
        while(n-- > 0) {
            second += first;
            first = second - first;
        }
        return second;
    }

复杂度对比：

• fib：O（2^n）

  
  fib复杂度-摘自小码哥课件

• fib2：使用for循环，复杂度估计为O（n）

• fib3：与for循环差别不大，复杂度估计为O（n）

简单看来，fib实现方式易于理解，且代码较少，但从时间复杂度来看，fib2的性能大大的高于fib；

对比-摘自小码哥课件

• 如果有一台1GHz的计算机，运算速度为10^9每秒

• 当n=64时；

  • fib：O（2^n） 耗时584.94年

  • fib2与fib3：O（n） 耗时6.4 * 10 ^(-8)秒（纳秒级别）