Ch3 算法分析

1. 时间成本

一个算法运行的总时间主要和两点有关：

1. 执行每条语句的耗时
2. 执行每条语句的频率

前者取决于计算机，编译器和操作系统；后者取决于程序本身和输入，因此：

通过以上公式可知分析程序执行的时间成本关键在分析”语句频率”，我们通常使用的方法—“渐进分析”

渐进分析

定义：渐进分析是指当输入规模（n）很大，或者说达到极限（微积分意义上），对算法进行研究，此时我们可以在频率分析中忽略幂次较低的项和某些系数。 :::info 数学语言：
在频率分析中可能产生冗长的表达式，如：

根据渐进分析定义

则原式可近似为

给出一般的近似方式（来自《算法》）
:::

上限

:::danger “大欧表示法”
定义：
意义：对于问题的所有输入（包括最差情况），只要输入规模足够大，算法总能够在步以内完成 :::

下限

:::danger “大欧米伽表示法”
定义：
意义：对于问题的所有输入（包括最优情况），只要输入规模足够大，算法最快能够在步以内完成 :::

平均

:::danger “大西塔表示法”
当算法开销增长率的上下限相等时，即算法既在又在中，可以用表示
给定一个反映算法时间开销的表达式时，其上下限通常相等，因为此时运行时间函数已经被表示了出来，渐进分析过程已经确定，则可确定 :::

常见增长率

描述	增长的数量级	说明	举例	图像
常数级别	1	普通语句	两数相加
对数级别	logN	二分策略	二分查找
线性级别	N	循环	找出最大值
线性对数级别	NlogN	分治	归并排序
平方级别	N²	双层循环	检查所有元素对
立方级别	N³	三层循环	检查所有三元组
指数级别	2^N	穷举查找	检查所有子集

注意：平方级别和立方级别的算法对于大规模的问题是不可用的，许多问题的平方级解法可以有线性对数级别算法代替

2. 空间成本

数据结构主要的目的是存储数据，提供简单高效的访问，为此每个数据结构都有附加的”结构性开销（overhead）”，不同算法的空间成本主要来自于使用数据结构的结构性开销

以Java为例

以下以Java为例讨论不同数据结构的空间成本，已知Java原始数据类型常见内存需求：

• 对象

对象使用内存 = 所有实例变量内存 + 对象本身开销(一般为16字节，包括一个指向对象的类的引用，垃圾收集信息，同步信息，且一般内存的使用都会被填充为8字节的倍数)
eg：一个Integer对象使用24字节开销 = 16字节对象开销 + 4字节int开销 + 4字节填充

• 链表

嵌套的非静态(内部)类，如Node类，还需要额外8字节用于一个指向外部类的引用
eg：一个Node对象使用40字节开销 = 16字节对象本身 + 指向Item和Node对象的引用各需要8字节 + 8字节额外开销

• 数组

Java中数组被视为对象，数组都需要24字节的头信息(16字节对象开销+4字节保存长度+4字节填充);一个对象的数组实际上是对象的引用的数组，除了对象元素的开销还有对象引用的开销;而二维数组是一个数组的数组，每个数组都是一个对象：
一般数组：一个N个int的数组开销(24+4N)字节 = 24字节头信息 + 4N数组元素开销
对象数组：一个含有N个Node对象的数组开销(24+40N+8N)字节 = 24字节头信息 + 40N对象元素开销 + 8N对象引用开销
二维数组：一个M*N的double类型数组开销()字节 = 24字节头信息 + 8M字节所有对象引用开销 + 24M元素数组开销 + 8MN所有double变量开销

• String对象

String对象在库中定义

public class String
{
    private char[] value;
    private int offset;
    private int count;
    private int hash;
    ...
}

String的标准实现含有4个实例变量：一个指向字符数组的引用(8字节)和三个int值(各4字节)，第一个int值描述的是字符数组中的偏移量，第二个int值是一个计数器(字符串的长度)，第三个int值是一个散列值，因此：
一个String对象开销40字节() = 16字节对象开销 + 3*4int开销 + 8字节引用开销 + 4个填充字节
但这只是除了字符数组之外字符串所需的内存空间，所有字符所需的内存需要另记，因为String的char数组常常在多个字符串之间共享，因为String对象不可变.这种设计使String的实现可以在多可对象有相同value[]数组时节省内存