Tyrone 的博客

复杂度分析

发表于 更新于 分类于
本文字数： 2.9k 阅读时长 ≈ 3 分钟
复杂度分析

复杂度分析

复杂度分析是整个算法学习的基础和重点，当开发人员在编写代码时，可以粗略地估算代码的执行效率是非常重要的；

所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比，用公式可以表示为：

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

所以我们一般使用 大 O 时间复杂度表示法来表示时间复杂度；

时间复杂度

这里将使用网上找的几个例子来学习时间复杂度的计算：

例子一：

1
2
3
4
int func1(void) {
  printf("哈哈"); # 1 次
  return 0 # 1 次
}

例子二：

1
2
3
4
5
6
7
int func2(int n){
  for (int i = 0; i < n; ++i) # 1 + n+1 + n 
  {
    printf("哈哈哈哈哈"); # n
  }
  return 0; # 1
}

上述两个例子中，分别计算的次数为：

  • 2
  • 3n+3

常见的时间复杂度分析

  • O(1)

    在上述例一中的时间复杂度就是 O（1）—— 表示常量级时间复杂度；

    一般情况下，只要算法中不存在循环语句，递归语句，即使有成千上万行代码，其时间复杂度也是 O(1);

  • O(logn) && O(nlogn)

    对数时间复杂度非常常见，同时也是比较难分析的一种时间复杂度

    我们来用一个例子来详细还原一个这种时间复杂度的计算：

    1
    2
    3
    4
    5
    void func(int n) {
      for (int i = 1; i < n; i *= 2) {
        printf("xi xi xixixi")
      }
    }

    首先，当 n = 8：

    • i = 1 时 -> 判断 1 < 8 成立；i = 1 * 2 = 2，打印文本
    • i = 2 时 -> 2 < 8 成立；i = 2*2 = 4，打印文本
    • i = 4 时 -> 4 < 8 成立；i = 4 * 2 = 8，打印文本
    • i = 8 时 -> 8 < 8 不成立；程序结束

    于是，其执行时间 T(8) = 3（for 循环）+ 3（printf）+ (3+1)(i<n) + 1(int i = 1) -> 3 * (3) +2

    因为对这个代码的时间复杂度的影响最大的就是 i< n && i =2 ；*于是我们可以简化为：T(8) = 3, 只关注 for 循环语句；

    于是，得出规律：

    2^3 = 8;

    2^4 = 16;

    …

    2^T(n) = 3

    我们知道，对于对数而言，不论是以 2，3，10 为低，都是可以互相转换的，于是可以统一采用 logn 来表示

    从而推出：T(n) = 3log2n +2 = O(logn)

  • O(n^2)

​ n 方的复杂度也十分常见，在代码中常表示为 for 嵌套或者 while 循环；

​ 这里也是用一个例子来进行学习：

1
2
3
4
5
6
7
void func2(int n) {
  for (int i = 0; i<n; ++i){ # n
    for (int j = 0; j<n; ++j) { # n
      printf("hahahahah")
    }
  }
}

这里嵌套了两层 for 循环，可以很明显的看出其时间复杂度为 O(n^2)

当然，如果是 n 层嵌套，那么其时间复杂度为：O(n^n)

时间复杂度对比

名称 时间复杂度
常数时间 O(1)
对数时间 O(logn)
线性时间 O(n)
线性对数时间 O(nlogn)
二次时间 O(n^2)
三次时间 O(n^3)
指数时间 O(2^n)

空间复杂度分析

空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系

这段代码仅用于举例：

1
2
3
4
5
6
7
8
9
10
11
12

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

可以看到我们申请了一个大小为 n 的数组，于是其空间复杂度为 O(n);

常见的空间复杂度就是 O(1), O(n), O(n^2)，类似对数的复杂度都用不到

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

最好、最坏时间复杂度

上代码：

1
2
3
4
5
6
7
8
9
10

// 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;
}

按照时间复杂度分析，这段代码的时间复杂度为 O(n)

但是在实际情况中，当我们在一个数组中查找某个数据，并不一定需要将整个数组遍历一遍；

可能会出现比较极端的情况，例如 一次 就查找到了数据或者最后才查找到数据；

平均时间复杂度

平均时间复杂度应该如何分析呢？

要查找的变量 x 在数组中的位置，有 n+1 种情况；在数组的 0～n-1 的位置中和不在数组中，将每种情况下，需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值：

1+2+3+…+n+n/n+1 = 1/2 n = O(n)

均摊时间复杂度

均摊时间复杂度，以及它对应的分析方法，摊还分析（或者叫做平摊分析）

借助一段代码来学习：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = new int[n];
int count = 0;

void insert(int val) {
   if (count == array.length) {
      int sum = 0;
      for (int i = 0; i < array.length; ++i) {
         sum = sum + array[i];
      }
      array[0] = sum;
      count = 1;
   }

   array[count] = val;
   ++count;
}

我先来解释一下这段代码。这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。

  • 最理想的情况下，是该数组一直有空闲空间，只需要插入数据即可，时间复杂度为 O(1)
  • 最坏情况下，是插入数据时，数据已满，时间复杂度为 O(n)

那么平均时间复杂度为多少呢？

答案是 O(1)

因为对于每个数据的插入而言，其数组满的情况都被分解为每次插入了，例如已经插入了 9 次数据时，第十次插入时发生了 for 循环，那么这一次的复杂度也被均摊到前 9 次了。

这也就是均摊时间复杂度的由来了

参考

video: https://www.bilibili.com/video/BV1nE411x7qP/?from=search&seid=3250974645541167987&spm_id_from=333.337.0.0&vd_source=67c3c7f430d599a6b5dacd9127487fc7

-------------THANKS FOR READING-------------