算法性能分析

算法的性能分析概括成时间复杂度和空间复杂度两部分；

　　1. 时间复杂度

　　　　通常指算法运行的时间（大O记法只保留最高次项，忽略低次项和常数项）

　　2. 空间复杂度

　　　　通常指算法在运行过程中占用内存空间大小，记做S(n)=O(f(n))。

　　　　O(1)：随着n的变化，所需开辟的内存空间并不会随着n的变化而变化，即算法空间复杂度为一个常量；eg. for (int i = 0; i < n; i++) { ... } 

　　　　O(n)：消耗空间和输入参数n保持线性增长；eg. for (int i = 0; i < n; i++) { a[i] = i; }

　　3. 硬件性能（力扣上超时一般也是判断是否超过1s执行的次数，可以推算代码大概运行时间）

　　　　CPU配置：2.7 GHz Dual-Core Intel Core i5，1 GHz = 1000MHz = 10亿Hz，（1Hz即CPU的一次脉冲，也叫时钟周期）

　　　　计算执行代码所需的时间，例如 1+2=3（分成将1存入寄存器，将2存入寄存器，运算，保存运算结果）

　　　　运行过程中有时间损耗，所以可推算 O(n) 大约为 5 亿左右，O(n²) 大概为 O(n) 开根号，以此类推。

　　4. 递归算法

　　　　递归算法的时间复杂度 = 递归的次数 * 每次递归的时间复杂度。（a^b = n 推出 b = log_an）

　　　　递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度（每次递归所需的空间都被压到调用栈里，每次递归结束就是本次数据弹栈的过程，所以栈最大的长度就是递归的深度）。

　　5. JVM

　　　　Java 依赖JVM来做内存管理，不了解JVM内存管理的机制，很可能会因一些错误的代码写法而导致内存泄漏或内存溢出。

　　6. 内存对齐

　　　　平台原因：不是所有的硬件平台都能访问任意内存地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。为了同一个程序可以在多平台运行，需要内存对齐。

　　　　硬件原因：经过内存对齐后，CPU访问内存的速度大大提升。

　　　　注：CPU一次寻址四个字节，因此char在内存对齐的时候会产生3个空位。eg. struct node { int num; char cha;}st；st占用的内存是 4个字节(int) + 内存对齐产生的4个字节内存(char，3个内存为空)