数据结构 | 算法的时间复杂度和空间复杂度【详解】(一)

1. 什么是数据结构？

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

2. 什么是算法？

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

3. 算法效率

• 算法效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。在现在的计算机硬件环境中，比较少需要考虑这个问题了，特别是pc机的编程，内存空间越来越大，所以被考虑得也越来越少，不过一个好的程序员，都应该对自己的程序有要求，每一个for比别人少一次判断1000个for就能够少掉很多的运行时间。所以能够理解，能够大概的去运用"效率度量"还是有很大意义的。

• 算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算 机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

4. 时间复杂度

4.1 时间复杂度的概念

• 时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一 个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

实际中我们计算时间复杂度的时候其实并不需要计算精确的执行次数，而只需要知道大概执行次数，所以这里我们引入了大O的渐进表示法。其中大O符号是用于描述函数渐进行为的数学符号。

案例1：

请计算一下Func1中++count语句总共执行了多少次？

• 如果用一个函数F(N)来解释的话，怎么解释？【F(N) = N*N + 2N + 10】这是一个函数式
  这并不方便我们进行比较，能不能简化一下？

这里的时间复杂度是要取影响最大的项

大O渐进表示法：估算–>O(N^2)–>O(N)

我们这里不关心硬件，相同的配置N比N^2的程序要快

void Func1(int N)
{
  int count = 0;
  for (int i = 0; i < N; ++i)
  {
    for (int j = 0; j < N; ++j)
    {
      ++count;
    }
  }
  for (int k = 0; k < 2 * N; ++k)
  {
    ++count;
  }
  int M = 10;
  while (M--)
  {
    ++count;
  }
  printf("%d\n", count);
}

Func1 执行的基本操作次数 ：

• N = 10 F(N) = 130
• N = 100 F(N) = 10210
• N = 1000 F(N) = 1002010

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

4.2 推导大O阶的方法：

大 O 表示法是一种计算机科学和算法分析中常用的渐进表示法，用于描述算法的时间复杂度和空间复杂度。它帮助我们衡量算法在输入规模增加时，运行时间或内存使用的增长趋势，而不需要精确地测量或比较具体的运行时间。

大 O 表示法使用 “O(f(n))” 的形式，其中 “f(n)” 表示输入规模 “n” 的函数。这意味着当输入规模足够大时，算法的运行时间或内存使用将以 “f(n)” 函数的方式增长。以下是一些常见的大 O 表示法及其含义：

• O(1)：常数时间复杂度
  表示算法的运行时间不受输入规模的影响，无论输入有多大，运行时间都是固定的。
• O(log n)：对数时间复杂度
  表示算法的运行时间以对数方式增长，通常见于二分查找等分治算法。
• O(n)：线性时间复杂度
  表示算法的运行时间与输入规模线性增长，随着输入规模增加，运行时间也会线性增加。
• O(n log n)：线性对数时间复杂度
  表示算法的运行时间随着输入规模的对数线性增加，常见于快速排序和归并排序等算法。
• O(n^2)：二次时间复杂度
  表示算法的运行时间与输入规模的平方成正比，通常见于嵌套循环等情况。
• O(n^k)：多项式时间复杂度
  表示算法的运行时间与输入规模的 k 次方成正比，其中 k 为常数。
• O(2^n)：指数时间复杂度
  表示算法的运行时间随着输入规模的指数级增长，通常表示算法的效率非常低。
• O(n!)：阶乘时间复杂度
  表示算法的运行时间随着输入规模的阶乘级增长，通常表示算法的效率非常低。
• 大 O 表示法的目的是为了提供算法效率的一种抽象概念，让人们能够更容易比较不同算法的性能，并估计它们在大规模输入下的行为。通过了解算法的大 O 复杂度，开发者可以选择合适的算法来解决问题，以便在实际应用中获得更好的性能。

用大O的渐进表示法以后，Func1的时间复杂度为：

• N = 10 F(N) = 100
• N = 100 F(N) = 10000
• N = 1000 F(N) = 1000000

4.3 常见时间复杂度计算举例：

接下来就看看下面这几个案例，相信你看完就有一定的了解

