算法
2025-09-09 本文已影响0人
努力生活的西鱼
算法复杂度
引入算法复杂度的目的
- 度量算法的效率和性能
大O表达式
- 算法效率与性能的近似表示(定性描述)
- 算法执行时间与问题规模的关系
表示原则
- 忽略所有对变化趋势影响较小的项，例如多项式忽略高阶项之外的所有项
- 忽略所有与问题规模无关的常数，例如多项式的系数
标准算法复杂度类型
- O(1)：常数级，表示算法执行时间与问题规模无关
- O(n)：线性级，表示算法执行时间与问题规模成正比
- O(n2)：平方级，表示算法执行时间与问题规模的平方成正比
- O(log(n))： 对数级，表示算法执行时间与问题规模的对数成正比
- O(sqrt(n)）：平方根级，表示算法执行时间与问题规模的平方根成正比
O(n)
for(i = 0; i < n; i++)
cout << "No." << i << ":Hello, World!"
O(n2)
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
cout << ":Hello, World!"
O(n2)
for(i = 0; i < n; i++)
for(j = i; j < n; j++)
cout << ":Hello, World!"
