如何用 Python 實(shí)現(xiàn)所有算法?

拓?fù)渑判蚧蛴邢驁D的拓?fù)渑判蚴瞧漤旤c(diǎn)的線(xiàn)性排序，使得對(duì)于從頂點(diǎn)u到頂點(diǎn)v的每個(gè)有向邊uv，u在排序中位于v之前。例如，圖的頂點(diǎn)可以表示要執(zhí)行的任務(wù)，并且邊可以表示一個(gè)任務(wù)必須在另一個(gè)之前執(zhí)行的約束；在這個(gè)應(yīng)用程序中，拓?fù)渑判蛑皇侨蝿?wù)的有效序列。當(dāng)且僅當(dāng)圖形沒(méi)有有向循環(huán)時(shí)，即，如果它是有向非循環(huán)圖，則拓?fù)渑判蚴强赡艿模―AG）。任何DAG都具有至少一個(gè)拓?fù)渑判?，并且已知算法用于在線(xiàn)性時(shí)間內(nèi)構(gòu)建任何DAG的拓?fù)渑判颉?/p>

時(shí)間復(fù)雜折線(xiàn)圖

比較排序算法的復(fù)雜性（冒泡排序，插入排序，選擇排序）

比較排序算法：

Quicksort是一種非?？焖俚乃惴ǎ珜?shí)現(xiàn)起來(lái)相當(dāng)棘手。Bubble sort是一種慢速算法，但很容易實(shí)現(xiàn)。為了對(duì)小數(shù)據(jù)集進(jìn)行排序，冒泡排序可能是一個(gè)更好的選擇。

搜索算法

線(xiàn)性搜索

線(xiàn)性搜索或順序搜索是用于在列表中查找目標(biāo)值的方法。它按順序檢查列表中的每個(gè)元素的目標(biāo)值，直到找到匹配或直到搜索完所有元素。

假設(shè)一個(gè)數(shù)組中有N個(gè)元素，最好的情況就是要尋找的特定值就是數(shù)組里的第一個(gè)元素，這樣僅需要1次比較就可以。而最壞的情況是要尋找的特定值不在這個(gè)數(shù)組或者是數(shù)組里的最后一個(gè)元素，這就需要進(jìn)行N次比較。

Binary 二進(jìn)制搜索

二進(jìn)制搜索，也稱(chēng)為半間隔搜索或?qū)?shù)搜索，用于查找已排序數(shù)組中目標(biāo)值的位置。它將目標(biāo)值與數(shù)組的中間元素進(jìn)行比較，如果它們不相等，則目標(biāo)的一半被消除，并且在剩下的一半上繼續(xù)搜索直到成功。

插值搜索

插值搜索是一種用于搜索已按照鍵值的數(shù)值排序的數(shù)組中鍵的算法。

最先由WW Peterson在1957年描述。插值搜索類(lèi)似于人們?cè)陔娫?huà)目錄中搜索名稱(chēng)的方法（用于訂購(gòu)書(shū)籍條目的關(guān)鍵值）：在每個(gè)步驟中，算法計(jì)算剩余搜索空間中的位置，基于搜索空間邊界處的鍵值和所尋找的鍵的值，通?？梢酝ㄟ^(guò)線(xiàn)性插值來(lái)尋找項(xiàng)目。

相比之下，二進(jìn)制搜索總是選擇剩余搜索空間的中間，丟棄一半或另一半，這取決于在估計(jì)位置找到的密鑰與所尋找的密鑰之間的比較。剩余的搜索空間縮小到估計(jì)位置之前或之后的部分。線(xiàn)性搜索僅使用相等性，因?yàn)樗鼜囊婚_(kāi)始就逐個(gè)比較元素，忽略任何排序。

平均插值搜索使得log（log（n））比較（如果元素均勻分布），其中n是要搜索的元素的數(shù)量。在最壞的情況下（例如，鍵的數(shù)值以指數(shù)方式增加），它可以構(gòu)成O（n）比較。

在插值順序搜索中，插值用于查找正在搜索的項(xiàng)目附近的項(xiàng)目，然后使用線(xiàn)性搜索來(lái)查找確切項(xiàng)目。

跳轉(zhuǎn)搜索

跳轉(zhuǎn)搜索是指有序列表的搜索算法。它首先檢查所有項(xiàng)目的Lkm，其中K∈N，并且m是塊大小，直到找到大于搜索關(guān)鍵字的項(xiàng)目。為了在列表中找到搜索關(guān)鍵字的確切位置，在子列表L[（k-1）m，km]上執(zhí)行線(xiàn)性搜索。

m的最優(yōu)值是√n，其中n是列表L的長(zhǎng)度。因?yàn)樗惴ǖ膬蓚€(gè)步驟最多都是√n項(xiàng)，所以算法在O（√n）時(shí)間內(nèi)運(yùn)行。這比線(xiàn)性搜索更好，但比二分搜索差。優(yōu)于后者的優(yōu)點(diǎn)是跳轉(zhuǎn)搜索只需要向后跳一次，而二進(jìn)制可以向后跳轉(zhuǎn)到記錄n次。

在最終執(zhí)行線(xiàn)性搜索之前，可以通過(guò)在子列表上執(zhí)行多級(jí)跳轉(zhuǎn)搜索來(lái)修改算法。對(duì)于k級(jí)跳躍搜索，第l級(jí)的最佳塊大小ml（從1開(kāi)始計(jì)數(shù)）是n（k1）/k。修改后的算法將執(zhí)行k個(gè)向后跳轉(zhuǎn)并在O（kn1/（k+ 1））時(shí)間內(nèi)運(yùn)行。

