拓撲排序演算法復雜度

❶ 數據結構中排序和查找各種時間復雜度

數據結構中排序和查找各種時間復雜度
(1)冒泡排序
冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。
(2)選擇排序
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的。…… 例子說明好多了。序列5 8 5 2 9， 我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了， 所以選擇排序不穩定的排序演算法
(3)插入排序
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果和插入元素相等，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變。所以插入排序是穩定的。
(4)快速排序
快速排序有兩個方向，左邊的i下標一直往右走（往後），當a[i] <= a[center_index]，其中center_index是中樞元素的數組下標，一般取為數組第0個元素。而右邊的j下標一直往左走（往前），當a[j] > a[center_index]。如果i和j都走不動了，i <= j, 交換a[i]和a[j],重復上面的過程，直到i>j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為 5 3 3 4 3 8 9 10 11， 現在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩定性打亂，所以快速排序是一個不穩定的排序演算法。（不穩定發生在中樞元素和a[j]交換的時刻）
(5)歸並排序
歸並排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然後把各個有序的段序列合並成一個有序的長序列。不斷合並直到原序列全部排好序。相等時不發生交換。所以，歸並排序也是穩定的排序演算法。
(6)基數排序
基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優先順序排序，最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以其是穩定的排序演算法。
(7)希爾排序(shell)
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對於有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n^2)好一些。由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。
(8)堆排序
我們知道堆的結構是節點i的孩子為2*i和2*i+1節點，大頂堆要求父節點大於等於其2個子節點，小頂堆要求父節點小於等於其2個子節點。在一個長為n的序列，堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n/2-1, n/2-2, ...1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把後面一個元素交換過去了，而第n/2-1個父節點把後面一個相同的元素沒有交換，那麼這2個相同的元素之間的穩定性就被破壞了。所以，堆排序是不穩定的排序演算法
一、排序
排序法 平均時間 最差情形 穩定度 額外空間 備注
冒泡 O(n2) O(n2) 穩定 O(1) n小時較好
交換 O(n2) O(n2) 不穩定 O(1) n小時較好
選擇 O(n2) O(n2) 不穩定 O(1) n小時較好
插入 O(n2) O(n2) 穩定 O(1) 大部分已排序時較好
Shell O(nlogn) O(ns) 1<s<2 不穩定???="" o(1)???????="" s是所選分組</s
快速 O(nlogn) O(n2) 不穩定 O(nlogn) n大時較好
歸並 O(nlogn) O(nlogn) 穩定 O(1) n大時較好
堆 O(nlogn) O(nlogn) 不穩定 O(1) n大時較好
基數 O(logRB) O(logRB) 穩定 O(n) B是真數(0-9)，R是基數(個十百)
二、查找
未寫……
三 樹圖
克魯斯卡爾演算法的時間復雜度為O（eloge）
普里姆演算法的時間復雜度為O（n2）
迪傑斯特拉演算法的時間復雜度為O（n2）
拓撲排序演算法的時間復雜度為O（n+e）
關鍵路徑演算法的時間復雜度為O（n+e）

❷ 求詳解 pascal 拓撲排序

拓撲排序
有向無迴路圖又稱為dag。對這種有向無迴路圖的拓撲排序的結果為該圖所有頂點的一個線性序列，滿足如果G包含(u,v)，則在序列中u出現在v之前（如果圖是有迴路的就不可能存在這樣的線性序列)。一個圖的拓撲排序可以看成是圖的所有頂點沿水平線排成的一個序列，使得所有的有向邊均從左指向右。因此，拓撲排序不同於通常意義上對於線性表的排序。

有向無迴路圖經常用於說明事件發生的先後次序，圖1給出一個實例說明早晨穿衣的過程。必須先穿某一衣物才能再穿其他衣物(如先穿襪子後穿鞋)，也有一些衣物可以按任意次序穿戴(如襪子和短褲)。圖1(a)所示的圖中的有向邊(u,v)表明衣服u必須先於衣服v穿戴。因此該圖的拓撲排序給出了一個穿衣的順序。每個頂點旁標的是發現時刻與完成時刻。圖1(b)說明對該圖進行拓撲排序後將沿水平線方向形成一個頂點序列，使得圖中所有有向邊均從左指向右。

