【C】初阶数据结构1 -- 时间复杂度与空间复杂度

1 数据结构

2 算法

3 复杂度

1）时间复杂度

2）空间复杂度

4 提升算法能力的两点建议

1）画图

2）多实践，多上手写代码

重点一  数据结构的定义

1 数据结构

数据结构是计算机存储、组织数据的方式，主要是指相互之间存在一种或多种特定关系的数据元素的集合。在计算机中，包含多种数据结构，如：顺序表、链表以及树、图、哈希表等多种数据结构，需要知道的一点是，没有任何一种数据结构能够适用于所有的情况，有时候需要综合多种数据结构才能解决一个实际问题，所以才会有多种数据结构。

重点二  算法

2 算法

数据结构是与算法紧密相关的，所谓算法（Algorithm）就是定义良好的计算过程，取一个值或者一组值为输入，然后通过一系列的计算步骤，用来将输入的数据输出结果。

算法也是分好坏的，用有的算法写出来的程序可能运行时间只需要4毫秒，而有的算法写出来的程序可能就会需要8秒甚至9秒，如，堆排序和冒泡排序（以后会讲解），都是100000个数据进行排序，但是堆排序只需要4毫秒，而冒泡排序却需要8秒，所以衡量一个算法的好坏就显得尤为重要，那么该用什么来衡量算法的好坏或者执行效率呢？

这里就不得不提到这篇文章的重点，复杂度了。

重点三  复杂度

3 复杂度

算法在编写成程序后，运行效率无非是从两个角度来分析，一个就是运行时间的长短，另一个就是运行所占空间的大小，所以复杂度也就区分为了时间复杂度与空间复杂度。

重点四  时间复杂度

1）时间复杂度

时间复杂度主要是用来衡量一个算法的运行快慢的，如果一个算法的时间复杂度越小，那么这个算法也就越好。

那么时间复杂度是否是直接计算程序运行时间的长短呢？答案是并不是，因为一个程序运行时间的长短不仅是跟算法的好坏相关，也与计算机的配置相关，一个计算机的配置越好，运行时间越快，也与编译器本身相关，而且最重要的一点是，用程序运行时间衡量的话，是不能事前估计的，只能在程序运行后才能衡量，综合来说，是不能用一个程序的具体运行时间来衡量一个算法的好坏的。

在计算机科学中，时间复杂度是一个函数式T(n)，这个函数式定量描述了一个算法的运行时间，体现了一个算法的运行时间的规模，规模越大，算法运行时间也就越长，就没有那么好，比如，算法A时间复杂度T(n)是n^2，算法B的时间复杂度T(n)是n，所以算法B是优于算法A的。

计算一个算法的时间复杂度时，主要是看某个语句的运行次数，如以下这个代码：

//计算跟count相关语句的执行次数
void Func1()
{
  int count = 0;
  for (int i = 0;i < n;i++)
  {
    for (int j = 0;j < n;j++)
    {
      count++;
    }
  }
 
  for (int i = 0;i < n;i++)
  {
    count++;
  }
}

运行次数如下面表格所示：

count语句运行次数
语句	运行次数
int count = 0	1
第一个count++	n^2
第二个count++	n

所以这个程序中的T(n) = n^2 + n + 1，但是只有当n很小的时候，T(n)中的n和1才会对T(n)起影响作用，但是当n特别大的时候，甚至是趋于无穷量的时候，n^2趋于无穷的速度远远快于n趋于无穷的速度的，所以当n特别大的时候，n和1也就对T(n)的影响很小了，由于T(n)只是衡量一个算法运行时间的规模，所以n和1也就可以舍弃了，这时候T(n) = n^2了。

所以在计算时间复杂度时，只需要计算运行次数中量级最大的那个语句的执行次数（一般是循环中的语句），也就是能够代表增长量的大概执行次数就可以了，这种表示时间复杂度的表示法叫做大O表示法。

大O表示法规则：

1） 在计算时间复杂度时，只保留高阶项，去掉低阶项，因为当n特别大时，低阶项对于T(n)的影响可以忽略不计

2） 如果高阶项前面有系数且不为1，那么就把系数变为1，因为时间复杂度只是描述运行时间规模，常数项不影响

