第三章 复杂度

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

一般从以下维度来评估算法的好坏：

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

• 空间复杂度（space complexity）：估算所需要占用的存储空间

  复杂度：一个关于输入数据量n的函数

• 时间复杂度 — 昂贵

  • 与代码的结构设计有紧密联系
  • 一个顺序结构的代码，时间复杂度是 O(1)，即任务与算例个数n 无关

• 空间复杂度 — 廉价

  • 与数据结构设计有关

    大O表示法（Big O Notation）

• 一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度

• 忽略常数、系数、低阶
• 9 >> O(1)
• 2n+3 >> O(n)
• n^2 +2n+3 >> O(n^2)
• 4n^3 +7n^2 +3n+2 >> O(n^2)
• 注意：大O标识法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
• 对数阶的细节
  • 对数阶一般省略底数
  • logn = log9 + logn
  • 所以 logn、logn 统称为 log n

**

常见复杂度

O(1) < O(log n) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
**

 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");
        }
        // 1 + 4+4+4
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }
        //14 >> O(1)
    }
    public static void test2(int n) {
        // 1+ n +n + n=1+3n >> O(n)
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }
    }
    public static void test3(int n) {
        // 1+ n +n + n * (1+3n)
        // 1+2n + n +3n^2
        // 1+ 3n+ 3n^2 >> O(n^2)
        for (int i = 0; i < n; i++) {
            //1+3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }
    public static void test4(int n) {
        // 1 + n + n + n * (1+15+15+15)
        // 1+2n +46n
        // 1+48n >> O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 15; j++) {
                System.out.println("test");
            }
        }
    }
    //O(log n)
    public static void test5(int n) {
        // n = 8 >> 8/2=4 >> 4/2=2 >>2/2= 1 >> 0
        // 2^3 = 8
        //a ^ x = n  >> x =log a N  >> 3 = log 2 8  >> O(log 2 n) >> O(log n)
        while ((n = n / 2) > 0) {
            System.out.println("test");
        }
    }
    public static void test6(int n) {
        // O(log 5 n) >> O(log n)
        while ((n = n / 5) > 0) {
            System.out.println("test");
        }
    }
    public static void test7(int n) {
        // i+=i  <==> i=i+i <==> i = i * 2
        // n=8  i=1 <8 , i = 1*2
        // n=8  i=2 <8 , i = 2*2
        // n=8  i=4 <8 , i = 4*2
        // >> log 2 8
        // 1 + log n + log n + (log n * (1 + 3n))
        // 1+ log n + logn + logn +3nlogn
        // >> O(nlogn)
        for (int i = 1; i < n; i += i) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }
    //O(n)
    public static void test10(int 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);
        }
    }