下列簡單演算法可以對一個有向無迴路圖進行拓撲排序。

procere Topological_Sort(G);
begin
1.調用DFS(G)計算每個頂點的完成時間f[v];
2.當每個頂點完成後，把它插入鏈表前端;
3.返回由頂點組成的鏈表;
end;
圖1(b)說明經拓撲排序的結點以與其完成時刻相反的順序出現。因為深度優先搜索的運行時間為θ(V+E)，每一個v中結點插入鏈表需佔用的時間為θ(1)，因此進行拓撲排序的運行時間θ(V+E)。

圖1 早晨穿衣的過程

為了證明演算法的正確性，我們運用了下面有關有向無迴路圖的重要引理。

引理1

有向圖G無迴路當且僅當對G進行深度優先搜索沒有得到反向邊。

證明：

→：假設有一條反向邊(u,v)，那麼在深度優先森林中結點v必為結點u的祖先，因此G中從v到u必存在一通路，這一通路和邊(u,v)構成一個迴路。

←：假設G中包含一迴路C，我們證明對G的深度優先搜索將產生一條反向邊。設v是迴路C中第一個被發現的結點且邊(u,v)是C中的優先邊，在時刻d[v]從v到u存在一條由白色結點組成的通路，根據白色路徑定理可知在深度優先森林中結點u必是結點v的後裔，因而(u,v)是一條反向邊。(證畢)

定理1

Topological_Sort(G)演算法可產生有向無迴路圖G的拓撲排序。

證明:

假設對一已知有問無迴路圖G=(V,E)運行過程DFS以確定其結點的完成時刻。那麼只要證明對任一對不同結點u,v∈V，若G中存在一條從u到v的有向邊，則f[v]<f[u]即可。考慮過程DFS(G)所探尋的任何邊(u,v)，當探尋到該邊時，結點v不可能為灰色，否則v將成為u的祖先，(u,v)將是一條反向邊，和引理1矛盾。因此，v必定是白色或黑色結點。若v是白色，它就成為u的後裔，因此f[v]<f[u]。若v是黑色，同樣f[v]<f[u]。這樣一來對於圖中任意邊(u,v)，都有f[v]<f[u]，從而定理得證。（證畢）

另一種拓撲排序的演算法基於以下思想：首先選擇一個無前驅的頂點（即入度為0的頂點，圖中至少應有一個這樣的頂點，否則肯定存在迴路），然後從圖中移去該頂點以及由他發出的所有有向邊，如果圖中還存在無前驅的頂點，則重復上述操作，直到操作無法進行。如果圖不為空，說明圖中存在迴路，無法進行拓撲排序；否則移出的頂點的順序就是對該圖的一個拓撲排序。

下面是該演算法的具體實現：

procere Topological_Sort_II(G);
begin
1 for 每個頂點u∈V[G] do d[u]←0; //初始化d[u],d[u]用來記錄頂點u的入度

2 for 每個頂點u∈V[G] do
3 for 每個頂點v∈Adj[u] do d[v]←d[v]+1; //統計每個頂點的入度

4 CreateStack(s); //建立一個堆棧s

5 for 每個頂點u∈V[G] do
6 if d[u]=0 then push(u,s); //將度為0的頂點壓入堆棧

7 count←0;

8 while (not Empty(s)) do
begin
9 u←top(s); //取出棧頂元素
10 pop(s); //彈出一個棧頂元素
11 count←count+1;
12 R[count]←u; //線性表R用來記錄拓撲排序的結果

13 for 每個頂點v∈Adj[u] do //對於每個和u相鄰的節點v
begin
14 d[v]←d[v]-1;
15 if d[v]=0 then push(v,s); //如果出現入度為0的頂點將其壓入棧
end;
end;

