参考：

时间复杂度

常见的时间复杂度

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n²)
  • 立方阶O(n³)
  • K次方阶O(n^k)
  • 指数阶(2^n)

    常数阶O(1)

    1. int i = 1;
    2. int j = 2;
    3. ++i;
    4. j++;
    5. int m = i + j;

线性阶O(n)

  1. for(i=1; i<=n; ++i)
  2. {
  3.    j = i;
  4.    j++;
  5. }

对数阶O(logN)

  1. int i = 1;
  2. while(i<n)
  3. {
  4.     i = i * 2;
  5. }

i 乘以 2 的 n 次方 小于 n，属于对数函数

线性对数阶O(nlogN)

对数函数 加一个 循环

  1. for(m=1; m<n; m++)
  2. {
  3.     i = 1;
  4.     while(i<n)
  5.     {
  6.         i = i * 2;
  7.     }
  8. }

平方阶O(n²)

两个循环

  1. for(x=1; i<=n; x++)
  2. {
  3.    for(i=1; i<=n; i++)
  4.     {
  5.        j = i;
  6.        j++;
  7.     }
  8. }

空间复杂度

空间复杂度 O(1)

  1. int i = 1;
  2. int j = 2;
  3. ++i;
  4. j++;
  5. int m = i + j;

空间复杂度 O(n)

第一行，决定了 空间 随 n变化情况。

  1. int[] m = new int[n]
  2. for(i=1; i<=n; ++i)
  3. {
  4.    j = i;
  5.    j++;
  6. }