1.时间复杂度分析:
一个程序运行总时间主要和两点有关:
- 1.执行每条语句的耗时
- 2.执行每条语句的频率
对于大多数程序,得到运行时间的数学模型所需的步骤如下:
- 1.确定输入模型,定义问题规模
- 2.识别内循环
- 3.根据内循环的操作确定成本模型
- 4.对于给定的输入,判断这些操作的执行频率.
例如:
二分查找.他的输入模型是a[],内循环是一个while循环的所有语句,成本模型是比较操作.他的所需比较次数最多为lgN+1.
算法分析中常用函数
| 描述 | 记号 | 定义 |
|---|---|---|
| 向下取整(floor) | ⎿x⏌ | <=x的最大整数 |
| 向上取整(cell) | ⎾x⏋ | >=x的最小整数 |
| 自然对数 | lnN | LogeN (表示ex=N) |
| 以2为底对数 | lgN | log2N(表示2x=N) |
| 以2为底的整形对数 | ⎿lgN⏌ | <=lgN的最大整数 |
| 调和级数 | HN | 1+1/2+1/3+1/4+1/5+…+1/N |
| N! | 1x2x3x4x...xN |
2.空间复杂度分析:
分析内存的使用比分析时间复杂度要简单得多.而且在分析过程中我们会把复杂的对象简化成原始数据类型,而原始数据类型是预先定义好的.而且非常好理解:只需要将变量的数量和他们的类型对应的字节数分别相乘汇总即可.
对象:要知道一个对象所用的内存量,需要将所有实例变量的使用内存与对象本身的开销相加.对象本身开销一般是16字节(包括一个对象类的引用 [8字节] ,垃圾收集信息[4字节]以及同步信息[4字节]).另外一般对象的内存大小会被填充称为8的倍数(也就是对象开销+实例变量+padding=8N, 其中0<=padding<8)填充字节需要根据大小来调整.对象的引用一般是一个内存地址,因此会用8字节.
-
Integer封装的对象内存计算:
计算:16+4+?=8N 所以padding=4 ,一共占24 Byte
-
Date对象内存计算:
计算 :16+4*3+?=16+12+? =8N (?=4,一共为 32)
-
Counter 对象:
计算:16+8+4+?=8N(28+?=8N, ?=4 ,一共为32)
-
链表:
对于嵌套内部类(非静态类)例如Node 类.还需要一个额外的8字节(用于指向外部类)
public class Node{
private Node next;
private Item item;
public class Item{
... }
}
此时内存大小计算为 :
| 内存组成 |
|---|
| 对象开销[16] |
| 额外开销[8] |
| Item [引用 8] |
| Next [引用 8] |
| Padding =? |
16+8+8*2+?=40 (8N)
所以padding =0,一共内存占40byte
-
数组:
一个原始类型数据的数组一般需要24个字节的头信息(16字节对象开销+4字节保存长度+4字节填充) ,再加上保存值的所需内存 .
例如一个含有N个int 数组 内存为 (24+4N+padding) 字节 会保持8N.
一个N的double 数组 内存为 (24+8N+padding)
一个对象的数组就是一个对象的引用的数组.需要额外加上引用所需内存;
例如:一个含有N个Date的数组.
内存=24+(8 [对象引用大小]+32[对象本身内存大小])N
