Pan's RD

Appearance

时间复杂度 ​

计算时间复杂度通常需要两个步骤：1.根据(或推断)算法函数的时间增长趋势，得出其操作数函数。2.判断操作数函数的渐进上界。

1. 时间增长趋势 ​

TIP

通常将线性时间复杂度记为：O(n),表示标识算法操作次数的函数的*渐进上界*。因此想获得算法的时间复杂度，需要先计算出算法的操作数函数T(n)。

🎉一些推算操作数的技巧：

  1. 忽略T(n)中的常数项。因为它们都与n无关，所以对时间复杂度不产生影响。
  2. 省略所有系数。例如，循环2n次、 3n+1次等，都可以简化记为n次。
  3. 循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积，每一层循环依然可以分别套用第 1. 点和第 2. 点的技巧。
rust
 fn algorithm(n: i32) {
        let mut a = 1;     // +0（技巧 1）
        a = a + n;        // +0（技巧 1）

        // +n（技巧 2）
        for i in 0..(5 * n + 1) {
            println!("{}", 0);
        }

        // +n*n（技巧 3）
        for i in 0..(2 * n) {
            for j in 0..(n + 1) {
                println!("{}", 0);
            }
        }
}
T(n)=n2+n

2. 判断渐进上界 ​

TIP

时间复杂度由T(n)中最高阶的项来决定,应为当n趋于无穷大是,最高阶对时间增长的趋势的影响是其他项所不能相比的。

一些操作数对应的时间复杂度

操作数时间复杂度
1000000O(1)
2nO(n)
3n+2O(n)
n^2 + 2n +1o(n^2)
n^3 + 2n^2 + n + 10O(n^3)
2^n + 10000n^2O(2^n)

因此该算法的的时间复杂度:

O(n)<==>O(n2)

3. 常见时间复杂度类型 ​

时间复杂度类型是根据输入数据n的大小与算法执行时间(趋势)的变化来决定的。

常见时间复杂度类型图

3.1 常数阶O(1) ​

当算法的运行时间跟输入数据n无关时，算法属于常数阶。

rust
      fn alog(n: i32) -> i32 {
        println!("{}", 0);  //打印函数的执行时间固定，因此该算法的时间复杂度是常数阶。
      }
  
      fn alog(n: i32) -> i32 {
        for i in 0..1000 {
            println!("{}", i);  //虽然打印程序需要循环1000次，但打印函数的执行时间固定，与输入数据n无关，因此该算法的时间复杂度是常数阶。
        } 
      }

3.2 对数阶O(log n) ​

当算法的运行时间跟输入数据n的log成正比时，算法属于对数阶。

rust
   /* 对数阶（循环实现） */
   fn logarithmic(mut n: i32) -> i32 {
       let mut count = 0;
       while n > 1 {
           n = n / 2;
           count += 1;
       }
       count
   }

3.3 线性阶O(n) ​

当算法的运行时间跟输入数据n成正比时，算法属于线性阶。

rust
    fn linear(n: i32) -> i32 {
        let mut count = 0;
        for i in 0..n {
            count += 1
        }
    }

3.4 线性对数阶 ​

线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为 O(n)和O(log n) 相关代码如下：

rust
    /* 线性对数阶 */
    fn linear_log_recur(n: i32) -> i32 {
        if n <= 1 {
            return 1;
        }
        let mut count = linear_log_recur(n / 2) + linear_log_recur(n / 2);
        for _ in 0..n as i32 {
            count += 1;
        }
        return count;
    }

3.5 平方阶 ​

平方阶的操作数量相对于输入数据大小n以平方级别增长。平方阶通常出现在嵌套循环中，外层循环和内层循环的时间复杂度都为O(n)。因此总体的时间复杂度为：O(n^2)

rust
    fn square(n: i32) -> i32 {
        let mut count = 0;
        for i in 0..n {
            for j in 0..n {
                count += 1;
            }
        }
    }

3.6 指数阶 ​

生物学的“细胞分裂 ”是指数阶增长的典型例子：初始状态为1个细胞，分裂一轮后变为2个 ，分裂两轮后变为4个，以此类推，分裂n轮后有 2^n个细胞。时间复杂度为2^n

rust
    /* 指数阶（循环实现） */
    fn exponential(n: i32) -> i32 {
        let mut count = 0;
        let mut base = 1;
        // 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
        for _ in 0..n {
            for _ in 0..base {
                count += 1
            }
            base *= 2;
        }
        // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
        count
    }

3.7 阶乘 ​

阶乘阶对应数学上的“全排列 ”问题。给定 n互不重复的元素，求其所有可能的排列方案，方案数量为：

n!=n∗(n−1)∗(n−2)∗...∗1
rust
    /* 阶乘阶（递归实现） */
    fn factorial_recur(n: i32) -> i32 {
        if n == 0 {
            return 1;
        }
        let mut count = 0;
        // 从 1 个分裂出 n 个
        for _ in 0..n {
            count += factorial_recur(n - 1);
        }
        count
    }