通過線性時間演算法建立二叉堆

1. 堆排序是什麼

堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系（參見二叉樹的順序存儲結構），在當前無序區中選擇關鍵字最大（或最小）的記錄
其過程為：
（1）用大根堆排序的基本思想

① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區

②
再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key

③由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。

……

直到無序區只有一個元素為止。

（2）大根堆排序演算法的基本操作：

① 初始化操作：將R[1..n]構造為初始堆；

②
每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆（亦稱重建堆）。

注意：

①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。

②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止

2. ACM 關於ACM程序設計競賽，需要掌握哪些知識點，最好能詳細一點，謝謝高手們了。

訓練過ACM等程序設計競賽的人在演算法上有較大的優勢，這就說明當你編程能力提高之後，主要時間是花在思考演算法上，不是花在寫程序與debug上。
下面給個計劃你練練：

第一階段：練經典常用演算法，下面的每個演算法給我打上十到二十遍，同時自己精簡代碼，因為太常用，所以要練到寫時不用想，10-15分鍾內打完，甚至關掉顯示器都可以把程序打出來。

1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成樹(先寫個prim,kruscal要用並查集，不好寫)
3.大數（高精度）加減乘除
4.二分查找. (代碼可在五行以內)
5.叉乘、判線段相交、然後寫個凸包.
6.BFS、DFS,同時熟練hash表(要熟，要靈活,代碼要簡)
7.數學上的有：輾轉相除（兩行內），線段交點、多角形面積公式.
8. 調用系統的qsort, 技巧很多，慢慢掌握.
9. 任意進制間的轉換

第二階段：練習復雜一點，但也較常用的演算法。
如：
1. 二分圖匹配（匈牙利），最小路徑覆蓋
2. 網路流，最小費用流。
3. 線段樹.
4. 並查集。
5. 熟悉動態規劃的各個典型：LCS、最長遞增子串、三角剖分、記憶化dp
6.博弈類演算法。博弈樹，二進製法等。
7.最大團，最大獨立集。
8.判斷點在多邊形內。
9. 差分約束系統.
10. 雙向廣度搜索、A*演算法，最小耗散優先.

第三階段：
前兩個階段是打基礎，第三階段是鍛煉在比賽中可以快速建立模型、想新演算法。這就要平時多做做綜合的題型了。
1. 把oibh上的論文看看（大概幾百篇的，我只看了一點點，呵呵）。
2. 平時掃掃zoj上的難題啦，別老做那些不用想的題.(中大acm的版主經常說我挑簡單的來做:-P )
3. 多參加網上的比賽，感受一下比賽的氣氛，評估自己的實力.
4. 一道題不要過了就算，問一下人，有更好的演算法也打一下。
5. 做過的題要記好 :-)
下面轉自：http://hi..com/wilworld/blog/item/88b1b844d37e4049500ffe6a.html
ACMer必備知識（任重而道遠......）

圖論

路徑問題
0/1邊權最短路徑
BFS
非負邊權最短路徑（Dijkstra）
可以用Dijkstra解決問題的特徵
負邊權最短路徑
Bellman-Ford
Bellman-Ford的Yen-氏優化
差分約束系統
Floyd
廣義路徑問題
傳遞閉包
極小極大距離 / 極大極小距離
Euler Path / Tour
圈套圈演算法
混合圖的 Euler Path / Tour
Hamilton Path / Tour
特殊圖的Hamilton Path / Tour 構造

生成樹問題
最小生成樹
第k小生成樹
最優比率生成樹
0/1分數規劃
度限制生成樹

連通性問題
強大的DFS演算法
無向圖連通性
割點
割邊
二連通分支
有向圖連通性
強連通分支
2-SAT
最小點基

有向無環圖
拓撲排序
有向無環圖與動態規劃的關系

二分圖匹配問題
一般圖問題與二分圖問題的轉換思路
最大匹配
有向圖的最小路徑覆蓋
0 / 1矩陣的最小覆蓋
完備匹配
最優匹配
穩定婚姻

網路流問題
網路流模型的簡單特徵和與線性規劃的關系
最大流最小割定理
最大流問題
有上下界的最大流問題
循環流
最小費用最大流 / 最大費用最大流

弦圖的性質和判定

組合數學

解決組合數學問題時常用的思想
逼近
遞推 / 動態規劃
概率問題
Polya定理

計算幾何 / 解析幾何

計算幾何的核心：叉積 / 面積
解析幾何的主力：復數

基本形
點
直線，線段
多邊形

凸多邊形 / 凸包
凸包演算法的引進，卷包裹法

Graham掃描法
水平序的引進，共線凸包的補丁

完美凸包演算法

相關判定
兩直線相交
兩線段相交
點在任意多邊形內的判定
點在凸多邊形內的判定

經典問題
最小外接圓
近似O(n)的最小外接圓演算法
點集直徑
旋轉卡殼，對踵點
多邊形的三角剖分

數學 / 數論

最大公約數
Euclid演算法
擴展的Euclid演算法
同餘方程 / 二元一次不定方程
同餘方程組

線性方程組
高斯消元法
解mod 2域上的線性方程組
整系數方程組的精確解法

矩陣
行列式的計算
利用矩陣乘法快速計算遞推關系

分數
分數樹
連分數逼近

數論計算
求N的約數個數
求phi(N)
求約數和
快速數論變換
……

素數問題
概率判素演算法
概率因子分解

數據結構

