时间复杂度计算

时间复杂度计算

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

博文链接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");
    }
}

方法的执行次数约为n2+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)n #

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

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

时间复杂度实验

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

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

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

标签

评论

this is is footer