漢諾塔演算法復雜度

A. 漢諾塔該怎麼玩，方法

漢諾塔演算法介紹：

一位美國學者發現的特別簡單的方法：只要輪流用兩次如下方法就可以了。

把三根柱子按順序排成「品」字型，把所有圓盤按從大到小的順序放於柱子A上，根據圓盤數量來確定柱子排放的順序：

n若為偶數的話，順時針方向依次擺放為：ABC；而n若為奇數的話，就按順時針方向依次擺放為：ACB。這樣經過反復多次的測試，最後就可以按照規定完成漢諾塔的移動。

因此很簡單的，結果就是按照移動規則向一個方向移動金片：

如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C。

(1)漢諾塔演算法復雜度擴展閱讀：

漢諾塔經典題目：

三根相鄰的柱子，標號為A,B,C，A柱子上從下到上按金字塔狀疊放著n個不同大小的圓盤，要把所有盤子一個一個移動到柱子B上，且每次移動同一根柱子上都不可以出現大盤子在小盤子上方的情況。

至少需要幾次移動的問題，我們設移動次數為H(n）。

把上面n-1個盤子移動到柱子C上，把最大的一塊放在B上，把C上的所有盤子移動到B上，由此我們得出表達式：

H⑴ = 1

H(n) = 2*H(n-1）+1 (n>1）

很快我們就可以得到H(n）的一般式為：

H(n) = 2^n - 1 (n>0)

且這種方法的確是最少次數的，證明非常簡單，可以嘗試從2個盤子的移動開始證，可以試試。

進一步加深問題：

假如現在每種大小的盤子都有兩個，並且是相鄰的，設盤子個數為2n，問：⑴假如不考慮相同大小盤子的上下要幾次移動，設移動次數為J(n）；⑵只要保證到最後B上的相同大小盤子順序與A上時相同，需要幾次移動，設移動次數為K(n）。

⑴中的移動相當於是把前一個問題中的每個盤子多移動一次，也就是：

J(n) = 2*H(n) = 2*（2^n - 1） = 2^(n+1）-2

在分析⑵之前，我們來說明一個現象，假如A柱子上有兩個大小相同的盤子，上面一個是黑色的，下面一個是白色的，我們把兩個盤子移動到B上，需要兩次。

盤子順序將變成黑的在下，白的在上，然後再把B上的盤子移動到C上，需要兩次，盤子順序將與A上時相同，由此我們歸納出當相鄰兩個盤子都移動偶數次時，盤子順序將不變，否則上下顛倒。

回到最開始的問題，n個盤子移動，上方的n-1個盤子總移動次數為2*H(n-1），所以上方n-1個盤子的移動次數必定為偶數次，最後一個盤子移動次數為1次。

討論問題⑵：

綜上可以得出，要把A上2n個盤子移動到B上，可以得出上方的2n-2個盤子必定移動偶數次，所以順序不變，移動次數為：

J(n-1） = 2^n-2

然後再移動倒數第二個盤子，移動次數為2*J(n-1）+1 = 2^(n+1）-3，

最後移動最底下一個盤子，所以總的移動次數為：

K(n) = 2*（2*J(n-1）+1）+1 = 2*（2^(n+1）-3）+1 = 2^(n+2）-5

B. 各種演算法的時間復雜度

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