組織結構
二叉堆
左偏樹
二項樹
勝者樹
跳躍表
樣式圖標
斜堆
reap

統計結構
樹狀數組
虛二叉樹
線段樹
矩形面積並
圓形面積並

關系結構
Hash表
並查集
路徑壓縮思想的應用

STL中的數據結構
vector
deque
set / map

動態規劃 / 記憶化搜索

動態規劃和記憶化搜索在思考方式上的區別

最長子序列系列問題
最長不下降子序列
最長公共子序列
最長公共不下降子序列

一類NP問題的動態規劃解法

樹型動態規劃

背包問題

動態規劃的優化
四邊形不等式
函數的凸凹性
狀態設計
規劃方向

線性規劃

常用思想

二分
最小表示法

串

KMP
Trie結構
後綴樹/後綴數組
LCA/RMQ
有限狀態自動機理論

排序
選擇/冒泡
快速排序
堆排序
歸並排序
基數排序
拓撲排序
排序網路

3. 排序演算法的時間復雜度如何

排序演算法的時間復雜度是若文件的初始狀態是正序的，一趟掃描即可完成排序。

比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。

次線性時間

對於一個演算法，若其匹配T(n) = o(n)，則其時間復雜度為次線性時間（sub-linear time或sublinear time）。實際上除了匹配以上定義的演算法，其他一些演算法也擁有次線性時間的時間復雜度。例如有O(n)葛羅佛搜索演算法。

常見的非合次線性時間演算法都採用了諸如平行處理（就像NC1matrix行列式計算那樣）、非古典處理（如同葛羅佛搜索那樣），又或者選擇性地對有保證的輸入結構作出假設（如冪對數時間的二分搜索）。

不過，一些情況，例如在頭 log(n) 比特中每個字元串有一個比特作為索引的字元串組就可能依賴於輸入的每個比特，但又匹配次線性時間的條件。

「次線性時間演算法」通常指那些不匹配前一段的描述的演算法。它們通常運行於傳統計算機架構系列並且不容許任何對輸入的事先假設。但是它們可以是隨機化演算法，而且必須是真隨機演算法除了特殊情況。

4. 用線性時間復雜度的演算法將給定序列調整為最大堆什麼意思

線性時間復雜度，就是時間復雜度為線性階O(n)。同一問題可用不同演算法解決，而一個演算法的質陵圓褲量優劣（或者說演算法復雜度）尺簡可由時間復雜腔戚度和空間復雜度來評價。演算法的時間復雜度是指執行演算法所需要的計算工作量，即度量演算法執行的時間長短，它定量描述了該演算法的運行時間。按數量級遞增排列，常見的時間復雜度有：常數階O(1),對數階O(log2n),線性階O(n),線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...。隨著問題規模n的不斷增大，時間復雜度不斷增大，演算法的執行效率越低。

5. 歸並排序

先考慮一個簡單的問題：如何在線性的時間內將兩個有序隊列合並為一個有序隊列（並輸出）？

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9

看上面的例子，AB兩個序列都是已經有序的了。在給出數據已經有序的情況下，我們會發現很多神奇的事，比如，我們將要輸出的第一個數一定來自於這兩個序列各自最前面的那個數。兩個數都是1，那麼我們隨便取出一個（比如A隊列的那個1）並輸出：

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1

注意，我們取出了一個數，在原數列中刪除這個數。刪除操作是通過移動隊首指針實現的，否則復雜度就高了。
現在，A隊列打頭的數變成3了，B隊列的隊首仍然是1。此時，我們再比較3和1哪個大並輸出小的那個數：

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1 1

接下來的幾步如下：

A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9
B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ……
輸出：1 1 2 輸出：1 1 2 3 輸出：1 1 2 3 5 輸出：1 1 2 3 5 7

我希望你明白了這是怎麼做的。這個做法顯然是正確的，復雜度顯然是線性。

歸並排序(Merge Sort)將會用到上面所說的合並操作。給出一個數列，歸並排序利用合並操作在O(nlogn)的時間內將數列從小到大排序。歸並排序用的是分治(Divide and Conquer)的思想。首先我們把給出的數列平分為左右兩段，然後對兩段數列分別進行排序，最後用剛才的合並演算法把這兩段（已經排過序的）數列合並為一個數列。有人會問「對左右兩段數列分別排序時用的什麼排序」么？答案是：用歸並排序。也就是說，我們遞歸地把每一段數列又分成兩段進行上述操作。你不需要關心實際上是怎麼操作的，我們的程序代碼將遞歸調用該過程直到數列不能再分（只有一個數）為止。
初看這個演算法時有人會誤以為時間復雜度相當高。我們下面給出的一個圖將用非遞歸的眼光來看歸並排序的實際操作過程，供大家參考。我們可以藉助這個圖證明，歸並排序演算法的時間復雜度為O(nlogn)。

[3] [1] [4] [1] [5] [9] [2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2 7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]

