公式:T(n) = O(f(n))
其为渐进分析法。 我们常用大O表示法表示时间复杂度,注意它是某一个算法的时间复杂度。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。此外,一个问题本身也有它的复杂度,如果某个算法的复杂度到达了这个问题复杂度的下界,那就称这样的算法是最佳算法。
n是问题规模,它代表着要处理的数据量,举例:对1000个数排序,1000是数据量.
f(n)是代码的运行工作量,即算法的基本操作重复执行的次数, 举例:
#include <stdio.h> int main() { int i; for(i = 1; i <= 10; i++) printf("*"); return 1; }
f(10) = 10.
O(), O是常量, 可以理解为忽略不计的那部分。 比如:O(n^3+3n+2)可以写成O(n^3)。