3） 如果程序的运行次数与n没有关系，只有常数次，那就统一用 1 来表示，表示这个算法的T(n)为常数阶

接下里我们来看几个例子：

例1：计算Func1函数的时间复杂度

void Func1(int n)
{
  int count = 0;
  for (int i = 0; i < 3 * n; i++)
  {
    count++;
  }

  int m = 100;
  
  for (int i = 0; i < m;i--)
  {
    count++;
  }

}

运行次数如下面表格所示：

Func1函数运行次数
语句	执行次数
第一个count++	2 * n
第二个count++	100

总执行次数：2 * n + 1

时间复杂度：根据以上大O表示法规则，舍弃低阶项以及系数，可得T(n) = n，所以时间复杂度为：O(n)

例2：计算Func2函数的时间复杂度

void Func2(int n, int m)
{
  int count = 0;
  for (int i = 0;i < n; i++)
  {
    count++;
  }

  for (int j = 0;j < m; j++)
  {
    count++;
  }

}

运行次数如表格所示：

Func2函数运行次数
语句	运行次数
第一个count++语句	n
第二个count++语句	m

总执行次数：m + n

这个函数的运行次数与两个变量n，m都相关，当m < n时，T(n) = n，时间复杂度：O(n)；当m == n时，T(n) = n 或者 m，时间复杂度：O(n) 或者 O(m)；当m > n时，T(n) = m，时间复杂度：O(m)。

例3：计算Func3函数的时间复杂度

int Func3(int n)
{
  int count = 0;
  for (int i = 0;i < 1000;i++)
  {
    count++;
  }
  
  return count;
}

运行次数：

Func3函数语句的运行次数
语句	运行次数
count++	100

这个函数里count++语句的运行次数为100次，跟n是没有关系的，T(n) = 100，根据上面的大O推导规则，运行次数为常数次，时间复杂度为：O(1)。

需要注意的是，这里的O(1)并不是代表运行次数为1次，而是代表该算法的消耗时间的规模是常数阶，跟输入的数据n是没有关系的。

例3：计算Func4函数的时间复杂度

const char* Func4(const char* str, char character)//查找character字符在str字符串中的位置
{
  const char* p = s;
  while (*p != character)
  {
    if (*p == '\0')
    {
      return NULL;
    }
    
    p++;
  }

  return p;
}

执行次数（这里假设字符串长度为n）：

Func4函数语句的运行次数
查找情况	执行次数
若查找字符在第一个位置	1次
若查找字符在中间位置	n/2次
若查找字符在最后位置或者找不到	n次

所以可以看到上述程序的运行次数是与查找字符的位置相关的，当查找字符位于前面位置时，T(n)是常数次，所以时间复杂度是：O(1)；当查找字符位于偏中间位置时，T(n) = n/2，时间复杂度为：O(n)；当查找字符位于末尾位置时，T(n) = n，时间复杂度为：O(n)。

这种分不同情况时，复杂度也随之不同的算法，是有最好时间复杂度、平均时间复杂度和最坏时间复杂度的：

最坏时间复杂度：任意输入规模的最大运行次数（上界）。

平均时间复杂度：任意输入规模的期望（均值）运行次数。

最好时间复杂度：任意输入规模的最小运行次数（下界）。

显然，这个算法的最坏和平均时间复杂度为O(n)，最好时间复杂度为O(1)。

例4：计算Func5函数的时间复杂度

void Func5(int n)
{
  int count = 1;
  while (count < n)
  {
    count *= 2;
  }
  
}

这个函数的运行次数跟之前函数不太一样，之间count都是++，这里是每次乘2，要分析运行次数就得根据运行次数和count值之间的关系来推导出运行次数，count *= 2 语句运行次数（也就是循环次数）与count值变化如下表格：

Func5函数语句的运行次数
count的值	运行次数
1	0
1*2	1
122	2
122*2	3
12222	4
......	......
2^i	i