上圖中的每一個「 \ / 」表示的是上文所述的線性時間合並操作。上圖用了4行來圖解歸並排序。如果有n個數，表示成上圖顯然需要O(logn)行。每一行的合並操作復雜度總和都是O(n)，那麼logn行的總復雜度為O(nlogn)。這相當於用遞歸樹的方法對歸並排序的復雜度進行了分析。假設，歸並排序的復雜度為T(n)，T(n)由兩個T(n/2)和一個關於n的線性時間組成，那麼T(n)=2*T(n/2)+O(n)。不斷展開這個式子我們可以同樣可以得到T(n)=O(nlogn)的結論，你可以自己試試。如果你能在線性的時間里把分別計算出的兩組不同數據的結果合並在一起，根據T(n)=2*T(n/2)+O(n)=O(nlogn)，那麼我們就可以構造O(nlogn)的分治演算法。這個結論後面經常用。我們將在計算幾何部分舉一大堆類似的例子。
如果你第一次見到這么詭異的演算法，你可能會對這個感興趣。分治是遞歸的一種應用。這是我們第一次接觸遞歸運算。下面說的快速排序也是用的遞歸的思想。遞歸程序的復雜度分析通常和上面一樣，主定理(Master Theory)可以簡化這個分析過程。主定理和本文內容離得太遠，我們以後也不會用它，因此我們不介紹它，大家可以自己去查。有個名詞在這里的話找學習資料將變得非常容易，我最怕的就是一個東西不知道叫什麼名字，半天找不到資料。

歸並排序有一個有趣的副產品。利用歸並排序能夠在O(nlogn)的時間里計算出給定序列里逆序對的個數。你可以用任何一種平衡二叉樹來完成這個操作，但用歸並排序統計逆序對更方便。我們討論逆序對一般是說的一個排列中的逆序對，因此這里我們假設所有數不相同。假如我們想要數1, 6, 3, 2, 5, 4中有多少個逆序對，我們首先把這個數列分為左右兩段。那麼一個逆序對只可能有三種情況：兩個數都在左邊，兩個數都在右邊，一個在左一個在右。在左右兩段分別處理完後，線性合並的過程中我們可以順便算出所有第三種情況的逆序對有多少個。換句話說，我們能在線性的時間里統計出A隊列的某個數比B隊列的某個數大有多少種情況。

A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6
B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ……
輸出： 輸出：1 輸出：1 2 輸出：1 2 3 輸出：1 2 3 4

每一次從B隊列取出一個數時，我們就知道了在A隊列中有多少個數比B隊列的這個數大，它等於A隊列現在還剩的數的個數。比如，當我們從B隊列中取出2時，我們同時知道了A隊列的3和6兩個數比2大。在合並操作中我們不斷更新A隊列中還剩幾個數，在每次從B隊列中取出一個數時把當前A隊列剩的數目加進最終答案里。這樣我們算出了所有「大的數在前一半，小的數在後一半」的情況，其餘情況下的逆序對在這之前已經被遞歸地算過了。

============================華麗的分割線============================

堆排序(Heap Sort)利用了堆(Heap)這種數據結構（什麼是堆？）。堆的插入操作是平均常數的，而刪除一個根節點需要花費O(log n)的時間。因此，完成堆排序需要線性時間建立堆（把所有元素依次插入一個堆），然後用總共O(nlogn)的時間不斷取出最小的那個數。只要堆會搞，堆排序就會搞。堆在那篇日誌里有詳細的說明，因此這里不重復說了。

============================華麗的分割線============================

快速排序(Quick Sort)也應用了遞歸的思想。我們想要把給定序列分成兩段，並對這兩段分別進行排序。一種不錯的想法是，選取一個數作為「關鍵字」，並把其它數分割為兩部分，把所有小於關鍵字的數都放在關鍵字的左邊，大於關鍵字的都放在右邊，然後遞歸地對左邊和右邊進行排序。把該區間內的所有數依次與關鍵字比較，我們就可以在線性的時間里完成分割的操作。完成分割操作有很多有技巧性的實現方法，比如最常用的一種是定義兩個指針，一個從前往後找找到比關鍵字大的，一個從後往前找到比關鍵字小的，然後兩個指針對應的元素交換位置並繼續移動指針重復剛才的過程。這只是大致的方法，具體的實現還有很多細節問題。快速排序是我們最常用的代碼之一，網上的快速排序代碼五花八門，各種語言，各種風格的都有。大家可以隨便找一個來看看，我說過了我們講演算法但不講如何實現。NOIp很簡單，很多人NOIp前就背了一個快速排序代碼就上戰場了。當時我把快速排序背完了，抓緊時間還順便背了一下歷史，免得晚上聽寫又不及格。
不像歸並排序，快速排序的時間復雜度很難計算。我們可以看到，歸並排序的復雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是O(n^2)的。如果每一次選的關鍵字都是當前區間里最大（或最小）的數，那麼這樣將使得每一次的規模只減小一個數，這和插入排序、選擇排序等平方級排序沒有區別。這種情況不是不可能發生。如果你每次選擇關鍵字都是選擇的該區間的第一個數，而給你的數據恰好又是已經有序的，那你的快速排序就完蛋了。顯然，最好情況是每一次選的數正好就是中位數，這將把該區間平分為兩段，復雜度和前面討論的歸並排序一模一樣。根據這一點，快速排序有一些常用的優化。比如，我們經常從數列中隨機取一個數當作是關鍵字（而不是每次總是取固定位置上的數），從而盡可能避免某些特殊的數據所導致的低效。更好的做法是隨機取三個數並選擇這三個數的中位數作為關鍵字。而對三個數的隨機取值反而將花費更多的時間，因此我們的這三個數可以分別取數列的頭一個數、末一個數和正中間那個數。另外，當遞歸到了一定深度發現當前區間里的數只有幾個或十幾個時，繼續遞歸下去反而費時，不如返回插入排序後的結果。這種方法同時避免了當數字太少時遞歸操作出錯的可能。