快速選擇算法

快速選擇（Quicksort）是一種從無(wú)序列表找到第k小元素的選擇算法。它從原理上來(lái)說(shuō)與快速排序有關(guān)。與快速排序一樣都由托尼·霍爾提出的，因而也被稱(chēng)為霍爾選擇算法。同樣地，它在實(shí)際應(yīng)用是一種高效的算法，具有很好的平均時(shí)間復(fù)雜度，然而最壞時(shí)間復(fù)雜度則不理想?？焖龠x擇及其變種是實(shí)際應(yīng)用中最常使用的高效選擇算法。

快速選擇的總體思路與快速排序一致，選擇一個(gè)元素作為基準(zhǔn)來(lái)對(duì)元素進(jìn)行分區(qū)，將小于和大于基準(zhǔn)的元素分在基準(zhǔn)左邊和右邊的兩個(gè)區(qū)域。不同的是，快速選擇并不遞歸訪(fǎng)問(wèn)雙邊，而是只遞歸進(jìn)入一邊的元素中繼續(xù)尋找。這降低了平均時(shí)間復(fù)雜度，從O(n log n)至O(n)，不過(guò)最壞情況仍然是O(n2)。

禁忌搜索

禁忌搜索(Tabu Search,TS,又稱(chēng)禁忌搜尋法）是一種現(xiàn)代啟發(fā)式算法，由美國(guó)科羅拉多大學(xué)教授Fred Glover在1986年左右提出的，是一個(gè)用來(lái)跳脫局部最優(yōu)解的搜索方法。其先創(chuàng)立一個(gè)初始化的方案；基于此，算法“移動(dòng)”到一相鄰的方案。經(jīng)過(guò)許多連續(xù)的移動(dòng)過(guò)程，提高解的質(zhì)量。

密碼

凱撒密碼

凱撒密碼，也稱(chēng)為凱撒密碼，移位密碼，凱撒代碼或凱撒移位，是最簡(jiǎn)單和最廣為人知的加密技術(shù)之一。

它是一種替換密碼，其中明文中的每個(gè)字母都被字母表中的一些固定數(shù)量的位置的字母替換。例如，左移3，D將被A替換，E將變?yōu)锽，依此類(lèi)推。

該方法以Julius Caesar的名字命名，最初是他在私人通信中使用了它。由Caesar密碼執(zhí)行的加密步驟通常作為更復(fù)雜的方案的一部分，例如Vigenère密碼，并且仍然在ROT13系統(tǒng)中具有現(xiàn)代應(yīng)用。與所有單字母替換密碼一樣，Caesar密碼很容易破解，在現(xiàn)代實(shí)踐中基本上沒(méi)有通信安全性。

Vigenère密碼

Vigenère密碼是一種通過(guò)使用基于關(guān)鍵字字母的一系列交織的凱撒密碼來(lái)加密字母文本的方法。它是一種多字母替代形式。

Vigenère密碼該方法最初由Giovan Battista Bellaso在其1553年的書(shū)“La cifra del”中提出。然而，該計(jì)劃后來(lái)在19世紀(jì)被誤用于BlaisedeVigenère，現(xiàn)在被廣泛稱(chēng)為“Vigenère密碼”。

雖然該密碼易于理解和實(shí)施，但三個(gè)世紀(jì)以來(lái)它一直抵制所有打破密碼的企圖，因此也被稱(chēng)為這lechiffreindéchiffrable（法語(yǔ)為“難以理解的密碼”）。Friedrich Kasiski是第一個(gè)在1863年發(fā)表破譯Vigenère密碼的通用方法。

轉(zhuǎn)置密碼

轉(zhuǎn)置密碼是一種加密方法，通過(guò)該加密方法，明文單元（通常是字符或字符組）所保持的位置根據(jù)常規(guī)系統(tǒng)移位，使得密文構(gòu)成明文的排列。也就是說(shuō)，單位的順序改變（明文被重新排序）。

在數(shù)學(xué)上，雙字符函數(shù)用于加密字符的位置和用于解密的反函數(shù)。

RSA (Rivest–Shamir–Adleman)

RSA加密算法是一種非對(duì)稱(chēng)加密算法。在公開(kāi)密鑰加密和電子商業(yè)中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_(kāi)頭字母拼在一起組成的。

1973年，在英國(guó)政府通訊總部工作的數(shù)學(xué)家克利福德·柯克斯（Clifford Cocks）在一個(gè)內(nèi)部文件中提出了一個(gè)與之等效的算法，但該算法被列入機(jī)密，直到1997年才得到公開(kāi)。

ROT13

ROT13（“旋轉(zhuǎn)13個(gè)位置”，有時(shí)用連字符ROT-13）是一個(gè)簡(jiǎn)單的字母替換密碼，用字母表后面的第13個(gè)字母替換一個(gè)字母。ROT13是古羅馬開(kāi)發(fā)的Caesar密碼的特例。

因?yàn)榛纠∽帜钢杏?6個(gè)字母（2×13），所以ROT13是自身的反轉(zhuǎn)，也就是說(shuō)，要撤消ROT13需要相同的算法，因此可以使用相同的動(dòng)作進(jìn)行編碼和解碼。該算法幾乎不提供加密安全性，并且經(jīng)常被引用為弱加密的典型示例。