Backto Algo Index

优秀的代码有两个硬性指标

• 快 : 代码运行的速度更快 -> 时间复杂度分析
• 省 : 代码更节省存储空间 -> 空间复杂度分析

复杂度分析是整个数据结构与算法的精髓, 要时刻拿着这把戒尺, 去衡量自己遇到的代码, 这个够快么? 够省么? 怎么能更快呢? 怎么能更省呢?

大 O 复杂度表示法

代码的运行时间, 是运行的指令次数成正比.

$T(n) = O(f(n))$T(n)=O(f(n))

• $T(n)$T(n) 是所有代码的执行时间
• $n$n 表示数据规模的大小
• $f(n)$f(n) 表示一行一行代码执行次数的总和

可见, Big-O 分析法不表示具体代码真正的执行时间, 而是表示代码执行时间随着数据规模增长的变化趋势.

常见的时间复杂度实例分析

O(1) : 常量阶

所有的代码的执行次数是一个定值, 无论多大多小, 只要不随 $n$n 的增大而增大, 这样的代码复杂度就是 $O(1)$O(1)

// O(1)
int k = 100;

// O(1)
const long long f = 10000000000000000000000000000;
for(int i = 0; i < f; ++i)
{
}

O(log n) : 对数阶

数据从起始状态, 以乘法的形式向上生长去接近 $n$n, 其时间复杂度就是 $O(\log n)$O(logn)

int i = 1;
while(i <= n)
	i = i * 2;

$i$i 是以 $2^0$20 为起始, 跳着 $2^1, 2^2, ..., 2^k, ...2^x$21,22,...,2k,...2x 的台阶逐步接近 $n$n 的, 其跳跃的次数, 自然就是 $\log_2 n$log2​n, 即使是 $i = i*3$i=i∗3, $i = i * 1000$i=i∗1000, 由于 $\log_k n = \log_k 2 * \log_2 n$logk​n=logk​2∗log2​n, 前面的常数项都可以约去, 所以, 统一用 $O(\log n)$O(logn) 表示

O(n) : 线性阶

与 $n$n 成正比, 自然就是 n 层循环啦

int i = 0;
while( i < n)
	printf("%d \n",i);

O (nlog n) : 线性对数阶

$O (n \log n)$O(nlogn) 自然就是 一段 $O(\log n)$O(logn) 的代码, loop 了 $n$n 次. 之所以,这个复合府再度单提出来, 是因为这个 $O(n \log n)$O(nlogn) 复杂度很常见, 比如 归并排序, 快排等等.

O($n^k$nk) : k 次方阶, $O(n^2)$O(n2) : 平方阶, $O(n^3)$O(n3):立方阶

展开就是 $n \times n \times n \times ... \times n$n×n×n×...×n, 就是 $k$k 层循环的嵌套嘛!

O($2^n$2n) : 指数阶

O ($n!$n!) : 阶乘阶

常用的空间复杂度分析实例

空间复杂度的分析和事件复杂度的分析是一样一样滴,

• $O(1)$O(1) : 只要分配常量个存储单元, 都是 $O(1)$O(1), 不管是 1 个 int , 还是 10000 个对象
• $O(n)$O(n) : 按 $n$n 的大小分配空间

// O(1)
int arr[9] = {0};

// O(n)
int arr[] = new int[n];

---

Ref

• the Big-O Cheatsheet : 很棒的图表