算法

算法复杂度

引入算法复杂度的目的

1. 度量算法的效率和性能

大O表达式

1. 算法效率与性能的近似表示(定性描述)
2. 算法执行时间与问题规模的关系

表示原则

1. 忽略所有对变化趋势影响较小的项，例如多项式忽略高阶项之外的所有项
2. 忽略所有与问题规模无关的常数，例如多项式的系数

标准算法复杂度类型

• 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!"