1.O(1)
在这个案例中, println语句执行1次, return 0语句执行1次,语句共执行2次。常数的时间复杂度为O(1)。
int func1(){
println("Hello,world");//执行1次
return 0;
}
2.O(n)
在这个案例中,int i语句执行1次,i<n语句执行n+1次(最后1次是不符合判断),i++语句执行n次 ,println语句执行1*n次, return 0语句执行1次,语句共执行3n+3次。时间复杂度为O(n)。
int func2(int n){
for(int i=0;i<n;i++){
println("Hello,world");
}
return 0;
}
3.O(n^2)
在这个案例中,for(int j;j<n;i++)循环大概执行n次,for(int i;i<n;i++)循环大概执行n次, return 0忽略不计,语句共执行n*n次。时间复杂度为O(n^2)。
int func3(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
println("Hello,world");
}
return 0;
}
4.O(n^2)
在这个案例中,i=0时,for(int j=i;j<n;j++)大概执行n次;i=1时,for(int j=i;j<n;j++)大概执行n-1次;i=2时,for(int j=i;j<n;j++)大概执行n-2次.......return 0忽略不计,语句共执行(n-1)+(n-2)+(n-3)+......+2+1=n*(n+1)/2次。时间复杂度为O(n^2)。
int func4(){
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
println("Hello,world");
}
return 0;
}
5.O(logn)
在这个案例中,i=1,i=2,i=4,i=8......i=n,return 0忽略不计,语句共执行log2n次。时间复杂度为O(logn)。
int func4(){
for(int i=1;i<n;i*=2){
println("Hello,world");
return 0;
}
标签:语句,return,案例,int,复杂度,如何,计算,执行
From: https://www.cnblogs.com/tsin/p/17606580.html