我们在实现算法时使用了几种结构性的原语(普通语句、条件语句、循环、嵌套语句和方法调用),所以成本增长的数量级一般都是问题规模N的若干函数之一。总结如下:
- 描述:常数级别
- 增长的数量级:1
- 典型的代码:
a = b + c
- 说明:普通语句
- 举例:将两个数相加
- 描述:对数级别
- 增长的数量级:log N
- 典型的代码:二分查找
- 说明:
- 举例:
- 描述:线性级别
- 增长的数量级:N
- 典型的代码:
double max = a[0];
for (int i = 1; i < N; i++)
if (a[i] > max) max = a[i];
- 说明:循环
- 举例:找出最大元素
- 描述:线性代数级别
- 增长的数量级:N log N
- 典型的代码:``
- 说明:分治
- 举例:归并排序
- 描述:平方级别
- 增长的数量级:N²
- 典型的代码:
for (int i = 0; i < N; i++)
for (int j = i+1; j < N;j++)
if (a[i] + a[j] == 0) cnt++;
- 说明:双侧循环
- 举例:检查所有元素对
- 描述:立方级别
- 增长的数量级:N³
- 典型的代码:
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
- 典型的代码:``
- 说明:强句查找
- 举例:检查所有子集