通过推导运行次数和count值之间的关系，不难得出规律，就是当运行次数为 i 次时，count的值是2^i ，由于循环停止条件是count >= n，所以运行次数和n之间的关系就是2^i >= n，这里取等号，就是2^i = n，也就是 i = $\log_{2}n$ ，所以T(n) = $\log_{2}n$ ，时间复杂度为：O( $\log_{2}n$ )，这里写O(logn)也是可以的，这里还是因为时间复杂度表示的运行时间的规模，而 $\log_{2}n$ 就代表其时间复杂度为对数阶，所以写logn也是可以的。

例5：计算Func6函数的时间复杂度

//计算阶乘的递归函数
int Func6(int n)
{
  if (n == 0)
  {
    return 1;
  }
  
  return Func6(n - 1) * n;
}

Func6函数是用来计算一个数n的阶乘的递归（递归是指直接或者间接调用自身函数的一种算法思想）定义的函数，而计算一个跟递归相关算法的时间复杂度公式为：

递归函数的时间复杂度 = 单次递归的时间复杂度 * 递归的深度（次数）

Func6函数单次执行的时间复杂度为：O(1)

Func6函数递归的次数为：n次

所以Func6函数的时间复杂度为：O(n)

要注意的是这里的相乘并不是n * O(1)，而是直接将O(1)里面的1乘以n，其实递归函数计算时间复杂度的内在原理为：C语言在每次调用一个函数的时候，都会为其开辟一块函数栈帧（可以理解为在调用函数时，会为每一次多用的函数额外开辟一块空间，每个函数之间的函数栈帧是独立的），也叫运行时堆栈，而每递归一次，就相当于对该函数调用了一次，虽然每次运行次数为常数次，但是当递归次数达到n次时，也就相当于常数次的运行次数变为了n次，所以时间复杂度会变为O(n)。

重点五  空间复杂度

2）空间复杂度

空间复杂度类似于时间复杂度，也是一个表达式，用来描述程序在运行过程中临时额外开辟空间的大小，同样的，也是描述一个开辟空间的规模大小。

在时间复杂度中，时间复杂度并不是程序运行时间的大小；同样的，空间复杂度也不是实际开辟了多少个字节的空间，而是算的是额外使用变量的个数，把额外使用的一个变量抽象为一块空间。

空间复杂度的计算与时间复杂度一样，也采用大O渐进表示法。

需要注意的一点是：函数在运行时所需要的空间（形参，局部变量等）已经确定好了，所以这些变量不被计算到空间复杂度中，计算的是在运行过程中额外开辟的空间。

例6：计算Func7函数的空间复杂度

//数组打印函数
void Print(int* arr, int n)
{
  for (int i = 0;i < n;i++)
  {
    printf("%d ", arr[i]);
  }

  printf("\n");
}

在这个函数中，形参arr，n，以及局部变量 i 在运行时他们的空间就已经确定，所以是不会算到额外开辟空间中的，而这个函数有没有其他额外的变量，所以额外开辟空间为0，根据大O表示法，空间复杂度为：O(1)，这里的 1 仍表示额外开辟的空间为常数阶的。

例7：计算Func6函数的空间复杂度

//计算阶乘的递归函数
int Func6(int n)
{
  if (n == 0)
  {
    return 1;
  }
  
  return Func6(n - 1) * n;
}

这个函数还是上面那个求阶乘的递归函数，该函数的递归次数与额外开辟的空间如下：

Func6函数的空间复杂度
每次递归额外开辟空间大小	递归次数	总额外开辟空间大小
1	n	n

由此可以得出递归函数的额外开辟空间的大小的公式：

总的额外开辟空间大小 = 递归次数 * 单次函数额外开辟空间大小

根据大O渐进表示法，所以求阶乘的递归函数的空间复杂度为：O(n)

其实其内在原理和递归函数求空间复杂度是一样的：每次递归调用函数时，都会为每次函数调用开辟一块空间，这个空间叫做函数栈帧，所以每递归调用一次函数，就相当于额外开辟了一块空间，所以当递归调用n次时，也就额外开辟了n块空间。

例8：计算Func8函数的时间复杂度与空间复杂度

//求递归函数的时间复杂度与空间复杂度
void Func8(int n, int count, int stop)
{
  if (count >= stop)
  {
    printf("%d ", count);
    return;
  }

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

  Func8(n, count, stop);
}

先看时间复杂度：

count 的值与n和stop同时相关，count++单次递归运行次数和递归次数如表格所示：