下面我們證明，快速排序演算法的平均復雜度為O(nlogn)。不同的書上有不同的解釋方法，這里我選用演算法導論上的講法。它更有技巧性一些，更有趣一些，需要轉幾個彎才能想明白。
看一看快速排序的代碼。正如我們提到過的那種分割方法，程序在經過若干次與關鍵字的比較後才進行一次交換，因此比較的次數比交換次數更多。我們通過證明一次快速排序中元素之間的比較次數平均為O(nlogn)來說明快速排序演算法的平均復雜度。證明的關鍵在於，我們需要算出某兩個元素在整個演算法過程中進行過比較的概率。
我們舉一個例子。假如給出了1到10這10個數，第一次選擇關鍵字7將它們分成了{1,2,3,4,5,6}和{8,9,10}兩部分，遞歸左邊時我們選擇了3作為關鍵字，使得左部分又被分割為{1,2}和{4,5,6}。我們看到，數字7與其它所有數都比較過一次，這樣才能實現分割操作。同樣地，1到6這6個數都需要與3進行一次比較（除了它本身之外）。然而，3和9決不可能相互比較過，2和6也不可能進行過比較，因為第一次出現在3和9，2和6之間的關鍵字把它們分割開了。也就是說，兩個數A(i)和A(j)比較過，當且僅當第一個滿足A(i)<=x<=A(j)的關鍵字x恰好就是A(i)或A(j) （假設A(i)比A(j)小）。我們稱排序後第i小的數為Z(i)，假設i<j，那麼第一次出現在Z(i)和Z(j)之間的關鍵字恰好就是Z(i)或Z(j)的概率為2/(j-i+1)，這是因為當Z(i)和Z(j)之間還不曾有過關鍵字時，Z(i)和Z(j)處於同一個待分割的區間，不管這個區間有多大，不管遞歸到哪裡了，關鍵字的選擇總是隨機的。我們得到，Z(i)和Z(j)在一次快速排序中曾經比較過的概率為2/(j-i+1)。
現在有四個數，2,3,5,7。排序時，相鄰的兩個數肯定都被比較過，2和5、3和7都有2/3的概率被比較過，2和7之間被比較過有2/4的可能。也就是說，如果對這四個數做12次快速排序，那麼2和3、3和5、5和7之間一共比較了12*3=36次，2和5、3和7之間總共比較了8*2=16次，2和7之間平均比較了6次。那麼，12次排序中總的比較次數期望值為36+16+6=58。我們可以計算出單次的快速排序平均比較了多少次：58/12=29/6。其實，它就等於6項概率之和，1+1+1+2/3+2/3+2/4=29/6。這其實是與期望值相關的一個公式。
同樣地，如果有n個數，那麼快速排序平均需要的比較次數可以寫成下面的式子。令k=j-i，我們能夠最終得到比較次數的期望值為O(nlogn)。

這里用到了一個知識：1+1/2+1/3+...+1/n與log n增長速度相同，即∑(1/n)=Θ(log n)。它的證明放在本文的最後。

在三種O(nlogn)的排序演算法中，快速排序的理論復雜度最不理想，除了它以外今天說的另外兩種演算法都是以最壞情況O(nlogn)的復雜度進行排序。但實踐上看快速排序效率最高（不然為啥叫快速排序呢），原因在於快速排序的代碼比其它同復雜度的演算法更簡潔，常數時間更小。

快速排序也有一個有趣的副產品：快速選擇給出的一些數中第k小的數。一種簡單的方法是使用上述任一種O(nlogn)的演算法對這些數進行排序並返回排序後數組的第k個元素。快速選擇(Quick Select)演算法可以在平均O(n)的時間完成這一操作。它的最壞情況同快速排序一樣，也是O(n^2)。在每一次分割後，我們都可以知道比關鍵字小的數有多少個，從而確定了關鍵字在所有數中是第幾小的。我們假設關鍵字是第m小。如果k=m，那麼我們就找到了答案——第k小元素即該關鍵字。否則，我們遞歸地計算左邊或者右邊：當k<m時，我們遞歸地尋找左邊的元素中第k小的；當k>m時，我們遞歸地尋找右邊的元素中第k-m小的數。由於我們不考慮所有的數的順序，只需要遞歸其中的一邊，因此復雜度大大降低。復雜度平均線性，我們不再具體證了。
還有一種演算法可以在最壞O(n)的時間里找出第k小元素。那是我見過的所有演算法中最沒有實用價值的演算法。那個O(n)只有理論價值。

============================華麗的分割線============================

