它约等于算法中基本操作重复执行的次数(循环或递归的次数)不是行数!!!
最多为O(5)!!!
用乘号连接(在嵌套循环中),时间复杂度用O( )表示。(O( )只是符号)
如:
for(int = 1;i<=n*10/8;i++){
for(int j=1;j<=n*10/2;k++){
for(int k=1;k<n*10;k++){
//待填入……
}
}
}
时间复杂度为:(n*10/8)*(n*10/2)*(n*10)
= (那里是n的三次方,没打出来)
=O(n3)
当n很大时,系数对结果的影响非常小。
如没有循环(不包括判断),那么时间复杂度一般为O(1)。
如:
for(int i=l+1;i<=r;i++)
中时间复杂度为O(R-L)!!!
在信息学奥赛中1秒内运算次数约为107。
一般情况下: O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)
O(n) | n<=1000000 |
O(nlogn) | n<=100000 |
O(n2) | n<=1000 |
O(n3) | n<=100 |
O(2n) | n<=20 |
时间复杂度 适用范围
标签:10,int,复杂度,C++,次数,时间,讲解,n3 From: https://blog.csdn.net/2401_89060659/article/details/143835516