实例2：

计算Func2的时间复杂度？

• 我们前期就一点一点的算，F(N) = 2N + 10
• 时间复杂度是什么?【O(N)】
• 就是取最大的那一项，当N无限大的时候N和2N没有区别，所以系数要去掉
• 时间复杂度不是算次数，是算量级

void Func2(int N)
{
  int count = 0;
  for (int k = 0; k < 2 * N; ++k)
  {
    ++count;
  }
  int M = 10;
  while (M--)
  {
    ++count;
  }
  printf("%d\n", count);
}

实例3：

计算Func3的时间复杂度？

• 如果不确定M和N的关系，可能M很大，可能N很大–> O(M+N)或者O(max(M,N))
• 如果N远大于M–>o(n)
• 如果M远大于N–>O(M)
• 如果N和M差不多大–>O(N) or O(M)

void Func3(int N, int M)
{
  int count = 0;
  for (int k = 0; k < M; ++k)
  {
    ++count;
  }
  for (int k = 0; k < N; ++k)
  {
    ++count;
  }
  printf("%d\n", count);
}

实例4：

计算Func4的时间复杂度？

• 这里可以看到k循环了100次，那么他是O(100)吗？【不是！】是O(1)

注意：O(1)并不是代表一次，而是常数次！

void Func4(int N)
{
  int count = 0;
  for (int k = 0; k < 100; ++k)
  {
    ++count;
  }
  printf("%d\n", count);
}

小结一下：

• 大O阶的方法

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项，取决定性的那一项
• 如果最高阶项存在且系数是不唯1的常系数，则去除最高项的系数，得到的结果就是大O阶
• 如果最终结果是O(1)，则表示常数次，并不是代表一次
• 还有就是没有小o阶~~

实例5：

计算strchr的时间复杂度？

const char* strchr(const char* str, int character);

while (*str) {
  if (*str == character)
    return str;
  ++str;
}

• 这个函数有可能有的同学没有见过，这是C语言库里面的一个函数strchr，是定位字符串中出现的第一个字符
• 可能在前面的位置找到了（最好），肯在中间的位置找到了（平均），还有肯在最后的位置找到了（最坏）
  

小结一下：

• 最坏情况：

• 任意输入规模的最大运行次数（上界）

• 平均情况：

• 任意输入规模的期望运行次数

• 最好情况：

• 任意输入规模的最小运行次数（下界）
• 一般我们比较关心的是一个算法的最坏情况

• 如果有最好，最坏，平均，那么时间复杂度是一个保守的估算，是取最坏，这是最好的！！！
  

实例6：

计算BubbleSort的时间复杂度？

• 很多同学一眼看他是O(N^2)，那么他是O(N^2)吗？接下来接着看

void BubbleSort(int* a, int n)
{
  assert(a);
  for (size_t end = n; end > 0; --end)
  {
    int exchange = 0;
    for (size_t i = 1; i < end; ++i)
    {
      if (a[i - 1] > a[i])
      {
        Swap(&a[i - 1], &a[i]);
        exchange = 1;
      }
    }
    if (exchange == 0)
      break;
  }
}

• 再来看一个，这个相比上一个的时间复杂度是什么？
• 可能有点同学一看这个循环有两层那么他是O(N^2),它是O(N^2)吗？–>继续接着往下看！

int PartSort1(int* a, int left, int right) {
  int keyi = left;
  while (left < right) {
    while (left < right && a[right] >= a[keyi]) {
      --right;
    }
    while (left < right && a[left <= a[keyi]]) {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[right]);
}

我们上面都是看的循环，但是我们要看思想，不能只看循环，第一个是–>O(N^2)第二个是O(N)

你算对了吗？

• 首先我们先看第一个冒泡排序的时间复杂度，如图：

• 再来看第二个 PartSort1，当left和right相遇时，时间复杂度是O(N)

小结一下：

• 时间复杂度不能数代码中的循环
• 而是需要根据思想进行灵活计算！！！

数据结构 | 算法的时间复杂度和空间复杂度【详解】(二):https://developer.aliyun.com/article/1426602