时间复杂度如何计算？-526互联

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忽略不计，语句共执行log₂n次。时间复杂度为O(logn)。

int func4(){
    for(int i=1;i<n;i*=2){
        println("Hello,world");
    return 0;
}