演算法有正確性

『壹』 設計一個好的演算法通常要考慮哪些要求

數據結構中評價一個好的演算法，應該從四個方面來考慮，分別是：

一、演算法的正確性。

二、演算法的易讀性。

三、是演算法的健壯性。

四、是演算法的時空效率（運行）。

演算法的設計取決於數據（邏輯）結構，演算法的實現取決於所採用的存儲結構。數據的存儲結構本質上是其邏輯結構在計算機存儲器中的實現。為了全面反映一個數據的邏輯結構，它在內存中的影像包括兩個方面，即數據元素之間的信息和數據元素之間的關系。

不同的數據結構有相應的操作。數據的操作是在數據的邏輯結構上定義的操作演算法，如檢索、插入、刪除、更新和排序。

(1)演算法有正確性擴展閱讀

該演算法的一般性質包括：

1．通用性對於任何符合輸入類型的輸入數據，都可以根據演算法解決問題，並且包保證了計算結構的正確性。

2．演算法的每一條指令都必須能夠被人或機器執行。

3．確定性演算法應該在每一步之後都有明確的下一步指示。也就是說，確保每個步驟都有下一步行動的指示，不缺少或只包含含糊的下一步行動指示。

4．有限演算法的執行必須在有限步結束。

『貳』 演算法的正確性如何檢驗

演算法正確性證明包括兩個方面：1.證明關於輸入與喊大輸出之關系的命題是正確的；2.證明演算法中的公式及計算方法是正確的。

1、檢驗演算法是否正確可以將所編寫演算法寫成代碼帶入程序中進行運行測驗，隨機選擇多個數值分別鄭純豎進行測試，如果結果符合，則此演算法基本無誤。

2、請教前輩比如老師或褲畢者師兄師姐，請他們幫忙檢驗。

『叄』 演算法的正確性、健壯性、易讀性、時空性怎麼評價

評價演算法的四個標准：

1.正確性

能正確地實現預定的功能，滿足具體問題的需要。處理數據使用的演算法是否得當，能不能得到預想的結果。

2.易讀性

易於閱讀、理解和交流，便於調試、修改和擴充。寫出的演算法，能不能讓別人看明白，能不能讓別人明白演算法的邏輯？如果通俗易懂，在系統調試和修改或者功能擴充的時候，使系統維護更為便捷。

3.健壯性

輸入非法數據，演算法也能適當地做出反應後進行處理，不會產嫌或生預料不到的運行結果。數據的形式多種多樣，演算法可能面臨著接受各種各樣的數據，當演算法接收到不適合演算法處理的數據，演算法本身該如何處理呢？如果演算法能夠處理異常數據，處理能力越強，健壯性越好。

4.時空性

演算法的時空性是該演算法的時間性能和空間性能。主要是說演算法在執行過程中的時間長短和空間佔用多少問題。

演算法處理數據過程中，不同的演算法耗費的時間和內存空間是不同的。

(3)演算法有正確性擴展閱讀：

演算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。芹者伍此外，一個演算法還具有下列5個重要的特性。

（1）、有窮性

一個演算法必須總是（對任何合法的輸入值）在執行有窮步之後結束，且每一步都可在有窮時間內完成。

（2）、確定性嫌圓

演算法中每一條指令必須有明確的含義，讀者理解時不會產生二義性。即對於相同的輸入只能得到相同的輸出。

（3）、可行性

一個演算法是可行的，即演算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現的。

（4）、輸入

一個演算法有零個或多個的輸入，這些輸入取自於某個特定的對象的集合。

（5）、輸出

一個演算法有一個或多個的輸出，這些輸出是同輸入有著某種特定關系的量。

『肆』 計算機的演算法具有哪些特性

計算機的演算法具有可行性，有窮性、輸入輸出、確定性。

計算機演算法特點

1.有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他視為有效演算法。

2. 確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。

3. 有零個或多個輸入、所謂輸入是指在執行演算法是需要從外界取得必要的信息。

