时间复杂度 · Yubao-wss

时间复杂度:代码的总执行时间

int cal(int n) {
  int sum = 0;
  int i = 1;
    for (; i <= n; ++i) {
    sum = sum + i; 
  }
  return sum; 
}

CPU执行每行代码的时间unit_time

T(n) = 2n + 4

T(n) = O(2n+4)

一段代码执行时间与代码行数有关

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

int cal(int n) {
  int sum = 0;
  int i = 1;
  int j = 1;
  for (; i <= n; ++i) 
    j = 1;
  for (; j <= n; ++j) { 
      sum=sum+ i*j;
    } 
  }
}

3+2n+2n^2

T(n) = O(2n^2+2n+3)

T(n) = O(2n+4)

【大O时间复杂度只需要记录最大量级】

T(n) = O(n^2)

T(n) = O(n)

分析方法:

1.只关心循环次数最多的代码

代码中只有一个循环体

2.加法法则:总复杂度等于量量级最⼤的那段代码的复杂度

代码中有多个循环体

3.乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

复杂度量级分为两类:

多项式时间复杂度:

O(1)、O(n)、O(logn)、O（n^2)

O(1) : 常数级时间复杂度

只要代码不随n的增长变化，都属于O(1)常数级复杂度

int i = 1;

O(logn)、O(nlogn):对数时间复杂度

2^1 2^2 2^3 2^n….

log2n

for (; i <= n; ++i) {
  sum = sum + i; 
}

任意底数的对数都可换成以2为底

最终记为O(logn)

O(nlogn):快速排序、归并排序

O(m+n)

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
for (; i < m; ++i) {
    sum_1 = sum_1 + i;
}
  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }
  return sum_1 + sum_2;
}

O(m+n):由于m与n的数据规模不定，因此使用加法法则保留两者的复杂度

O(n^2)

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

非多项式时间复杂度:当n越来越大时，非多项式的时间复杂度急剧增加，因此非多项式的算法基本不用

O(2^n)

O(n!)

最好、最坏、平均时间复杂度

最好时间复杂度:

// n 表示数组 array 的⻓长度

int find(int[] array, int n, int x) {
    int i = 0;
    int pos = -1;
   for (; i < n; ++i) 
      if (array[i] == x) pos = i;
    }
  return pos;
}

T(n) = O(n)

int find(int[] array, int n, int x) {
    int i = 0;
    int pos = -1;
    for (; i < n; ++i) {
     if (array[i] == x) {
        pos = i
        break;
     }
    }
  return pos;
}

最好情况:O(1)

最坏情况:O(n)

平均情况:O(n)

时间复杂度:

常见时间复杂度:O(1)、O(n)、O(logn)、O(n^2)

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)

空间复杂度:代码的占用空间(需要的内存大小)

public static int sum(int n) {
   int count = 0;
    for (int i = 1; i <= n; i++) {
        count += i;
}
    return count;
}

sum(10)

O(1)

int sum(int n) {
  sum(n);
}

sum(10)

栈溢出异常:StackOverFlowError

时间复杂度 Yubao-wss

时间复杂度:代码的总执行时间