时间复杂度

时间复杂度

前言

我们在程序开发过程中为了衡量一个算法的好坏制定了两个标准时间复杂度和空间复杂度，因为程序运行的时间长短和占用内存的大小直接影响到程序的执行效率。

但我们需要注意程序运行的时间长短不仅仅取决于代码，还有运行环境、硬件、数据量等因素影响，什么意思呢？

• 硬件：当一段相同的代码同时在2C4G和4C8G上的机器运行因为机器计算力不一样，所以程序运行时间大概率不同（特别是代码计算量大时）。

• 运行时环境：当一台机器上大部分资源被其它服务所占用，另外一台机器上面没有其它服务，那么一段相同的代码在两个硬件相同机器上执行时间长短会不一样。

• 数据量：一段相同的代码定义入参为n（或输入规模），代码片段会循环n次，那么n=1和n=1w执行时间长度上肯定不一样。

所以说时间复杂度并不能直接等于代码运行的时间长短，这里的时间复杂度指的是代码基本操作执行的次数。

基本操作执行次数

所有案例只考虑主要流程的执行次数

案例一

如存在一个面包长10cm，每2分钟只能吃1cm，那么吃完这个面包需要多长时间呢？

很明显答案为10*2=20分钟，所以当吃面包的速度不变的情况下面包长n cm那么就需要花费2n的时间才能吃完面包，这里可以记作T(n) = 2n。

public void method1(int n){
    for (int i = 0; i < n; i++) {
        System.out.println("吃一口面包");
        System.out.println("吃完了~");
    }
}

1
2
3
4
5
6
7

案例二

假设再存在一个面包长16cm，每过5分钟吃掉该面包的一半，那么面包变为1cm需要花费多长时间？

这个计算稍微复杂点，第五分钟吃掉8cm、第十分钟吃掉4cm、第十五分钟吃掉2cm、第二十分钟吃掉第1cm，还剩1cm，就是将面包长度不断的做等分，这就是数学中的对数，这里答案就是5 * log2(16) = 20，当面包长度为n时这里可以记作T(n) = 5logn。

public void method2(int n){
    for (int i = n; i > 1; i=i/2) {
        System.out.println("吃一口面包");
        System.out.println("吃一口面包中2");
        System.out.println("吃一口面包中3");
        System.out.println("吃一口面包中4");
        System.out.println("吃完了~");
    }
}

1
2
3
4
5
6
7
8
9
10

案例三

假设存在一个面包长10cm，吃掉第一个1cm需要1分钟，吃掉第二个1cm需要2分钟，吃掉第三个1cm需要3分钟，那么一个面包吃完需要多少分钟呢？

这其实就是1到10的累加，所以当面包长度为n时需要的时间就可以记作T(n) = (n / 2) * (1+n) ，变化为T(n) = 0.5n + 0.5n²。

public void method3(int n){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j