复杂度

1、什么是算法

算法就是解决特定问题的一系列执行步骤。
下面用两种不同的算法来实现获取第n个斐波那契数，在讲这个例子之前，先来说下什么是斐波那契。
斐波那契数又称为"[兔子数列]"，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N。
下面我们就使用递归和非递归的方式来实现。

1.1、递归方式

static int fib1(int n) {
    if (n <= 1)
        return n;
    return fib1(n - 1) + fib1(n - 2);
}

1.2、迭代方式

static int fib2(int n) {
    if (n <= 1)
        return n;
    int first = 0;
    int second = 1;
    int sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}

2、如何判断一个算法的好坏

我们一般从如下方面判断算法的好坏：

• 正确性、可读性、健壮性
• 时间复杂度：估算程序指令执行的时间。
• 空间复杂度：估算所占用内存空间。
  下面就来看下如何描述复杂度。

3、大O表示法

• 一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度。
  下面举例看下如何使用大O表示法来描述时间复杂度。

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");
    }

    /**
     * i = 0只会初始化一次 计为1 i < 4会执行4次 计为4 i++ 会执行4次 计为4 test输出4次 计为4 则循环共执行1+4+4+4
     */
    for (int i = 0; i < 4; i++) {
        System.out.println("test");
    }
    // 上面代码共执行1+1+4+4+4=14次
    // 大O表示法会忽略常数所以复杂度为O(1)
}

public static void test2(int n) {
    // 分析同test() 循环会执行1 + 3n
    for (int i = 0; i < n; i++) {
        System.out.println("test");
    }
    // 忽略常数，复杂度为O(n)
}

public static void test3(int n) {
    /**
     * 内部循环会执行1+3n次 则执行的次数为1+2n+n*(1+3n)=1+3n+3n^2 忽略常数、系数和低阶，复杂度为O(n^2)
     */
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println("test");
        }
    }
}

public static void test4(int n) {
    /**
     * 分析同test3()，执行次数为1+2n+n*(1+15+15+15)=1+48n 复杂度为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) {
    /**
     * 执行次数表示为n可以被2除多少次， 即log2(n)次 复杂度为(logn)
     */
    while ((n = n / 2) > 0) {
        System.out.println("test");
    }
}

public static void test6(int 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");
        }
    }
}

• 使用大O表示法，一般忽略常数、系数、低阶

执行次数	复杂度
9	O(1)
2n+3	O(n)
n²+2n+8	O(n²)
4n³+3n²+8n+22	O(n³)
4log₂n+25	O(logn)
3n+2nlog₂n+15	O(nlogn)

• 注意：大O表示法仅仅是粗略的估算，能帮助我们短时间内了解一个算法的执行效率。
• 对数阶一般省略底数
  log₂n=log₂9*log₉n
• 所以log₂n、log₉n统称为logn
• 复杂度的大小排序如下：
  O(1)< O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)
  了解了如何用大O表示法表示复杂度，以及复杂度的大小排序，下面看下我们刚开始使用迭代和递归两种方式实现的斐波那契的复杂度。

4、斐波那契两种实现方法的复杂度分析

4.1、迭代的实现方式如下

static int fib2(int n) {
    if (n <= 1)
        return n;
    int first = 0;
    int second = 1;
    int sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}

从上面代码可知循环会执行n-1次，所以复杂度为O(n-1)，忽略常数，所以复杂度为O(n)。

4.2、递归的实现方式如下

static int fib1(int n) {
    if (n <= 1)
        return n;
    return fib1(n - 1) + fib1(n - 2);
}

当n=5时，具体的执行如下图：

image.png

从上图可知递归方式的复杂度为O(2^n)。
所以递归方式实现的执行效率是远低于迭代方式的。

5、多数据规模的复杂度

上面我们举的例子都是单个数据规模的，下面看下多数据规模的复杂度如何表示。

public static void test(int n, int k) {
    for (int i = 0; i < n; i++) {
        System.out.println(i + "");
    }
    for (int j = 0; j < k; j++) {
        System.out.println(j + "");
    }
}

上面代码中有两个数据规模：n和k，其复杂度为O(n+k)。