16 if count<>G.size then writeln('Error! The graph has cycle.')
17 else 按次序輸出R;
end;
上面的演算法中利用d[u]來記錄頂點u的入度，第2-3行用來統計所有頂點的入度，第5-6行將入度為0的頂點壓入堆棧，第8-15行不斷地從棧頂取出頂點，將該頂點輸出到拓撲序列中，並將所有與該頂點相鄰的頂點的入度減1，如果某個頂點的入度減至0，則壓入堆棧，重復該過程直到堆棧空了為止。顯而易見該演算法的復雜度為O(VE)，因為第2-3行的復雜性就是O(VE)，後面8-15行的復雜性也是O(VE)。這個演算法雖然簡單，但是沒有前面一個演算法的效率高。

❸ 採用鄰接表存儲，拓撲排序演算法的時間復雜度為多少

要看使用什麼樣的拓撲排序，最好的方法是輸出DFS的逆序，這樣的演算法復雜度是O(V+L),V是頂點個數，L是邊個數。

❹ 採用鄰接表存儲，拓撲排序演算法的時間復雜度為多少

要看使用什麼樣的拓撲排序，最好的方法是輸出DFS的逆序，這樣的演算法復雜度是O(V+L),V是頂點個數，L是邊個數。

❺ 拓撲排序時間復雜度o(n+e)怎麼算的

對有n個頂點和e條弧的有向圖而言，建立求各頂點的入度的時間復雜度為O(e)；建零入度頂點棧的時間復雜度為O(n)；在拓撲排序過程中，若有向圖無環，則每個頂點進一次棧、出一次棧，入度減1的操作在while語句中總共執行e次，所以總的時間復雜度為O(n+e)。

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前。

通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。

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

計算機科學中，演算法的時間復雜度是一個函數，它定性描述了該演算法的運行時間。這是一個關於代表演算法輸入值的字元串的長度的函數。

時間復雜度常用大O符號表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間復雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。

(5)拓撲排序演算法復雜度擴展閱讀

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

按數量級遞增排列，常見的時間復雜度有：

常數階O(1),線性階O(n),

線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，

k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

❻ 設圖 G 採用鄰接表存儲，則拓撲排序演算法的時間復雜度為（）

如果是鄰接表存儲，拓撲排序演算法的時間復雜度應該是O(n + e)，n是頂點個數，e是弧的數量

❼ 拓撲排序 pascal

拓撲排序
有向無迴路圖又稱為dag。對這種有向無迴路圖的拓撲排序的結果為該圖所有頂點的一個線性序列，滿足如果G包含(u,v)，則在序列中u出現在v之前（如果圖是有迴路的就不可能存在這樣的線性序列)。一個圖的拓撲排序可以看成是圖的所有頂點沿水平線排成的一個序列，使得所有的有向邊均從左指向右。因此，拓撲排序不同於通常意義上對於線性表的排序。

有向無迴路圖經常用於說明事件發生的先後次序，圖1給出一個實例說明早晨穿衣的過程。必須先穿某一衣物才能再穿其他衣物(如先穿襪子後穿鞋)，也有一些衣物可以按任意次序穿戴(如襪子和短褲)。圖1(a)所示的圖中的有向邊(u,v)表明衣服u必須先於衣服v穿戴。因此該圖的拓撲排序給出了一個穿衣的順序。每個頂點旁標的是發現時刻與完成時刻。圖1(b)說明對該圖進行拓撲排序後將沿水平線方向形成一個頂點序列，使得圖中所有有向邊均從左指向右。

下列簡單演算法可以對一個有向無迴路圖進行拓撲排序。

procere Topological_Sort(G);
begin
1.調用DFS(G)計算每個頂點的完成時間f[v];
2.當每個頂點完成後，把它插入鏈表前端;
3.返回由頂點組成的鏈表;
end;
圖1(b)說明經拓撲排序的結點以與其完成時刻相反的順序出現。因為深度優先搜索的運行時間為θ(V+E)，每一個v中結點插入鏈表需佔用的時間為θ(1)，因此進行拓撲排序的運行時間θ(V+E)。

圖1 早晨穿衣的過程

為了證明演算法的正確性，我們運用了下面有關有向無迴路圖的重要引理。

引理1

