时间复杂度

基础

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作

T(n)=O(f(n))

它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。

语句的频度是指该语句重复执行的次数。

  • O(1) 常量阶
  • O(n) 线性阶
  • O(n²) 平方阶
  • O(log n) 对数阶
  • O(2²) 指数阶
  • O(nlog2 n) 线性对数阶

我们应该尽可能选择多项式阶O(n^k)的算法,而不希望使用指数阶算法。

时间复杂度由小到大:

O(1) < O(log2 n) < O(n) < O(nlog2 n) < O(n²) < O(2^n) < O(n!)

计算

容易计算的方法是:看看有几重循环,只有一重循环则时间复杂度为O(n),二重则为O(n²),以此类推。如果有二分则为O(log n),二分例如有快速幂、二分查找, 如果一个for循环套一个二分,那么时间复杂度为O(nlog n)。

快速幂: 快速算底数的n次幂,其时间复杂度为O(log2 n)。

N = a^x --> loga N = x

例如:

for(int i = 0; i < n; i++) {
    // O(n)
}

//----------------
for(int i = 0; i < n; i = 2*n){
    // O(log2 n)
}

//----------------
int count = 1;
while(count < n) {
    count = count * 2;   // O(log2 n)
}

//----------------
for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
        // O(n*m)
    }
}

//----------------
for(int i = 0; i < n; i++) {
    while(count < n) {
        count = count * 2;  // O(nlog2 n)
    }
}

//----------------
int i,j = 0;
for(i = 0; i < n; i++) {
    for(j = 0; j < n; j++) {
        // 当i=0时,内层执行了n次,i=1时,内层执行了(n-1)次,所以
        // n + (n-1) + (n-2) + ... + 1
        // = (n+1)/2 * n
        // = n²/2
        // 即 O(n²)
    }
}
Last Updated: 1/24/2019, 11:30:29 PM