其实时间复杂度比较的问题并不复杂，但是又很多的朋友都不太了解如何计算空间复杂度，因此呢，今天小编就来为大家分享时间复杂度比较的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！
本文目录
一、各种算法的时间复杂度
1、 O(1)< O(logn)< O(n)< O(nlogn)< O(n^2)< O(n^3)< O(2^n)< O(n!)< O(n^n)
2、一般时间复杂度到了2 n(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是O(2 n).
3、平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.
4、冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)
5、快速排序空间复杂度为logn(因为递归调用了),归并排序空间复杂是O(n),需要一个大小为n的临时数组.
6、基数排序的空间复杂是O(n),桶排序的空间复杂度不确定
7、原文：
二、时间复杂度怎么算例题
这是一个简单的"累乘"问题，用递归算法也能解决。
fact(3)-----fact(2)-----fact(1)------fact(2)-----fact(3)
递归算法在运行中不断调用自身降低规模的过程，当规模降为1，即递归到fact(1)时，满足停止条件停止递归，开始回溯(返回调用算法)并计算，从fact(1)=1计算返回到fact(2);计算2*fact(1)=2返回到fact(3)；计算3*fact(2)=6，结束递归。
每一次递归调用，都用一个特殊的数据结构"栈"记录当前算法的执行状态，特别地设置地址栈，用来记录当前算法的执行位置，以备回溯时正常返回。递归模块的形式参数是普通变量，每次递归调用得到的值都是不同的，他们也是由"栈"来存储。
一般递归调用有以下几种形式(其中a1、a2、b1、b2、k1、k2为常数)。
<1>直接简单递归调用：f(n){...a1*f((n-k1)/b1);...};
<2>直接复杂递归调用：f(n){...a1*f((n-k1)/b1);a2*f((n-k2)/b2);...};
<3>间接递归调用：f(n){...a1*f((n-k1)/b1);...}，
g(n){...a2*f((n-k2)/b2);...}。
递归算法的分析 *** 比较多，最常用的便是迭代法。
迭代法的基本步骤是先将递归算法简化为对应的递归方程，然后通过反复迭代，将递归方程的右端变换成一个级数，最后求级数的和，再估计和的渐进阶。
算法的递归方程为：T(n)=T(n-1)+O(1);
这个例子的时间复杂性是线性的。
T(n)=2T(n/2)+2,且假设n=2的k次方。
=2的(k-1)次方*T(n/2的(i-1)次方)+$(i:1~(k-1))2的i次方
这个例子的时间复杂性也是线性的。
T(n)=2T(n/2)+O(n),且假设n=2的k次方。
一般地，当递归方程为T(n)=aT(n/c)+O(n),T(n)的解为：
O(nlog2n)(a=c&&c>1)//以2为底
O(nlogca)(a>c&&c>1)//n的(logca)次方，以c为底
上面介绍的3种递归调用形式，比较常用的是之一种情况，第二种形式也有时出现，而第三种形式(间接递归调用)使用的较少，且算法分析
比较复杂。下面举个第二种形式的递归调用例子。
<4>递归方程为：T(n)=T(n/3)+T(2n/3)+n
为了更好的理解，先画出递归过程相应的递归树：
...............................
累计递归树各层的非递归项的值，每一层和都等于n，从根到叶的最长路径是：
n-->(2/3)n-->(4/9)n-->(12/27)n-->...-->1
于是T(n)<=(K+1)*n=n(log(2/3)n+1)
由此例子表明，对于第二种递归形式调用，借助于递归树，用迭代法进行算法分析是简单易行的。
三、快速排序法的平均时间复杂度和最坏时间复杂度分别是多少
1、快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n^2)。
2、当排序已经成为基本有序状态时，快速排序退化为O(n^2)，一般情况下，排序为指数复杂度。
3、快速排序最差情况递归调用栈高度O(n)，平均情况递归调用栈高度O(logn)，而不管哪种情况栈的每一层处理时间都是O(n)，所以，平均情况（更佳情况也是平均情况）的时间复杂度O(nlogn)，最差情况的时间复杂度为O(n^2)。
4、快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序，它采用了一种分治的策略，通常称其为分治法。快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
5、（1）首先设定一个分界值，通过该分界值将数组分成左右两部分。
6、（2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
7、（3）然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
8、（4）重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
四、常见排序算法以及对应的时间复杂度和空间复杂度
排序：将杂乱无章的数据，按照一定的 *** 进行排列的过程叫做排序。
排序大的分类可分为内排序和外排序，不需要访问外存就能进行排序的叫做内排序。
排序也可以分为稳定排序和不稳定排序
稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序 *** 是稳定的。即；若 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次，更高可执行到世界的尽头。。。
五、空间复杂度的时间与空间复杂度比较
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。
END，本文到此结束，如果可以帮助到大家，还望关注本站哦！