有向圖G無迴路當且僅當對G進行深度優先搜索沒有得到反向邊。

證明：

→：假設有一條反向邊(u,v)，那麼在深度優先森林中結點v必為結點u的祖先，因此G中從v到u必存在一通路，這一通路和邊(u,v)構成一個迴路。

←：假設G中包含一迴路C，我們證明對G的深度優先搜索將產生一條反向邊。設v是迴路C中第一個被發現的結點且邊(u,v)是C中的優先邊，在時刻d[v]從v到u存在一條由白色結點組成的通路，根據白色路徑定理可知在深度優先森林中結點u必是結點v的後裔，因而(u,v)是一條反向邊。(證畢)

定理1

Topological_Sort(G)演算法可產生有向無迴路圖G的拓撲排序。

證明:

假設對一已知有問無迴路圖G=(V,E)運行過程DFS以確定其結點的完成時刻。那麼只要證明對任一對不同結點u,v∈V，若G中存在一條從u到v的有向邊，則f[v]<f[u]即可。考慮過程DFS(G)所探尋的任何邊(u,v)，當探尋到該邊時，結點v不可能為灰色，否則v將成為u的祖先，(u,v)將是一條反向邊，和引理1矛盾。因此，v必定是白色或黑色結點。若v是白色，它就成為u的後裔，因此f[v]<f[u]。若v是黑色，同樣f[v]<f[u]。這樣一來對於圖中任意邊(u,v)，都有f[v]<f[u]，從而定理得證。（證畢）

另一種拓撲排序的演算法基於以下思想：首先選擇一個無前驅的頂點（即入度為0的頂點，圖中至少應有一個這樣的頂點，否則肯定存在迴路），然後從圖中移去該頂點以及由他發出的所有有向邊，如果圖中還存在無前驅的頂點，則重復上述操作，直到操作無法進行。如果圖不為空，說明圖中存在迴路，無法進行拓撲排序；否則移出的頂點的順序就是對該圖的一個拓撲排序。

下面是該演算法的具體實現：

procere Topological_Sort_II(G);
begin
1 for 每個頂點u∈V[G] do d[u]←0; //初始化d[u],d[u]用來記錄頂點u的入度

2 for 每個頂點u∈V[G] do
3 for 每個頂點v∈Adj[u] do d[v]←d[v]+1; //統計每個頂點的入度

4 CreateStack(s); //建立一個堆棧s

5 for 每個頂點u∈V[G] do
6 if d[u]=0 then push(u,s); //將度為0的頂點壓入堆棧

7 count←0;

8 while (not Empty(s)) do
begin
9 u←top(s); //取出棧頂元素
10 pop(s); //彈出一個棧頂元素
11 count←count+1;
12 R[count]←u; //線性表R用來記錄拓撲排序的結果

13 for 每個頂點v∈Adj[u] do //對於每個和u相鄰的節點v
begin
14 d[v]←d[v]-1;
15 if d[v]=0 then push(v,s); //如果出現入度為0的頂點將其壓入棧
end;
end;

16 if count<>G.size then writeln('Error! The graph has cycle.')
17 else 按次序輸出R;
end;
上面的演算法中利用d[u]來記錄頂點u的入度，第2-3行用來統計所有頂點的入度，第5-6行將入度為0的頂點壓入堆棧，第8-15行不斷地從棧頂取出頂點，將該頂點輸出到拓撲序列中，並將所有與該頂點相鄰的頂點的入度減1，如果某個頂點的入度減至0，則壓入堆棧，重復該過程直到堆棧空了為止。顯而易見該演算法的復雜度為O(VE)，因為第2-3行的復雜性就是O(VE)，後面8-15行的復雜性也是O(VE)。這個演算法雖然簡單，但是沒有前面一個演算法的效率高。

❽ 在用鄰接表表示圖時，拓撲排序演算法時間復雜度為多少

O（n + e）。
對於一個具有n個頂點e條弧的有向圖來說，剛開始將入度為0的頂點入棧的時間復雜為O(n)，在之後頂點出棧時，入度減1的操作共執行了e次，所以整個演算法的時間復雜度為O(n + e)。