算法的时间复杂度咋计算

Question

时间复杂度的计算

表示方法

我们一般用“大 O 符号表示法”来表示时间复杂度：T(n) = O(f(n)) n 是影响复杂度变化的因子，f(n)是复杂度具体的算法。

常见的时间复杂度量级

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

常数阶 O(1)

int a = 1;
int b = 2;
int c = 3;

线性阶 O(n)

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

对数阶 O(logN)

int i = 1;
while(i < n) {
  i = i * 2;
}

可以看到每次循环的时候 i 都会乘 2，那么总共循环的次数就是 log2n，因此这个代码的时间复杂度为 O(logn)。

线性对数阶 O(nlogN)

for(m = 1; m < n; m++) {
  i = 1;
  while(i < n) {
    i = i * 2;
  }
}

线性对数阶 O(nlogN) 其实非常容易理解，将时间复杂度为 O(logn)的代码循环 N 遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了 O(nlogN)。

平方阶 O(n²)

for(x = 1; i <= n; x++){
   for(i = 1; i <= n; i++) {
     j = i;
     j++;
  }
}

把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

空间复杂度计算

创建的变量的数量

空间复杂度 O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

空间复杂度 O(n)

int[] m = new int[n]
for(i = 1; i <= n; ++i) {
   j = i;
   j++;
}

这段代码中，第一行 new 了一个数组出来，这个数据占用的大小为 n，后面虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)。

案例分析

二分查找的迭代算法

int BinarySearch(int arr[], int len, int num)
{
  assert(arr);

  int left = 0;

  int right = len - 1;

  int mid;

  while (left <= right)
  {
    mid = left + (right - left) / 2;

    if (num > arr[mid])
    {
      left = mid + 1;
    }
    else if (num < arr[mid])
    {
      right = mid - 1;
    }
    else
    {
      return mid;
    }
  }
  return -1;
}

二分查找时，每次都在原有查找内容进行二分，所以时间复杂度为 O（logn）

因为变量值创建一次，所以空间复杂度为 O（1）

二分查找的递归算法

int BinarySearchRecursion(int arr[5], int lef, int rig,int aim)
{
  int mid = lef + (rig - lef) / 2;

  if (lef <= rig)
  {
    if (aim < arr[mid])
    {
      rig = mid - 1;
      BinarySearchRecursion(arr, lef, rig, aim);
    }
    else if (arr[mid] < aim)
    {
      lef = mid + 1;
      BinarySearchRecursion(arr, lef, rig, aim);
    } 
    else if (aim == arr[mid])
    {
      return mid;
    }
  }
  else
    return -1;
}

时间复杂度为 O（log2 n）

每进行一次递归都会创建变量，所以空间复杂度为 O（log2 n）

斐波那契数列的迭代算法

int FeiBoNaCciInteration(int a,int b,int num)
{
  int c;

  if (num <= 0)
    return -1;

  else if (num == 1)
    return a;

  else if (num == 2)
    return b;

  else
  {
    while (num - 2)
    {
      c = a + b;
      a = b;
      b = c;
      num--;
    }
    return c;
  }
}

时间复杂度 O（n)

空间复杂度为 O（1）

斐波那契数列的递归算法

int FeiBoNaCciRecursion(int num)
{
  if (num < 0)
    return -1;

  if (num <= 2 && num > 0)
    return 1;

  else
    return FeiBoNaCciRecursion(num - 1) + FeiBoNaCciRecursion(num - 2);

}

时间复杂度为 O（2^n）

空间复杂度为 O（n）