时间复杂度的计算问题汇总

写在前面，引用《大话数据结构》——“理解大O并不难，难的是对数列的一些相关运算，这更多的考察的是你的数学知识和能力。”

算法的时间复杂度：用来度量算法的运行时间，记作: T (n) = O (f (n))。 它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f (n) 来描述。

复杂度的大小

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

口诀：常对幂指阶
复杂度越小，则说明你的代码越好

时间复杂度简单来说就是估算指令执行了多少次。

method1(){
    System.out.println("祝你看了这篇文章"); //执行1次
    System.out.println("诸事顺利"); //执行1次
    System.out.println("万事如意"); //执行1次
}
// 1+1+1 = 3

method2(){
    for(int i=0;i<5;i++){ //i=0 执行1次；i<5 判断5+1次,等于5时判断后退出；i++ 执行5次
        System.out.println("好运连连"); //执行5次
    }
}  //1+(5+1)+5+5 = 17

method3(int n){
    for(int i=0;i<n;i++){ //i=0 执行1次；i
        System.out.println("好运连连"); //执行n次，你会有n次好运哦
    }
} //1+(n+1)+n+n = 3n+2

method4(int n){
    for(int i=0;i<n;i++){  //i=0 执行1次；i
        //整个内层循环 执行n次
        for(int j=0;j<n;j++){ //j=0 执行1次；j
            System.out.println("好运连连"); //执行n次
        }
    }} //外层2n+2; 复杂度：2n+2+n*(3n+2) = 3n^2+4n+2

method6(int n){
    while((n=n/2)>0){
        System.out.println("好运连连");
    }
}
/*
假如：n=8 ; 8/2=4 执行1次；4/2=2 执行1次；2/2=1 执行1次；1/2=0.5=0 执行判断后，不进入循环体。
    所以循环体执行3次，判断执行3+1次；2^3=8---->log2(8)=3
    n=16 ; 16/2=8 执行1次；8/2=4 执行1次；4/2=2 执行1次；2/2=1 执行1次；
    所以循环体执行4次，判断执行4+1次；2^4=16---->log2(16)=4
    所以时间复杂度：(log2(n)+1)+log2(n) = 2log2(n)+1
    log2(n):循环体内执行次数，(log2(n)+1):判断语句执行次数
*/

method8(int n){
    for(int i=1;i<n;i=i*2){
        for(int j=0;j<n;j++){ //j=0 1次，j
            System.out.println("好运连连");// n次
        }
    }}
    /*
    i=1, i=1*2=2, i=1*2*2=4, i=1*2*2*2=8 ;  所以i

method9(int n){
    for(int i=0;i<n;i++){ // i=0 执行1次；i
        for(int j=i;j<n;j++){
            System.out.println("好运连连");
        }
    }}
    /*
     i=0,内部执行n次；i=1,内部执行n-1; i=2,内部执行n-2;…… i=n-1,内部循环执行1次。等差数列
     =n*(n+1)/2 = (1/2)n^2+(1/2)n; 
     所以内部循环除了j

以上用大O表示法来简化表示时间复杂度：
method1: 1+1+1 = 3 即O(1)
method2: 1+(5+1)+5+5 = 17 即O(1)
method3: 3n+2 即O(n)
method4: 3n^2+4n+2 即O(n^2)
method6: 2log2(n)+1 即O(log2(n))
method8: 2nlog2(n)+4log2(n)+2 即O(nlog2(n))
method9: 2n+2+4*((1/2)n^2+(1/2)n)+1 即O(n^2)

解题方法：
对for(i = 0; i < n; i++）：起始为零加一次，（大）扩前比后多一次；
一般的：
1.设该语句执行x次终止;
2.找出第x次的表达式；
3.由终止条件x = f(n);

根式阶（一般都是变量的平方）

x = 0;
while(n >= (x + 1) * (x + 1))
     x = x+1;

解：对于循环体，我们只考虑小括号内的执行次数。因为小括号内的比较大。按步骤来
1.设小括号的语句执行x次终止
2.第一次：n > 0 × 0 n > 0 × 0n>0×0;
第二次: n > 1 × 1 n > 1 × 1n>1×1;
…
第x次:n > x ∗ x
3.第x次时终止，即x^2 即x>n^1/2

平方阶

method9(int n){
    for(int i=0;i<n;i++){ // i=0 执行1次；i
        for(int j=i;j<n;j++){
            System.out.println("好运连连");
        }
    }}

method9: 2n+2+4*((1/2)n^2+(1/2)n)+1 即O(n^2)

对数阶（一般变量都是乘或者除一个常数）

method6(int n){
    while((n=n/2)>0){
        System.out.println("好运连连");
    }
}

method6: 2log2(n)+1 即O(log2(n))

method8(int n){
    for(int i=1;i<n;i=i*2){
        for(int j=0;j<n;j++){ //j=0 1次，j
            System.out.println("好运连连");// n次
        }
    }}

method8: 2nlog2(n)+4log2(n)+2 即O(nlog2(n))

线性阶

method3(int n){
    for(int i=0;i<n;i++){ //i=0 执行1次；i
        System.out.println("好运连连"); //执行n次，你会有n次好运哦
    }
} //1+(n+1)+n+n = 3n+2

阶乘阶

int m = 1,n = 0,i = 0;
    for(i = 0; i <= n; i++)//语句1
    {
        m *= i;
    }
    for(i = 0; i < m; i++)//语句2
    {
        n++;
    }

语句1
易知语句1执行了n+2次；（有i<=n再加一次）
时间复杂度为O ( n )
语句2
易知语句2执行了m次；
而语句1中的循环体知m=n!
所以时间复杂度为O ( n ! )

如何较快看出时间复杂度
其实对于时间复杂度，我们一点也不关心语句执行了多少次，只关心语句执行次数的量级。
我们只要知道
循环变量i从一直加到n是线性阶，
循环体中i成倍增长为对数阶，
i在循环体内线性增加，在条件中倍增为根式阶，
记住几个特例，就可以快速知道结果。

口诀：
点增平方根式阶（循环体内变量（加常数）的平方）
变量线增对数阶（变量乘除常数）

参考资料：
https://blog.csdn.net/qq_45652428/article/details/112006865?spm=1001.2014.3001.5502
https://blog.csdn.net/qq_46499375/article/details/109458230