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

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

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）。

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

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

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