4. 有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。

5.有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。

拓展資料：

重要演算法

A*搜尋演算法

俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

Beam Search

束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。

二分取中查找演算法

一種在有序數組中查找某一特定元素的搜索演算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。

Branch and bound

分支定界(branch and bound)演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。

數據壓縮

數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。

Diffie–Hellman密鑰協商

Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。

Dijkstra』s 演算法

迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。

動態規劃

動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。

歐幾里得演算法

在數學中，輾轉相除法，又稱歐幾里得演算法，是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。

最大期望（EM）演算法

在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。

快速傅里葉變換(FFT)

快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。

哈希函數

HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。

堆排序

Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。

歸並排序

Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

RANSAC 演算法

RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。

RSA加密演演算法

這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。

並查集Union-find

並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。

Viterbi algorithm

尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。

參考資料：計算機演算法

『伍』 演算法的正確性證明方法一: 循環不變數

在之前的一篇文章里寫到 演算法的正確性 的概念以及它的作用，下面就來寫寫循環不變數在演算法的正確性證明中的用法。

在使用循環的演算法里，可以通過循環不變數證明其正確性。
所謂循環不變數是指一種在整個循環過程中保持不變的性質，它必須在以下3種情況下均保持不變，且該性質源困在循環終止後能證明演算法的正確性。

接下來就 歸並排序（Merge sort） 中的 merge 函數來說明一下循環不變數

先解釋一下這個函數的作用，sld 和 srd 為已排序數組，大小分別為 lc 和 rc，循環 tc (lc + rc) 次把它們的元素進行比較並復制到新分配的數組 md 中，那要怎麼證明這個演算法的正確性呢。

讓我們先設定循環不變數，然後看8-18行的循環能否在以上3種情況都滿足這個循環不變數。

結束時循環不變數給了我們一個有用信息，此遲氏時 md 已經把 sld 和 srd 中全部元素合並排序了， 從雹旦念而證明了演算法的正確性。

『陸』 在演算法實現中，演算法的正確性如何保證

演算法本身的正確性用邏輯推理來證明，和數學定理類似

實現演算法的程序的正確性則是兩碼事
簡單的程序也用邏輯推理來證明，稍復雜的可以用某些專門驗證程序正確性的程序來驗證，再復雜的就沒什麼好辦法了，事實上很多復雜的程序在比較極端的輸入下或多或少都會有點問題

『柒』 設計演算法的原則

設計演算法的原則：

1、正確性：演算法的正確性是指演算法至少應該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需要、能夠得到問題的正確答案。

2、可讀性：設計演算法的目的，一方面是為了讓計算機執行，但還有一個重要的目的就是為了便於他人的閱讀，讓人理解和交流，自己將來也可閱讀。如果可讀性不好，時間長了自己都不知道寫了什麼，可讀性是評判演算法（也包括實現它的程序代碼）好壞很重要的標志。

3、健壯性：當輸入的數據非法時，演算法應當恰當地做出反應或進行相應處理，而不是莫名其妙的輸出結果。並且處理出錯的方法不應是中斷程序的執行，而應是返回一個表示錯誤或錯誤性質的值，以便於在更高的抽象層次上進行處理。

4、高效率與低存儲量：通常，演算法的效率指的是演算法的執行時間；演算法的存儲量指的是演算法執行過程中所需要的最大存儲空間，兩者的復雜度都與問題的規模有關。演算法分析的任務是對設計的每一個具體的演算法，利用數學工具，討論其復雜度，探討具體演算法對問題的適應性。

(7)演算法有正確性擴展閱讀：

演算法的「正確」通常在用法上有很大的差別，大體分為以下4個層次：

1、演算法程序沒有語法錯誤；

2、演算法程序能夠根據正確的輸入的值得到滿足要求的輸出結果；

3、演算法程序能夠根據錯誤的輸出的值滿足規格說明的輸出結果；

