毕业好多年了，工作这些年不曾使用太多涉及算法的东西，大学学的几乎都已经还给老师了，接下来复习一下算法相关的知识吧。

评判算法的优劣

一般情况下从下面几个维度来评判算法的优劣：

• 正确性、可读性、健壮性
• 时间复杂度（估算程序执行的次数）
• 空间复杂度（估算程序占用的时间）

时间复杂度估算

就是来大概估算程序所执行的次数，来看下面几个例子

• 1.)案例一

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

    // 这里是循环：
    //  int i 声明执行 1 次 
    //  i < 4 判断执行 4 次
    //  i ++  执行 4 次
    //  输出语句执行 4 次
    for (int i = 0; i < 4; i++) {
        System.out.println("test");
    }

    // 总次数为 1 + 1 + 4 + 4 + 4
}

• 2.)案例二

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

• 3.)案例三

public static void test3(int n) {
    //外循环执行次数是 1 + 2n
    for (int i = 0; i < n; i++) {
        //内循环执行次数是 1 + 3n，还要乘上外层的 n 次
        for (int j = 0; j < n; j++) {
        System.out.println("test");
        }
    }

    // 总次数为 1 + 2n + n * (1 + 3n) = 3n^2 + 3n + 1
}

• 4.)案例四

public static void test4(int n) {
    while ((n = n / 2) > 0) {
        System.out.println("test");
    }

//如果输入的是 8, 循环过程如下
// 8
// 4
// 2
// 1
// 0  不符合，退出

// 8 = 2^3
// 由此可推算  输入 16 = 2^4

// 3 = log2(8)
// 4 = log2(16)

// 总执行次数为 log2(n)
// 其实这样的主要看除以几， 如果除以 5，那总次数就是 log5(n)

}

• 5.)案例五

public static void test5(int n) {
    // i += i 也就是 i * 2
    // 外层是 1 + log2(n) + log2(n)
    for (int i = 1; i < n; i += i) {
        // 内层是 1 + 3n, 在乘以 log2(n) 次
        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)
}

大O表示法

一般用 大O表示法 来描述复杂度，它表示的是数据规模 n 对应的复杂度，一般我们把算出来的次数 忽略常数，系数，低阶之后作为复杂度表示数，所以我们上面五个案例的时间复杂度分别为

• O(1)
• O(n)
• O(n^2)
• O(log(n))
• O(nlog(n))

常见的时间复杂度排序

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2 ) < O(n^3 ) < O(2^n ) < O(n!) < O(n^n)

根据时间复杂度反推可能的算法（临时用）

• 1.)O(1) 一般都是数学方法或者找规律直接求解的方法

• 2.)O(logn) 二分法或者位运算

• 3.)O(√n) 几乎是分解质因数

• 4.)O(n) 在面试题里高频出现。一般都是循环一遍得到解，简单的链表或者数组的题大都是O(n)， 可能的算法有：

  1. 枚举
  2. 一维状态的动态规划
  3. 树，图的遍历算法，包括并查集
  4. 可能用到栈和队列这些数据结构
  5. 使用hash优化检索复杂度
  6. 双个指针遍历问题 （two-pointers）
  7. 贪心

• 5.)O(nlogn)

  1. 排序，可能数据排序以后可以很容易解决
  2. 可能用到优先队列，比如用到堆
  3. 多次二分检索的问题
  4. 分治算法
  5. 可能用到线段树或者其他的高级数据结构

• 6.)O(n^2) 该复杂度的算法一般就是两重循环

  1. 动态规划
  2. 枚举
  3. 数组

• 7.)O(n^3)

  1. 动态规划
  2. 枚举
  3. 数组
• 8.)O(a^n)、O(n!)等等非多项式复杂度(non-deterministic polynomial NP)
  1. 搜索算法，包括回溯等等
  2. 状态压缩的动态规划问题
  3. 组合O(2^n)
  4. 排列O(n!)