算法时间复杂度的记法是什么?
求程序的时间复杂度?
大O
如何分析一个算法的时间复杂度?
1.用常数1取代运行时间中的所有加法常数。
2.再修改后的运行次数函数中,只保留最高阶项。
3.最高阶项存在且不是1,则去除与这个项相乘的常数,得到的最后结果就是大O阶。
实例:分支阶:O(1)。循环n次的线性阶:O(n2)。嵌套循环的平方阶:O(n3)。对数阶:
int i = 1, n = 100;
while(i < n){
i = i * 2;
}
由于运行次数为
2x = n
x=log(2)n
所以时间复杂度为:O(logn)
网友评论