4、演算法程序對於精心設計、極其刁難的測試數據都能滿足要求的輸出結果。

對於這4層含義，層次要求最低，因為僅僅沒有語法錯誤實在談不上是好的演算法。而層次（4）是最困難的，人們幾乎不可能逐一驗證所有的輸入都得到正確的結果。因此，演算法的正確性在大部分情況下都不可能用程序來證明，而是用數學方法證明的。

『捌』 一個好的演算法應該具備哪些特徵

一個好的演算法應該具畝悔備以下特徵：

• 正確性：演算法應該正確地解決問題，並且沒有明顯的錯誤。

• 易於理解：演算法應該清晰明了，容易理解，易於實現和調試。

• 可證明性：演算法應該有明確的證明，證明其正確性和最優性。

• 效率：演算法應該具有較高的效率，能夠在可接受的時間內完成計算。

• 穩定性：演算法的結果應該穩定，不會隨著數據的變化而變化。

• 適用性：演算法應該適用於不同的數據類型和規模

• 可源耐源擴展性：演算法應該具有可擴展性，能夠適應不斷增長的數據量。

雹態

『玖』 演算法及其特性有哪些

1.演算法的重要特性（1）有窮性：一個演算法必須在執行有窮步驟之後正常結束，而不能形成無窮循環。

（2）確定性：演算法中的每一條指令必須有確切的含義，不能產生多義性。

（2）可行性：演算法中的每一條指令必須是切實可執行的，即原則上可以通過已經實現的基本運算執行有限次來實現。

（4）輸入：一個演算法應該有零個或多個輸入。

（5）輸出：一個演算法應該有一個或多個輸出，這些輸出是同輸入有特定關系的量。

2.演算法描述的方法（1）框圖描述：該方法使用流程圖或N－S圖來描述演算法。

（2）自然語言描述：該方法採用自然語言，同時添加高級程序設計語言如while、for和if等基本控制語句來描述演算法。這類描述方法自然、簡潔，但缺乏嚴謹性和結構性。

（2）類語言描述：這是介於程序設計語言和自然語言之間演算法描述形式，其特徵是突出演算法設計的主體部分而有意忽略某些過於嚴格的語法細節，如類C或C＋＋的偽語言。這種演算法不能直接在計算機上運行，但專業設計人員經常使用它來描述演算法，它具有容易編寫、閱讀和格式統一的特點。

（4）程序設計語言描述：採用某種高級程序設計語言（如C或C＋＋）來描述。這是可以在計算機上運行並獲得結果的演算法描述。

本課程將採用偽C語言進行演算法描述。

2.演算法與程序的關系演算法的含義與程序十分相似，但二者是有區別的。演算法和程序都是用來表達解決問題的邏輯步驟；演算法是對解決問題方法的具體描述，程序是演算法在計算機中的具體實現；一個程序不一定滿足有窮性（死循環），而演算法一定滿足有窮性；程序中的指令必須是機器可執行的，而演算法中的指令則無此限制；一個演算法若用計算機語言來書寫，則它就可以是一個程序。因此，程序是演算法，但演算法不一定是程序。4.演算法設計要求在演算法設計中，對同一個問題可以設計出不同的求解演算法。如何評價這些演算法的優劣，從而為演算法設計和選擇提供可靠的依據？通常可從以下四個方面評價演算法的質量：

（1）正確性：演算法應該能夠正確地執行預先規定的功能，並達到所期望的性能要求。

（2）可讀性：演算法應該好讀，以有利於讀者對程序的理解，便於調試和修改。

（2）健壯性：演算法應具有容錯處理。當輸入非法數據時，演算法應對其作出反應，而不是產生莫名其妙的輸出結果。

（4）效率與低存儲量需求：效率指的是演算法執行的時間。對於同一個問題，如果有多種演算法可以求解，執行時間短的演算法效率高。演算法存儲量指的是演算法執行過程中所需要的最大存儲空間。高效率和低存儲量這兩者與問題的規模有關。