时间复杂度计算

注本文代码和思路都来源于下博文，作者只是练习了一遍，并做了自己的整理

博文链接https://www.jianshu.com/p/f4cca5ce055a

时间复杂度计算例子

常数阶

下代码中方法的时间复杂短为常数阶

int aFunc(void) {
    printf("Hello, World!\n");      //  需要执行 1 次
    return 0;       // 需要执行 1 次
}

以一句代码一次，方法中代码需要执行2次。

线性阶

下代码中方法的时间复杂度为线性阶

int aFunc(int n) {
    for(int i = 0; i<n; i++) {  //准确的来说是 ( 1 + (n+1) + (n) ) 
        printf("Hello, World!\n");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

以上代码需要执行(3n+3)次，在非常数阶中，常数可以被忽略掉，因此上代码的执行次数被说为3n，为线性阶。

二次阶

下代码的时间复杂度为二次阶

void aFunc(int n) {
    // 第一部分时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");
        }
    }
    // 第二部分时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
        printf("Hello, World!\n");
    }
}

方法的执行次数约为n^{2+n，指数阶和线性阶同时在时，若指数阶指数大于2，可忽略线性阶，因此方法执行次数约为n2阶，时间复杂度为二次阶}

二次阶2

下代码的时间复杂度为二次阶

void aFunc(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            printf("Hello World\n");
        }
    }
}

执行次数

T(n)=n+(n-1)+(n-2)+(n-3)+...+(1)
    ->n^2 - 1/2*(n+1)*n
    ->n^2/2-n/2

方法的时间复杂度约二次阶

二次阶3

下代码的执行次数计算会绕一些，但是也算简单#是我唐突了##是真的算不来##答案是：通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^{n，同时当} n > 4 时 T(n) >= (3/2)ⁿ #

long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

方法的时间复杂度为（3/2)^{2实际上更常见是表示为2n阶。}

时间复杂度实验

下代码中方法fun的时间复杂度为2ⁿ
** 代码如下**

public class Main{
    public static long fun(int n) {
        if(n==1 || n==2) {
            return 1L;
        }
        return fun(n-1)+fun(n-2);
    }
    public static void main(String[] args) {
        
        for(int i=1;i<60;i+=10) {
            long time1=new Date().getTime();
            System.out.println("i="+i+"\t返回值："+fun(i));
            System.out.println("运行耗时+"+(new Date().getTime()-time1)+"ms");
        }
    }
}

我们分别测试一下数据1,11,21,31,41,51,61,71的时间消耗，程序输出如下：

控制台输出

i=1 返回值：1
运行耗时+0ms
i=11    返回值：89
运行耗时+0ms
i=21    返回值：10946
运行耗时+0ms
i=31    返回值：1346269
运行耗时+10ms
i=41    返回值：165580141
运行耗时+857ms
i=51    返回值：20365011074
运行耗时+106505ms

这个代码实际上是斐波那契数列问题的解题代码，我们使用循环来代替递归，下代码中fun的时间复杂度为线性阶
代码如下

public class Main{
    public static long fun(int n) {
        if(n==1 || n==2) {
            return 1L;
        }
        int i=3;  //从第三项起开始
        int f=1,s=1,t;
        while(i++<=n) {
            t=s+f;
            f=s;
            s=t;
        }
        return s;
    }
    public static void main(String[] args) {
        
        for(int i=1;i<60;i+=10) {
            long time1=new Date().getTime();
            System.out.println("i="+i+"\t返回值："+fun(i));
            System.out.println("运行耗时+"+(new Date().getTime()-time1)+"ms");
        }
    }
}

** 控制台输出**

i=1 返回值：1
运行耗时+1ms
i=11    返回值：89
运行耗时+0ms
i=21    返回值：10946
运行耗时+0ms
i=31    返回值：1346269
运行耗时+0ms
i=41    返回值：165580141
运行耗时+1ms
i=51    返回值：-1109825406
运行耗时+0ms

在这里我们可以说递归的表现远不如循环，也可以说时间复杂度为指数阶和线性阶的代码的代码的差异，这都没有错，只是我们应当知道其中原理，并明白自己下一个判断是依据在何。