一、复杂度

2022-01-08 本文已影响0人咸鱼Jay

什么是算法

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

使用不同算法，解决同一个问题，效率可能相差非常大

比如：求第 n 个斐波那契数（fibonacci number）

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

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

如何评判一个算法的好坏？

如果单从执行效率上进行评估，可能会想到这么一种方案
- 比较不同算法对同一组输入的执行处理时间
- 这种方案也叫做：事后统计法
上述方案有比较明显的缺点
1. 执行时间严重依赖硬件以及运行时各种不确定的环境因素
2. 必须编写相应的测算代码
3. 测试数据的选择比较难保证公正性
一般从以下维度来评估算法的优劣
1. 正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
2. 时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
3. 空间复杂度（space complexity）：估算所需占用的存储空间

下面通过估算程序指令的执行次数算时间复杂度：

public static void test1(int n) {
    // 估算程序指令的执行次数（执行时间）
    // 下面if-else都算1次
    if (n > 10) { 
        System.out.println("n > 10");
    } else if (n > 5) {
        System.out.println("n > 5");
    } else {
        System.out.println("n <= 5"); 
    }
    
    //int i = 0执行1次，i < 4、 i++和println都是执行4次
    // 1 + 4 + 4 + 4 ==> 总共14次
    for (int i = 0; i < 4; i++) {// 1 + 4 + 4 
        System.out.println("test");// 4
    }
}

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

public static void test3(int n) {
    // 1 + 2n + n * (1 + 3n) ==>1 + 2n + n + 3n^2 ==> 3n^2 + 3n + 1

    for (int i = 0; i < n; i++) {//1 + 2n
        for (int j = 0; j < n; j++) {//n * (1 + 3n)
            System.out.println("test");//n
        }
    }
}

public static void test4(int n) {
    // 1 + 2n + n * (1 + 45) ==> 1 + 2n + 46n ==> 48n + 1

    for (int i = 0; i < n; i++) {//1 + 2n
        for (int j = 0; j < 15; j++) {// n * (1 + 45)
            System.out.println("test");//15
        }
    }
}

public static void test5(int n) {
    //假设n=16; 16 = 2^4 、 8 = 2^3 、 4 = 2^2 、 2 = 2^1 、 1 = 2^0
    // 其实就是求指数值
    // 4 = log2(16) 、 3 = log2(8) 、 2 = log2(4) 、 1 = log2(2)
    
    // 执行次数 = log2(n)
    while ((n = n / 2) > 0) {
        System.out.println("test");
    }
}

public static void test6(int n) {
    // log5(n)
    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)
    for (int i = 1; i < n; i = i * 2) {// 1 + 2*log2(n)
        for (int j = 0; j < n; j++) {//  log2(n) * (1 + 3n)
            System.out.println("test");// n
        }
    }
}

大O表示法（Big O）

一般用大O表示法来描述复杂度，它表示的是数据规模n 对应的复杂度
忽略常数、系数、低阶

$9 >> O(1)$
$2n + 3 >> O(n)$
$n{^2} + 2n +6 >> O(n{^2})$
$4n{^3} + 3n{^2} + 22n + 100 >> O(n{^3})$
$写法上，n{^3}等价于n{^3}$

注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率

对数阶的细节

对数阶一般省略底数
$log{_2}n$ = $log{_2}9$ * $log{_9n}$
所以 $log{_2}n$ 、 $log{_9n}$ 统称为 $logn$

最终使用大O表示法表示时间复杂度：

public static void test1(int n) {
    // 估算程序指令的执行次数（执行时间）
    // 下面if-else都算1次
    if (n > 10) { 
        System.out.println("n > 10");
    } else if (n > 5) {
        System.out.println("n > 5");
    } else {
        System.out.println("n <= 5"); 
    }
    
    //int i = 0执行1次，i < 4、 i++和println都是执行4次
    // 1 + 4 + 4 + 4 ==> 总共14次
    for (int i = 0; i < 4; i++) {// 1 + 4 + 4 
        System.out.println("test");// 4
    }
    // 时间复杂度：O(1)
}

public static void test2(int n) {
    // 1 + 3n(int i = 0执行1次，i < n、i++和都是执行n次)
    for (int i = 0; i < n; i++) {// 1 + n + n
        System.out.println("test");// n
    }
    // 时间复杂度：O(n)
}

public static void test3(int n) {
    // 1 + 2n + n * (1 + 3n) ==>1 + 2n + n + 3n^2 ==> 3n^2 + 3n + 1
    for (int i = 0; i < n; i++) {//1 + 2n
        for (int j = 0; j < n; j++) {//n * (1 + 3n)
            System.out.println("test");//n
        }
    }
    // 时间复杂度：O(n^2)
}

public static void test4(int n) {
    // 1 + 2n + n * (1 + 45) ==> 1 + 2n + 46n ==> 48n + 1
    for (int i = 0; i < n; i++) {//1 + 2n
        for (int j = 0; j < 15; j++) {// n * (1 + 45)
            System.out.println("test");//15
        }
    }
    // 时间复杂度：O(n)
}

public static void test5(int n) {
    //假设n=16; 16 = 2^4 、 8 = 2^3 、 4 = 2^2 、 2 = 2^1 、 1 = 2^0
    // 其实就是求指数值
    // 4 = log2(16) 、 3 = log2(8) 、 2 = log2(4) 、 1 = log2(2)
    
    // 执行次数 = log2(n)
    while ((n = n / 2) > 0) {
        System.out.println("test");
    }
    // 时间复杂度：O(logn)
}

public static void test6(int n) {
    // log5(n)
    while ((n = n / 5) > 0) {
        System.out.println("test");
    }
    // 时间复杂度：O(logn)
}

public static void test7(int n) {
    // 1 + 2*log2(n) + log2(n) * (1 + 3n) ==> 1 + 3*log2(n) + 2 * nlog2(n)
    for (int i = 1; i < n; i = i * 2) {// 1 + 2*log2(n)
        for (int j = 0; j < n; j++) {//  log2(n) * (1 + 3n)
            System.out.println("test");// n
        }
    }
    // 时间复杂度：O(nlogn)
}