算法基础知识

时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间。

算法导论给出的解释：大 $O$ 用来表示上界，

业内的一个默认规定，这里说的 $O$ 代表的就是一般情况，而不是严格的上界。快速排序的时间复杂度应该是 $O (n^{2})$ ，但是我们依然说快速排序是 $ O(n \log n)$ 的时间复杂度。

面试中说道算法的时间复杂度是多少指的都是一般情况。

但我们统一说 $\log n$ ，也就是忽略底数的描述，而且也可以证明（通过对数公式中的换底公式），当样本量很大的时候， $\log n$ 的大小与底数无关

换底公式：

\log_{i} n = \frac{\log_{j} i}{\log_{j} n}

\log_{i} n = O (\log_{i} j \times \log_{j} n)

其中 $\log_{i} j$ 是一个常数。

算法超时

任何开发计算机程序员的软件工程师都应该能够估计这个程序的运行时间是一秒钟还是一年。

自己写代码算一下一秒能执行多少次，代码地址

测试结果如下：

时间复杂度	时间/毫秒	计算次数
$n^{2}$	110	300000000
$n$	105	16000
$n \log n$	108	9500000

基本可以得出 $n$ 、 $n^{2}$ 、 $n \log n$ 的时间复杂度，几乎相同的时间，执行的次数不同，刚好对应时间复杂度公式： $1.6 \times 10^{4}$ 的平方约等于 $3 \times 10^{8}$ ，因为系统执行一次加法的时间是固定的，执行了多少次加法就跟算法复杂度有关

同时，我们也可以推算出，1s，可以执行 $3 \times 10^{9}$ 次加法，跟 CPU 主频 2.20GHZ 接近，G 代表十亿，

递归算法的时间复杂度

题目：求 x 的 n 次方，当我们拿到题目的时候，其实很自然的想到，执行 n-1 次乘法，算法复杂度 $O (n)$ ，但是这里面实际上是有优化空间的，比如当 n 为 6 的时候，执行到 x 的平方的时候，还剩下两个 x 的平方，这个时候，直接拿 x 的平方乘以自己即可，不需要再从 $x \times x$ 开始算起，这样， $x \times x \times x \times x$ 就只用了两次运算，而不是三次运算，这样就节省了一次运算，因为计算机执行一次运算的时间是固定的，算法的作用是，减少获取结果的运算执行次数，其中一个重要的提升效率的思路就是观察代码中的重复运算，

/**
 * 因为没有节省运算，所以实际上的算法复杂度还是 O(n)
 *
 * @param x
 * @param n
 * @return
 */
private static long functionBase(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }
    if (n % 2 == 1) {
        return functionBase(x, n / 2) * functionBase(x, n / 2) * x;
    } else {
        return functionBase(x, n / 2) * functionBase(x, n / 2);
    }
}

/**
 * 将 function(x, n / 2) 提取出来，节省了乘法运算，所以算法复杂度为 O(logn)
 *
 * @param x
 * @param n
 * @return
 */
private static long function(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }
    long t = function(x, n / 2);
    if (n % 2 == 1) {
        return t * t * x;
    } else {
        return t * t;
    }
}

PS：算法中乘法运算真的快，算 2 的 60 次方一毫秒都不到。

空间复杂度分析

空间复杂度 (Space Complexity) 记作 $S (n)$ 依然使用大 $O$ 来表示。利用程序的空间复杂度，可以对程序运行中需要多少内存有个预先估计。举个例子：

随着 n 的变化，所需开辟的内存空间并不会随着 n 的变化而变化。即此算法空间复杂度为一个常量，所以表示为大 $O (1)$ 。当消耗空间和输入参数 n 保持线性增长，这样的空间复杂度为 $O (n)$ ，递归算法的空间复杂度是 $O (\log n)$

空间复杂度跟编程语言的特性有很大关联（比如在 Java 和 C++ 中，递归中调用方法的时候，是值传递还是引用传递，会有不同，如果是值传递，就会发生内存空间的开辟，影响空间复杂度）

例如编译器的内存对齐，编程语言容器的底层实现等等这些都会影响到程序内存的开销。

递归

以递归为例理解时间复杂度和空间复杂度

