算法空间复杂度最小的

1. 算法的空间复杂度是指什么

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。

而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的。

它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变。

我们称这种算法是“就地"进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

2. 常见排序算法以及对应的时间复杂度和空间复杂度

排序 ：将杂乱无章的数据，按照一定的方法进行排列的过程叫做排序。

排序大的分类可分为 内排序 和 外排序 ，不需要访问外存就能进行排序的叫做内排序。

排序也可以分为 稳定排序 和 不稳定排序

稳定排序 ：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。即；若 a[i]=a[j] , a[i] 在 a[j] 之前，经过排序后 a[i] 依然在 a[j] 之前。冒泡排序、直接插入排序、二分插入排序、归并排序，基数排序都是稳定排序。
不稳定排序 ：直接选择排序、堆排序、快速排序、希尔排序，猴子排序。

以升序为例，比较相邻的元素，如果第一个比第二个大，则交换他们两个。如果两个元素一样大，则继续比较下一对。所以冒泡排序是一种稳定排序。

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。快速排序是不稳定排序。

将序列分为两个部分{{有序序列},{无序}}，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。如果碰到相等的元素，就会把它插入到想等元素后面，顺序不会改变，所以直接插入排序是稳定排序。

在直接插入排序的基础上，对有序序列进行划分。例如：序列为 {{a[0]......a[i-1]},a[i]} 其中 {a[0]......a[i-1]} 为有序序列，取 a[(i-1)/2] ，将其与 a[i] 比较，即可确定 a[i] 的范围 (a[0]...a[(i-1)/2] 或者 a[(i-1)/2]...a[i-1]) ,然后继续在已确定的范围内进行二分。范围依次缩小为： 1/2、1/4、1/8、1/16...... 可快速确定a[i]应该插入的位置。二分插入排序也是稳定排序。

将整个序列分割成若干个小的子序列，每个子序列内分别进行插入排序。一般情况下步长取n/2。直到最后一次步长为1，即所有元素在一个组中进行排序。由于希尔排序是先将整个序列划分为多个子序列进行排序，相同的元素顺序在这个过程中顺序可能会被打乱，所以希尔排序是不稳定排序。

从待排序的数据元素中，选出最小或最大的元素与序列第一个数交换。直到所有数据排完。直接选择排序是不稳定排序。例如： {3，3，1} ，第一次排序就将1和第一个3交换，想等元素的顺序改变了。

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

堆排序是一种树形选择排序，是对直接选择排序的有效改进。
最大堆:每个节点的值都大于等于它的孩子节点。
最小堆:每个节点的值都小于等于它的孩子节点。
最大堆第0个数据是最大数，最小堆第0个数据是最小数。
堆排序是不稳定排序

思想

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
如何将两个有序序列合并？(升序)
{a[0]......a[i-1]},{b[0]......b[j-1]}
若 b[0]<a[0] ，取 b[0] 放入数组 c 中，然后继续比较数组 a 和 b 中的第一个元素，直到数组 a 和 b 中最后一对元素比较完成。

思想

将数组分成二组 a , b 如果这二组组内的数据都是有序的，那么就可以按照上述方法对这二组数据进行排序。如果这二组数据是无序的？
可以将 a , b 组各自再分成二组。递归操作，直到每个小组只有一个数据，每个小组只有一个元素所以我们可以认为它已经是有序序列，然后进行合并。
先分解后合并。
归并排序是稳定排序

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。从最低位起从0-9依次扫描序列，一边扫描一边将扫描到的数据加到新的序列中，得到一个序列。然后比较高一位，重复上述操作，直到最高位排序完成。数列就变成一个有序序列。基数排序是稳定排序。

以全是二位数的序列举例

无限猴子定理 :指一只猴子随机在打字机键盘上按键，最后必然可以打出法国国家图书馆的每本图书。

时间复杂度最低1次，最高可执行到世界的尽头。。。

3. 算法的空间复杂度是指什么

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。

而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

注意

分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

4. 〔算法〕排序的最低时间复杂度为什么是O（nlogn）

这个首先要明确一点，只用到比较的排序算法最低时间复杂度是O(nlogn)，而像桶排这样的只需要O(R)(R为桶的大小)
为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。
首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。
先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。
具有L片树叶的二叉树的深度至少是logL。
所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。
而
log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1
>=logn+log(n-1)+log(n-2)+...+log(n/2)
>=(n/2)log(n/2)
>=(n/2)logn-n/2
=O(nlogn)
所以只用到比较的排序算法最低时间复杂度是O(nlogn)。

5. 算法的空间复杂度是多少

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

注意：

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

主要还是从算法所占用的“时间”和“空间”两个维度去考量。时间维度：是指执行当前算法所消耗的时间，我们通常用“时间复杂度”来描述。空间维度：是指执行当前算法需要占用多少内存空间，我们通常用“空间复杂度”来描述。

因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是“鱼和熊掌”，不可兼得的，那么我们就需要从中去取一个平衡点。