算法的时间复杂度的公式理解

公式: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)。  

算法的时间复杂度的公式理解

上一篇:[Leetcode]--Word Ladder


下一篇:【Java】String和Date、Timestamp之间的转换