递归的次数 X 每次递归的时间复杂度。

递归算法的空间复杂度 = 每次递归的空间复杂度 X 递归深度

为什么要求递归的深度呢？

因为每次递归所需的空间都被压到调用栈里（这是内存管理里面的数据结构，和算法里的栈原理是一样的），一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

此外，空间复杂度跟编程语言有关，在 C/C++ 中函数传递数组参数，不是整个数组拷贝一份传入函数而是传入的数组首元素地址，所以一次递归的空间复杂度是 $O (1)$ ，而不是 $O (n)$ ，所以

/**
 * 代码最简洁，但是时间复杂度爆炸
 * 时间复杂度为 2^(n-1),得出的结果是递归二叉树除根节点以外的节点数，即为调用次数
 * 空间复杂度为 O(n)
 * @param num Fibonacci 数列的第几个数 从 1 开始
 * @return
 */
public static long fibonacci0(int num) {
    if (num <= 1) {
        return 0;
    }
    if (num == 2) {
        return 1;
    }
    return fibonacci0(num - 1) + fibonacci0(num - 2);
}

/**
 * 主要目的是减少递归调用的次数，导致上面这种递归的时间复杂度爆表的根本原因是一次递归里调用了两次自身，
 *<br/>
 * 这个算法的重点在于，直接用递归来从 f(1)、f(2) 开始计算第 n 个项的值，这样，求 f(n) 实际上只用计算 n 次，复杂度大大降低 为 O(n) ，太香了
 * 而 fibonacci0 是把 f(n) 拆分成 f(n-1)、f(n-2) 不停地往下拆分，一直拆分到 f(1)、f(2))
 * <br/>
 * 实际操作中，为了帮助理解，我们还可以添加 nowNum 变量，记录一下，我们算到那个变量了。如果和目标 num 相等即可返回
 *
 *
 * 空间复杂度为 O(n)
 *
 * @return
 */
public static long fibonacci1(long first, long second, int nowNum, int num) {
    if (num <= 1) {
        return 0;
    }else if (num == 2) {
        return 1;
    }else if(num == nowNum) {
        return first + second;
    }else{
        return fibonacci1(second, first + second, nowNum +1, num);
    }
}

/**
 * 从 fibonacci1 中优化而来，可以看到，now 从 3 开始算，每次 +1，最终与 num 相等，拿其实可以直接用 num -1 最终等于 3，递归的次数是一样的，这样可以节约一个变量
 * @param first
 * @param second
 * @param num
 * @return
 */
public static long fibonacci2(long first, long second,int num) {
    if (num <= 1) {
        return 0;
    }else if (num == 2) {
        return 1;
    }else if(num == 3) {
        return first + second;
    }else{
        return fibonacci2(second, first + second, num-1);
    }
}

不同语言的内存管理

内存对齐

现代计算机中内存空间都是按照 byte 划分的，从理论上讲似乎对任何类型的变量的访问可以从任何地址开始，但是实际的计算机系统对基本类型数据在内存中存放的位置有限制，它们会要求这些数据的首地址的值是某个数 k（通常它为 4 或 8）的倍数，这就是所谓的内存对齐。即：CPU 读取内存不是一次读取单个字节，而是一块一块的来读取内存，块的大小可以是 2，4，8，16 个字节，具体取多少个字节取决于硬件。比如假设 CPU 把内存划分为 4 字节大小的块，现在内存里一个 char 占据了一个自己，后面跟着四个字节的 int，这个时候，CPU 要读取这个 int 的数值，得读取两次，总共 8 个字节，才能获取这个 int 数据，但是如果 char 占了 4 个字节（后面三个字节空着），那遇到 char 的时候，直接跳过，然后正好可以获取一个完整的 int，这样就会快很多，这个故意调大占用空间把多余的空间空着的操作，就是内存对齐。

内存对齐岂不是浪费的内存资源么？是的，事实上，相对来说计算机内存资源一般都是充足的，我们更希望的是提高运行速度。这是典型的，空间换时间，

编译器一般都会做内存对齐的优化操作，也就是说当考虑程序真正占用的内存大小的时候，也需要认识到内存对齐的影响。