第二章 程序的性能分析

时间复杂度

理论上是指算法的最坏情况，即上界

但平时指的是一般情况

例如：

插入排序 一般情况：O(n^2) 最好情况：O(n) 最坏情况：O(n^2)

快速排序 一般情况：O(n^2) 最好情况：O(nlogn) 最坏情况：O(n^2)

按理来说，快排时间复杂度应该是O(n^2)；但是业界习惯把快排的时间复杂度默认为O(nlogn)

时间复杂度还与数据规模有关

注意：logn是忽略底数的

注意：面试不要说不会；换成，可不可以给点提示

递归算法的时间复杂度本质上要看递归的次数与每次递归中的操作次数的乘积。

内存管理

程序运行时所需的内存空间分为固定部分和可变部分

固定部分的内存消耗不会随着代码运行而产生变化，而可变部分会产生变化。

固定部分：

代码区：存储二进制代码

数据区：全局变量，静态变量，常量等

可变部分：

栈区：运行方法的形参，局部变量，返回值，以及递归栈所需的空间。系统自动分配与回收

堆区：动态开辟的空间，存放new出来的对象在堆区中的真实数据。需要手动回收

固定部分占用空间固定，占用的空间非常小。运行时消耗的内存主要取决于可变部分。

堆区因为需要手动回收内存，所以容易出现内存泄漏。

数据类型大小

1字节byte=8bit

内存对齐

面试问题：为什么要内存对齐

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

（2）硬件原因：进程内存对其后，CPU访问内存的速度会大大提升。

内存对其也是空间换时间

空间复杂度

即程序运行时占用内存的大小；而不是程序的可执行文件的大小。

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

空间换时间

是常用的优化方法

在哈希法中，数组，set，map等容器都是以空间换时间的思路。