我們前面證明過，僅僅依靠交換相鄰元素的操作，復雜度只能達到O(n^2)。於是，人們嘗試交換距離更遠的元素。當人們發現O(nlogn)的排序演算法似乎已經是極限的時候，又是什麼制約了復雜度的下界呢？我們將要討論的是更底層的東西。我們仍然假設所有的數都不相等。
我們總是不斷在數與數之間進行比較。你可以試試，只用4次比較絕對不可能給4個數排出順序。每多進行一次比較我們就又多知道了一個大小關系，從4次比較中一共可以獲知4個大小關系。4個大小關系共有2^4=16種組合方式，而4個數的順序一共有4!=24種。也就是說，4次比較可能出現的結果數目不足以區分24種可能的順序。更一般地，給你n個數叫你排序，可能的答案共有n!個，k次比較只能區分2^k種可能，於是只有2^k>=n!時才有可能排出順序。等號兩邊取對數，於是，給n個數排序至少需要log2(n!)次。注意，我們並沒有說明一定能通過log2(n!)次比較排出順序。雖然2^5=32超過了4!，但這不足以說明5次比較一定足夠。如何用5次比較確定4個數的大小關系還需要進一步研究。第一次例外發生在n=12的時候，雖然2^29>12!，但現已證明給12個數排序最少需要30次比較。我們可以證明log(n!)的增長速度與nlogn相同，即log(n!)=Θ(nlogn)。這是排序所需要的最少的比較次數，它給出了排序復雜度的一個下界。log(n!)=Θ(nlogn)的證明也附在本文最後。
這篇日誌的第三題中證明log2(N)是最優時用到了幾乎相同的方法。那種「用天平稱出重量不同的那個球至少要稱幾次」一類題目也可以用這種方法來解決。事實上，這里有一整套的理論，它叫做資訊理論。資訊理論是由香農(Shannon)提出的。他用對數來表示信息量，用熵來表示可能的情況的隨機性，通過運算可以知道你目前得到的信息能夠怎樣影響最終結果的確定。如果我們的信息量是以2為底的，那資訊理論就變成信息學了。從根本上說，計算機的一切信息就是以2為底的信息量(bits=binary digits)，因此我們常說香農是數字通信之父。資訊理論和熱力學關系密切，比如熵的概念是直接從熱力學的熵定義引申過來的。和這個有關的東西已經嚴重偏題了，這里不說了，有興趣可以去看《資訊理論與編碼理論》。我對這個也很有興趣，半懂不懂的，很想了解更多的東西，有興趣的同志不妨加入討論。物理學真的很神奇，利用物理學可以解決很多純數學問題，我有時間的話可以舉一些例子。我他媽的為啥要選文科呢。
後面將介紹的三種排序是線性時間復雜度，因為，它們排序時根本不是通過互相比較來確定大小關系的。

