算法(4th ed)(158):基础——算法分析 6.4

阅读数:7 2019 年 11 月 6 日 07:53

算法(4th ed)(158):基础——算法分析 6.4

(增长数量级的分类)

我们在实现算法时使用了几种结构性的原语(普通语句、条件语句、循环、嵌套语句和方法调用),所以成本增长的数量级一般都是问题规模 $N$ 的若干函数之一。表 1.4.7 总结了这些函数以及它们的称谓、与之对应的典型代码以及一些例子。

表 1.4.7 对增长数量级的常见假设的总结

描述 增长的数量级 典型的代码 说明 举例
常数级别 1 a = b + c; 普通语句 将两个数相加
对数级别 $\log N$ (请见 1.1.10.2 节,二分查找) 二分策略 二分查找
线性级别 $N$
double max = a[0];
for (int i = 1; i < N; i++)
if (a[i] > max) max = a[i];
循环 找出最大元素
线性对数级别 $N\log N$ [ 请见算法 2.4] 分治 归并排序
平方级别 $N^2$
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
if (a[i] + a[j] == 0)
cnt++;
双层循环 检查所有元素对
立方级别 $N^3$
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++)
if (a[i] + a[j] + a[k] == 0)
cnt++;
三层循环 检查所有三元组
指数级别 $2^N$ (请见第 6 章) 穷举查找 检查所有子集

评论

发布