『壹』 各種演算法的時間復雜度
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問題來說貪心演算法一般是得不到最優解的