‘壹’ 各种算法的时间复杂度
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
一般时间复杂度到了2 n(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是O(2 n).
平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.
空间复杂度
冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)
快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.
基数排序的空间复杂是O(n),桶排序的空间复杂度不确定
原文： https://blog.csdn.net/weiwenhp/article/details/8622728
‘贰’ 算法复杂度中的O(n)、O(nlgn)、O(n^2)等是什么意思
关于算法的复杂度计算，初学者一开始便容易进入完全定量的思考之中，这是难以到达的。算法复杂度在很多时候是对算法运行的时间一个大概的定性（或者说大数）描述，因为很多时候无法精确地描述一条代码究竟执行了多少时间。而任何一个算法运行的大多时间都集中在某一主体循环之中，像for,while之类，主体循环的次数往往跟某个或多个输入参数或环境变量有关。像O(n)、O(nlgn)、O(n^2)之类描述都是围绕主体循环次数和输入参数或者环境变量的关系展开的。
下面举一个例子，从给定的整型数组中查找与某一数相等的数的位置，显然对于没有排序的数组而言，需要从数组头部开始向后遍历比较，那么这个主体遍历循环就跟数组的长度有关，即算法复杂度为O(n)。
‘叁’ 从n个数中取出m个最大的最好的算法是什么
有很多算法，复杂度也不尽相同。以下简单举几个例子：
1. n×m遍扫描
【算法基本描述】n×m遍扫描
【算法思想】每次都扫描一遍数组，取出最大元素，这样扫描m遍就能得到m个最大的数
【算法复杂度】O(nm)
2.排序后取最大m个数
【算法基本描述】对n个数排序，对拍完序后的序列取m个最大的数
【算法复杂度】视排序的复杂度，一般为O(nlogn)或O(n^2)
3.最小堆
【算法基本描述】一遍扫描+最小堆
【算法伪代码】
00-建立一个最小堆（优先队列），最小堆的大小控制在m之内
01-for 每个数：
02-----if 这个数比最小堆的堆顶元素大：
03---------弹出最小堆的最小元素
04---------把这个数插入到最小堆
05-最小堆中的m个元素就是所要求的元素
06-其中最小堆的作用就是保持里面始终有m个最大元素，且m个元素中最小的元素在堆顶。
【算法复杂度】O(nlogm) 遍历O(n) 最小堆O(logm)
【其他】如果要求n个数中取最小的m个，只要把算法反一下即可
总结：当n与m差不多大时，采用复杂度较低的排序是比较可取的，因为简单。当m<<n时，排序是很浪费时间的，因为我们不需要后(n-m)个数，所以可以采用最小堆的方法。
我不敢说我的算法是最好的，但是它一定是一个复杂度较低的算法。
‘肆’ TSP问题的遍历算法和贪心算法有什么区别,为什么不选择遍历算法
所有问题遍历算法的时间复杂度是最高的，但是对于TSP问题来说贪心算法一般是得不到最优解的