数据结构-时间复杂度/空间复杂度

  Hello，好久没有更新了哦，已经开始学习数据结构了，这篇文章呢就是对刚学数据结构所接触到的时间复杂度进行一个分享哦，如果有错误之处，大家记得拍拍我哦~

既然要讨论时间/空间复杂度，那我们就得知道时间/空间复杂度是什么，那到底什么是时间复杂度，什么是空间复杂度呢？

一、时间复杂度

时间复杂度：它是一个函数，这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用O（）来表示，不包括这个函数的低价项和首项系数。一个算法所花费的时间与其中语句的执行次数成正比例，那么，算法中的基本操作的执行次数就是算法的时间复杂度。

理解：算法的时间复杂度它是一个函数，其定量的描述了该算法的运行时间。但是，仔细一想，一个算法执行所消耗的时间，从理论上来说的话，它是不可以算出来的，只有在你把程序放在机器上跑起来时，我们才能够知道该算法在整个执行的过程中所消耗的时间。

说这么多，其实用一句话总结：就是找到某条基本语句与问题规模N之间的数学表达式，也就是算出了该算法的时间复杂度。

注：时间复杂度通常用O（）来表示。

常见的有：O(1),O(n),O(logn),O(nlogn),O(n^2)等

下面详细介绍一下：

O(1):常数时间复杂度。这类可以说明算法的执行时间不随输入规模的增大而增长。比如，数组的访问，哈希表的查找（后期会更）。

O(n):线性时间复杂度。这类可以说明算法的执行时间随输入规模的增大而增长，其增长速度与输入规模成正比。比如，数组的遍历，简单查找等。

O(logn):对数时间复杂度。这类可以说明算法的执行时间随输入规模的增大而增长。

O(nlogn):线性对数时间复杂度。这类可以说明算法的执行时间随着输入规模的增大而增长，但增长速度比线性快。比如，归并排序，快速排序等。

O(n^2):平方时间复杂度。这类可以说明算法的执行速度随着输入规模的增大而增长，且增长速度很快。比如，冒泡排序，选择排序等。

说明：这里提到的排序后面会更新的，大家在这里先听听哦，这里主要是掌握对时间复杂度的理解。

举个例子：

大家看这段代码：

// 请计算一下Func1中++count语句总共执行了多少次？
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);
}

实际上当我们掌握这个知识点并且有个很多的练习时，我们就知道，在计算时间复杂度的时候，我们其实并不一定要计算精确的执行次数，我们只需要计算知道大概的执行次数就可以啦~ 提高一个知识肯定就会有新的知识点的出现，这里我们就使用大O的渐进表示法。

接下来我们就介绍一下大O的渐进表示法的规则和该注意的点：

大O符号：用于描述函数渐进行为的数学符号。

规则：

（1）用常数1取代运行时间中的所有加法常熟。

（2）在修改后的运行次数函数中，只保留最高阶项。

（3）如果最高阶项存在但不是1时，这时就去除与这个项目相乘的常数，，从而得到的结果就是大O阶。

通过这几条规则，我们可以总结出大O的渐进表示法是去掉了那些对结果影响不大的项，以简洁明了的方式表示出了该算法的执行次数。

当然，讨论一个事，必然会分类讨论，那么，时间复杂度的情况也是分类讨论（最好，最坏，平均）

分类讨论：

最好时：任意输入规模的最大运行次数，也就是上界。

最坏时：任意输入规模的最小运行次数，也就是下界。

平均时：任意输入规模我们最期望，最想要让它达到的运行次数，简单点说，就是理想型嘛，哈哈

当然，在实际情况中，大家最应该关注且需要密切关注的得是算法的最坏运行情况，所以数组中搜时间复杂度为O(N).

算法的时间复杂度分为：

（1）最好时间复杂度：指的是算法计算量可能达到的最小值。

（2）最坏时间复杂度：指的是算法计算量可能达到的最大值。

（3)平均时间复杂度：指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。

时间复杂度主要衡量一个算法的运行速度的快慢，空间复杂度主要衡量一个算法运行所需要的额外空间。

二、空间复杂度

空间复杂度：也是一个数学表达式，是对一个算法在运行过程当中临时占用存储空间大小的量度，换句话说，也就是额外占取的空间的大小。空间复杂度不是程序占用了多少空间，因为讲这个其实没有多大意义，所以空间复杂度算的其实是变量的个数。当然，都是复杂度嘛，空间复杂度和时间复杂度的规则基本大差不差，同样使用大O渐进表示法。

注：空间复杂度基本上是O（1）/O（N），其他不怎么常见哦~

接下来举例子说明哦~

a:计算阶乘的时间复杂度

阶乘递归的空间复杂度是O（N）；

b:计算冒泡排序的空间复杂度

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{assert(a);for (int end = n; end > 0; --end){int exchange = 0;for (int i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

思路：重复走过要排序的数列，一次比较两个元素，如果它们的顺序不太对劲，就把它们错误的顺序交换过来。这个“工作”是重复的进行知道不再需要交换，换句话说这个数列已经排序完成了。

这里，冒泡排序的辅助变量只是一个临时变量，而且其不会随着排序规模的扩大而因此改变，所以它的空间复杂度为O（1）。

   不过，这里要提一嘴的是，对于算法的性能，需要从时间和空间的使用情况来评价。一个好的算法，应该是同时具备时间复杂度和空间复杂度都较低的特性，但是，从实际情况来看的话，对于某个算法问题，要想使得时间复杂度和空间复杂度都优化是蛮困难的。如果说降低时间复杂度的话，那么往往会是它的空间复杂度提高。所以，在通常情况下，在算法设计的过程当中，一般会通过空间换时间的做法，牺牲一部分计算机存储空间，从而来提升整个算法的运行速度。

好啦，关于数据结构中关于 时间复杂度和空间复杂度的介绍先到这里啦，后期有时间的话还会举一些更为详细的例子和大家一起进步~

看到这里，支持一下小编叭~ 如果有错误之处，大家记得评论区留言吖~