附1：∑(1/n)=Θ(log n)的證明
首先我們證明，∑(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/2，使得兩個1/2加起來湊成一個1；再把1/5,1/6和1/7全部變成1/4，這樣四個1/4加起來又是一個1。我們把所有1/2^k的後面2^k-1項全部擴大為1/2^k，使得這2^k個分式加起來是一個1。現在，1+1/2+...+1/n裡面產生了幾個1呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的擴大後原式各項總和為log n。O(logn)是∑(1/n)的復雜度上界。
然後我們證明，∑(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/4，使得兩個1/4加起來湊成一個1/2；再把1/5,1/6和1/7全部變成1/8，這樣四個1/8加起來又是一個1/2。我們把所有1/2^k的前面2^k-1項全部縮小為1/2^k，使得這2^k個分式加起來是一個1/2。現在，1+1/2+...+1/n裡面產生了幾個1/2呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的縮小後原式各項總和為1/2*logn。Ω(logn)是∑(1/n)的復雜度下界。

附2：log(n!)=Θ(nlogn)的證明
首先我們證明，log(n!)=O(nlogn)。顯然n!<n^n，兩邊取對數我們得到log(n!)<log(n^n)，而log(n^n)就等於nlogn。因此，O(nlogn)是log(n!)的復雜度上界。
然後我們證明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)....1，把前面一半的因子全部縮小到n/2，後面一半因子全部捨去，顯然有n!>(n/2)^(n/2)。兩邊取對數，log(n!)>(n/2)log(n/2)，後者即Ω(nlogn)。因此，Ω(nlogn)是log(n!)的復雜度下界。

今天寫到這里了，大家幫忙校對哦
Matrix67原創
轉貼請註明出處

6. 演算法的時間復雜度是指什麼

演算法的時間復雜度是指該演算法舉虛枯所需要的計算工作量隨問題規模增加而增加的趨勢，也就是演算法的運行時間與問題規模之間的關系。

1、演算法時間復雜度的概念

演算法時間復雜度是指在分析演算法性能時，關注的是該演算法的計算復雜程度。主要是根據演算法中基本操作的執行次數來估算演算法的效率。演算法的時間復雜度在一定程度上衡量了演算法的好壞，是在進行演算法性能分析時的一項基本指標。

2、計算時間復雜度的方法

通過代碼分析可以得出一個演算法的時間復雜度，一般採用大O表示法。大O表示法是一種用於描述演算法復雜度的表示方法。

用一個大O符號加上一個括弧括起來的函數描述演算法復雜度，在大O符號後面的函數里，n表示數據輸入的總量，T(n)表示演算法執行所需的時間復雜度函數。

5、總結：

演算法的時間復雜度是分析演算法效率的一種常用指標，可以通過大O記號表示演算法需要執行的操作次數，常見類型包括常數時間復雜度、線性時間復雜度、對數時間復雜度、平方時間復雜度和指數時間復雜度。

在實際應用中，需要根據具體需求綜合考慮時間復雜度和空間復雜度。

7. NOI考試的內容是什麼

1 時間復雜度（漸近時間復雜度的嚴格定義，NP問題，時間復雜度的分析方法，主定理）
2 排序演算法（平方排序演算法的應用，Shell排序，快速排序，歸並排序，時間復雜度下界，三種線性時間排序，外部排序）
3 數論（整除，集合論，關系，素數，進位制，輾轉相除，擴展的輾轉相除，同餘運算，解線性同餘方程，中國剩餘定理）
4 指針（鏈表，搜索判重，鄰接表，開散列，二叉樹的表示，多叉樹的表示）
5 按位運算（and，or，xor，shl，shr，一些應用）
6 圖論（圖論模型的建立，平面圖，歐拉公式與五色定理，求強連通分量，求割點和橋，歐拉迴路，AOV問題，AOE問題，最小生成樹的三種演算法，最短路的三種算 法，標號法，差分約束系統，驗證二分圖，Konig定理，匈牙利演算法，KM演算法，穩定婚姻系統，最大流演算法，最小割最大流定理，最小費用最大流演算法）
7 計算幾何（平面解幾及其應用，向量，點積及其應用，叉積及其應用，半平面相交，求點集的凸包，最近點對問題，凸多邊形的交，離散化與掃描）
8 數據結構（廣度優先搜索，驗證括弧匹配，表達式計算，遞歸的編譯，Hash表，分段Hash，並查集，Tarjan演算法，二叉堆，左偏樹，斜堆，二項堆，二叉查找樹，AVL，Treap，Splay，靜態二叉查找樹，2-d樹，線段樹，二維線段樹，矩形樹，Trie樹，塊狀鏈表）
9 組合數學（排列與組合，鴿籠原理，容斥原理，遞推，Fibonacci數列，Catalan數列，Stirling數，差分序列，生成函數，置換，Polya原理）
10 概率論（簡單概率，條件概率，Bayes定理，期望值）
11 矩陣（矩陣的概念和運算，二分求解線性遞推方程，多米諾骨牌棋盤覆蓋方案數，高斯消元）
12 字元串處理（KMP，後綴樹，有限狀態自動機，Huffman編碼，簡單密碼學）
13 動態規劃（單調隊列，凸完全單調性，樹型動規，多叉轉二叉，狀態壓縮類動規，四邊形不等式）
14 博奕論（Nim取子游戲，博弈樹，Shannon開關游戲）
15 搜索（A*，ID，IDA*，隨機調整，遺傳演算法）
16 微積分初步（極限思想，導數，積分，定積分，立體解析幾何）

8. Java怎麼用線性同餘法跟取余法一起產生一個序列。

亂數是不重復的隨機數嗎?

很多演算法的每一個計算步驟都是固定的，而在下面我們要討論的概率演算法，允許演算法在執行的過程中隨機選擇下一個計算步驟。許多情況下，當演算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率演算法可在很大程度上降低演算法的復雜度。
概率演算法的一個基本特徵是對所求解問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下，可將概率演算法大致分為四類:數值概率演算法，蒙特卡羅(Monte Carlo)演算法，拉斯維加斯(Las Vegas)演算法和舍伍德(Sherwood)演算法。
數值概率演算法常用於數值問題的求解。這類演算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數值概率演算法可得到相當滿意的解。
蒙特卡羅演算法用於求問題的准確解。對於許多問題來說，近似解毫無意義。例如，一個判定問題其解為「是」或「否」，二者必居其一，不存在任何近似解答。又如，我們要求一個整數的因子時所給出的解答必須是准確的，一個整數的近似因子沒有任何意義。用蒙特卡羅演算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴於演算法所用的時間。演算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅演算法的主要缺點就在於此。一般情況下，無法有效判斷得到的解是否肯定正確。
拉斯維加斯演算法不會得到不正確的解，一旦用拉斯維加斯演算法找到一個解，那麼這個解肯定是正確的。但是有時候用拉斯維加斯演算法可能找不到解。與蒙特卡羅演算法類似。拉斯維加斯演算法得到正確解的概率隨著它用的計算時間的增加而提高。對於所求解問題的任一實例，用同一拉斯維加斯演算法反復對該實例求解足夠多次，可使求解失效的概率任意小。
舍伍德演算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性演算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定演算法中引入隨機性將它改造成一個舍伍德演算法，消除或減少問題的好壞實例間的這種差別。舍伍德演算法精髓不是避免演算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關聯性。
本文簡要的介紹一下數值概率演算法和舍伍德演算法。
首先來談談隨機數。隨機數在概率演算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在概率演算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。
產生隨機數最常用的方法是線性同餘法。由線性同餘法產生的隨機序列a1,a2,...,an滿足
a0=d
an=(ban-1+c)mod m n=1,2.......
其中,b>=0, c>=0, d>=m。d稱為該隨機序列的種子。
下面我們建立一個隨機數類RadomNumber，該類包含一個由用戶初始化的種子randSeed。給定種子之後，既可產生與之相應的隨機數序列。randseed是一個無符號長整型數，既可由用戶指定也可由系統時間自動產生。
const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;
class RandomNumber
{
private:
//當前種子
unsigned long randseed;
public:
//構造函數，預設值0表示由系統自動產生種子
RandomNumber(unsigned long s=0);
//產生0-n-1之間的隨機整數
unsigned short Random(unsigned long n);
//產生[0，1)之間的隨機實數
double fRandom(void);
};
RandomNumber::RandomNumber(unsigned long s)
{
if(s==0)
randseed=time(0);
else
randseed=s;
}
unsigned short RandomNumber::Random(unsigned long n)
{
randseed=multiplier*randseed+adder;
return (unsigned short)((randseed>>16)%n);
}
double RandomNumber::fRandom(void)
{
return Random(maxshort)/double(maxshort);
}
函數Random在每次計算時，用線性同餘式計算新的種子。它的高16位的隨機性較好，將randseed右移16位得到一個0-65535之間的隨機整數然後再將此隨機整數映射到0-n-1范圍內。
對於函數fRandom,先用Random(maxshort)產生一個0-(maxshort-1之間的整型隨機序列)，將每個整型隨機數除以maxshort，就得到[0，1)區間中的隨機實數。
下面來看看數值概率演算法的兩個例子:
1.用隨機投點法計算π
設有一半徑為r的圓及其外切四邊形，如圖所示。向該正方形隨機投擲n個點。設落入圓內的點在正方形上均勻分布，因而所投入點落入圓內的概率為 πr^2/4r^2，所以當n足夠大時，k與n之比就逼近這一概率，即π/4。由此可得使用隨機投點法計算π值的數值概率演算法。具體實現時，只需要在第一次象限計算即可。

double Darts(int n)
{
static RandomNumber dart;
int k=0;
for(int i=1;i<=n;i++){
double x=dart.fRandom();
double y=dart.fRandom();
if((x*x+y*y)<1)
k++;
}
return 4*k/double(n);
}
再簡單舉個舍伍德演算法的例子。
我們在分析一個演算法在平均情況下的計算復雜性時，通常假定演算法的輸入數據服從某一特定的概率分布。例如，在輸入數據是均勻分布時，快速排序演算法所需的平均時間是O(n logn)。但是如果其輸入已經基本上排好序時，所用時間就大大增加了。此時，可採用舍伍德演算法消除演算法所需計算時間與輸入實例間的這種聯系。
在這里，我們用舍伍德型選擇演算法隨機的選擇一個數組元素作為劃分標准。這樣既能保證演算法的線性時間平均性能又避免了計算擬中位數的麻煩。非遞歸的舍伍德型演算法可描述如下:
template<class Type>
Type select(Type a[], int l, int r, int k)
{
static RandomNumber rnd;
while(true){
if(l>=r)
return a[l];
int i=l, j=l=rnd.Random(r-l+1);
Swap(a[i], a[j]);
j=r+1;
Type pivot=a[l];
while(true)
{
while(a[++i]<pivot);
while(a[--j]>pivot);
if(i>=j)
break;
Swap(a[i], a[j]);
}
if(j-l+1==k)
return pivot;
a[l]=a[j];
a[j]=pivot;
if(j-l+1<k)
{
k=k-j+l-1;
l=j+1;
}
else
r=j-1;
}
}
template <class Type>
Type Select(Type a[], int n, int k)
{
if(k<1||k>n)
throw OutOfBounds();
return select(a, 0, n-1, k);
}
平時我們一般開始考慮的是一個有著很好平均性能的選擇演算法，但在最壞情況下對某些實例演算法效率較低。這時候我們用概率演算法，將上述演算法改造成一個舍伍德型演算法，使得該演算法對任何實例均有效。
不過在有些情況下，所給的確定性演算法無法直接改造成舍伍德型演算法。這時候就可以藉助隨機預處理技術，不改變原有的確定性演算法，僅對其輸入進行隨機洗牌，同樣可以得到舍伍德演算法的效果。還是剛才的例子，換一種方法實現:
template<class Type>
void Shuffle(Type a[], int n)
{
static RandomNumber rnd;
for(int i=1;i<n;i++){
int j=rnd.Random(n-i)+i;
Swap(a[i], a[j]);
}
}

9. 《漫畫演算法》—— 【3】樹

在樹的結構中，樹的定義如下。
樹（tree）是n（n>=0）個節點的有限集，當n=0時，稱為空樹。在任意一個非空樹中，有如下特點：

1、有且僅有一個特定的稱為根的節點。
2、當n>1時，其餘節點可分為m(m>0)個互不相交的有限集，每一個集合本身又是一個樹，並稱為根的子樹。

【相關節點】

樹的最大層級樹，被稱為樹的高度或深度。

樹的每個節點最多有2個孩子節點。
樹的一種特殊形式。樹的每個節點 最多有2個孩子節點 。

二叉樹的兩個孩子節點，一個被稱為 左孩子 ，一個被稱為 右孩子 。這兩個孩子節點的順序是固定的。

二叉樹有兩種特殊形式：滿二叉樹、完全二叉樹。

滿二叉樹 ：一個二叉樹的所有非葉子節點都存在左右孩子，並且所有葉子節點都在同一層接上。簡言之，滿二叉樹的每一個分支都是滿的。

完全二叉樹 ：對一個有n個節點的二叉樹，按層級順序編號，則所有節點的編號為從1到n。如果這個樹所有節點和同樣深度的滿二叉樹的編號為從1到n的節點位置相同，則這個二叉樹為完全二叉樹。

一棵樹，若為滿二叉樹，那麼一定是完全二叉樹。反之，不一定。

在內存中存儲 ：

為什麼這么設計？可以更方便的定位孩子節點、父節點。
若父節點的下標是parent，那麼左孩子節點下標是2 parent+1，右孩子節點下標是2 parent+2。
反之，若左孩子節點下標是leftChild,那麼父節點下標是(leftChild - 1)/2。
稀疏二叉樹，用數組表示會很浪費空間。

二叉樹的應用：查找操作、維持相對順序。

1、查找

二叉查找樹在二叉樹的基礎上增加了以下幾個條件：

如果左子樹不為空，則左子樹上所有節點的值均小於根節點的值；
如果右子樹不為空，則右子樹上所有節點的值均大於根節點的值；
左、右子樹也都是二叉查找樹。

對於一個節點分布相對均衡的二叉查找樹來說，如果節點總數是n，那麼搜索節點的 時間復鬧液雜度都是O(logn) ，和樹的深度是一樣的。

2、維液模物持相對順序（插入）

二叉查找樹的特性保證了二叉樹的有序碼爛性，因此還有另外一個名字：二叉排序樹。

插入的過程中，可能會出現需要二叉樹進行自平衡，例如下圖的情況：

如圖所示，不只是樹的外觀看起來怪異，查詢節點的時間復雜度也退化成了O(n)。

二叉樹的自平衡的方式有很多種，如紅黑樹、AVL樹、樹堆等。

二叉樹的遍歷：
從節點之間位置關系的角度：
* 前序遍歷：輸出順序：根節點、左子樹、右子樹
* 中序遍歷：輸出順序：左子樹、根節點、右子樹
* 後序遍歷：輸出順序：左子樹、右子樹、根節點
* 層序遍歷：按照從根節點到葉子節點的層級關系，一層一層橫向遍歷各個節點。

從更宏觀的角度:
* 深度優先遍歷(前、中、後序遍歷，前中後是相對根節點)
* 廣度優先遍歷(層序遍歷)

二叉堆：本質上是一種完全二叉樹。
二叉堆本質上是一種完全二叉樹，分為2個類型：

最大堆 ：任何一個父節點的值，都大於或等於它左、右孩子節點的值；
最小堆 ：任何一個父節點的值，都小於或等於它左、右孩子節點的值。
二叉堆的根節點，叫作 堆頂 。最大堆的堆頂是整個堆中最大元素，最小堆的堆頂是整個堆中最小元素。
二叉堆雖然是一個完全二叉樹，但它的存儲方式並不是鏈式存儲，而是順序存儲，如下圖所示：

假設父節點的下標是parent，那麼它的左孩子的下標就是 2 * parent + 1 ，右孩子的下標就是 2 * parent + 2 。

二叉堆的3種操作（假設是最小堆）：
1、插入節點：時間復雜度O(logn)
插入節點是通過「上浮」操作完成的：當二叉堆插入節點時，插入位置是完全二叉樹的最後一個位置，將該節點與它的父節點進行比較，如果該節點小於它的父節點，那麼該與它的父節點交換位置，直到比較到堆頂位置。
2、刪除節點：時間復雜度O(logn)
刪除節點是通過「下沉」操作完成的：將要刪除的節點看作是堆頂，只看該節點及它下面的部分。因為堆頂元素要進行刪除，將最後一個節點元素替換堆頂元素，將替換後的元素與它的左、右子樹進行比較，如果左、右孩子節點中最小的一個比該節點小，那麼該節點「下沉」，直到葉子節點。
3、構建二叉堆：時間復雜度O(n)
構建二叉堆，也就是把一個無序的完全二叉樹調整為二叉堆，本質就是讓所有非葉子節點一次「下沉」。

優先隊列不再遵循先入先出的原則，而是分為兩種情況：

最大優先隊列 ，無論入隊順序如何，都是當前最大的元素優先出隊；
最小優先隊列 ，無論入隊順序如何，都是當前最小的元素優先出隊。

二叉堆節點的「上浮」和「下沉」的時間復雜度都是O(logn)，所以優先隊列入隊和出隊的時間復雜度也是O(logn)。

https://blog.csdn.net/qq_28958301/article/details/91590545

10. 將長度為n的單鏈表鏈接在長度為m的單鏈表之後的演算法的時間復雜度為

要插入到長度為m的單鏈表，需要找到表尾，這個過程的時間復雜度為o(m)，連接的時間復雜度為o(1)，所以總的時間復雜度為o(m)，所以答案選C。

單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) +指針(指示後繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。

時間復雜度是同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。

時間復雜度的計算方法：

1、一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，謹緩鉛稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。

分析：隨著模塊n的增大，演算法執行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，演算法的時間復雜度越低，演算法的效率越哪磨高。

2、在計算時間復雜度的時候，先找出演算法祥好的基本操作，然後根據相應的各語句確定它的執行次數，再找出 T(n) 的同數量級，找出後，f(n) = 該數量級，若 T(n)/f(n) 求極限可得到一常數c，則時間復雜度T(n) = O(f(n))。

(10)通過線性時間演算法建立二叉堆擴展閱讀

單鏈表的建立有頭插法、尾插法兩種方法。

1、頭插法：

單鏈表是用戶不斷申請存儲單元和改變鏈接關系而得到的一種特殊數據結構，將鏈表的左邊稱為鏈頭，右邊稱為鏈尾。頭插法建單鏈表是將鏈表右端看成固定的，鏈表不斷向左延伸而得到的。頭插法最先得到的是尾結點。

由於鏈表的長度是隨機的，故用一個while循環來控制鏈表中結點個數。假設每個結點的值都大於O，則循環條件為輸入的值大於o。

申請存儲空間可使用malloc()函數實現，需設立一申請單元指針，但malloc()函數得到的指針並不是指向結構體的指針，需使用強制類型轉換，將其轉換成結構體型指針。剛開始時，鏈表還沒建立，是一空鏈表，head指針為NULL。

鏈表建立的過程是申請空間、得到數據、建立鏈接的循環處理過程。

2、尾插法：

若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為尾插法。尾插法建立鏈表時，頭指針固定不動，故必須設立一個搜索指針，向鏈表右邊延伸，則整個演算法中應設立三個鏈表指針，即頭指針head、搜索指針p2、申請單元指針pl。尾插法最先得到的是頭結點。