算法分析方法

基础的时间分析与空间分析

作者 QIFAN 日期 2017-01-04
算法分析方法

分析类型

best case :成本的下限 lower bound 。没有任何情况能比其好。
worst case : 成本的上限 upper bound 。没有任何情况能比其差,就像保质期一样提供了一个保证。
average case : 成本的期望值。对于乱序输入的一个平均值,通常用于预测表现。

例子 2 - SUM binary search
best case ~N ~1
worst case ~N ~logN
average case ~N ~logN

常用符号

  1. Tilda ~ :
    • 最大影响项,通常是变动幅度最大的。
    • 如 $10N^3 + 20NlogN$ 可以缩写为 $~10N^3$
    • 大概的模型
  2. Big theta
    • 取决增长项的一个渐近。
    • 如 $10N^3 + 20NlogN$ 可以写为 $Θ(N^3)$
    • 用于对算法进行分类
  3. Big O
    • $Θ(N^2)$ 或更小
    • $O(N^2)$ 可以代表 $10N^2 + 20NlogN$ , $20NlogN$ , $2NlogN$
    • 用于优化算法的上限
  4. Big Omega
    • $(N^2)$ 或更大
    • $Ω(N^2)$ 可以代表 $10N^2$ , $20N^3$ , $2N^4logN + N$
    • 用于优化算法的下限

常见 big O

从左到右增长速度依次增大。

$O(1)$ $O(log n)$ $O(n)$ $O(n log n)$ $O(n^2)$ $O(2^n)$ $O(n!)$
Constant Logarithmic Linear Linearithmic Quatratic Exponential Factorial

空间分析

bit : 1 或 0
byte : 8 bits
MB : 一百万或 $2^20$ 字节
GB : 十亿或 $2^30$ 字节

64-bit 机器中通常用 8 个字节的指针。

下面是不同类型数据结构占用的空间:

Type bytes
primitive type ⬇️
boolean 1
byte 1
char 2
int 4
float 4
long 8
double 8
一维数组 ⬇️
char[] ~2N
int[] ~4N
double[] ~8N
二维数组 ⬇️
char[][] ~2MN
int[][] ~4MN
double[][] ~8MN
Object ⬇️
object overhead 16
引用 8
填充位( padding ) 每个对象内存规定要被 8 整除

空间计算举例

public class Box {
int size;
double weight;
Card card1;
Card card2;
...
}
类型 内存
object overhead 16
size 4(int)
weight 8(double)
card1 8(reference)
card2 8(reference)
当前总计 44
padding 4
总计 48


相关文章算法基础梳理



更新历史

  • 2017.01.04 初稿
  • 2017.01.05 增加「常见 big O」
  • 2017.01.06 代码转移