複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/algorithm/1581833
複製
複製成功

algorithm

（計算機術語）

鎖定
算法（algorithm），在數學（算學）和計算機科學之中，為任何良定義的具體計算步驟的一個序列，常用於計算、數據處理和自動推理。精確而言，算法是一個表示為有限長列表的有效方法。算法應包含清晰定義的指令用於計算函數。
算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和初始輸入（可能為空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在內的一些算法，包含了一些隨機輸入。
形式化算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效可計算性或者有效方法中成形。這些嘗試包括庫爾特·哥德爾、雅克·埃爾布朗和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年埃米爾·萊昂·珀斯特的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化算法的情況。
中文名
算法; 運算法則; 計算程序;
外文名
algorithm
編程語言
C++
類    別
C++標準庫
頭文件
#include
命名空間
using namespace std;

目錄

  1. 1 特徵
  2. 2 基本要素
  3. ▪ 常用設計模式
  4. ▪ 常用實現方法
  5. 3 形式化算法
  1. 4 複雜度
  2. ▪ 時間複雜度
  3. ▪ 空間複雜度
  4. 5 非確定性多項式時間（NP）
  1. 6 實現
  2. 7 示例
  3. ▪ 求最大值算法
  4. ▪ 求最大公約數算法
  5. 8 分類

algorithm特徵

以下是高德納在他的著作《計算機程序設計藝術》裏對算法的特徵歸納：
  1. 輸入：一個算法必須有零個或以上輸入量。
  2. 輸出：一個算法應有一個或以上輸出量，輸出量是算法計算的結果。
  3. 明確性：算法的描述必須無歧義，以保證算法的實際執行結果是精確地符合要求或期望，通常要求實際運行結果是確定的。
  4. 有限性：依據圖靈的定義，一個算法是能夠被任何圖靈完全系統模擬的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定算法必須在有限個步驟內完成任務。
  5. 有效性：又稱可行性。能夠實現，算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現。

algorithm基本要素

算法的核心是創建問題抽象的模型和明確求解目標，之後可以根據具體的問題選擇不同的模式和方法完成算法的設計。

algorithm常用設計模式

完全遍歷法和不完全遍歷法：在問題的解是有限離散解空間，且可以驗證正確性和最優性時，最簡單的算法就是把解空間的所有元素完全遍歷一遍，逐個檢測元素是否是我們要的解。這是最直接的算法，實現往往最簡單。但是當解空間特別龐大時，這種算法很可能導致工程上無法承受的計算量。這時候可以利用不完全遍歷方法——例如各種搜索法和規劃法——來減少計算量。
分治法：把一個問題分割成互相獨立的多個部分分別求解的思路。這種求解思路帶來的好處之一是便於進行並行計算。
動態規劃法：當問題的整體最優解就是由局部最優解組成的時候，經常採用的一種方法。
貪心算法：常見的近似求解思路。當問題的整體最優解不是（或無法證明是）由局部最優解組成，且對解的最優性沒有要求的時候，可以採用的一種方法。
線性規劃法：見條目。
簡併法：把一個問題通過邏輯或數學推理，簡化成與之等價或者近似的、相對簡單的模型，進而求解的方法。

algorithm常用實現方法

遞歸方法與迭代方法
順序計算、並行計算和分佈式計算：順序計算就是把形式化算法用編程語言進行單線程序列化後執行。
確定性算法和非確定性算法
精確求解和近似求解

algorithm形式化算法

算法是計算機處理信息的本質，因為計算機程序本質上是一個算法來告訴計算機確切的步驟來執行一個指定的任務，如計算職工的薪水或打印學生的成績單。一般地，當算法在處理信息時，會從輸入設備或數據的存儲地址讀取數據，把結果寫入輸出設備或某個存儲地址供以後再調用。

algorithm複雜度

algorithm時間複雜度

算法的時間複雜度是指算法需要消耗的時間資源。一般來説，計算機算法是問題規模n的函數f(n)，算法的時間複雜度也因此記做
算法執行時間的增長率與f(n)的增長率正相關，稱作漸近時間複雜度，簡稱時間複雜度。
常見的時間複雜度有：常數階O(1)，對數階，線性階 O(n)，線性對數階，平方階，立方階，...，k次方階,指數階。隨着問題規模n的不斷增大，上述時間複雜度不斷增大，算法的執行效率越低 [1]  。

algorithm空間複雜度

算法的空間複雜度是指算法需要消耗的空間資源。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示。同時間複雜度相比，空間複雜度的分析要簡單得多。

algorithm非確定性多項式時間（NP）

主條目：NP (複雜度)

algorithm實現

算法不單單可以用計算機程序來實現，也可以在人工神經網絡、電路或者機械設備上實現。

algorithm示例

algorithm求最大值算法

這是算法的一個簡單的例子。
我們有一串隨機數列。我們的目的是找到這個數列中最大的數。如果將數列中的每一個數字看成是一顆豆子的大小，可以將下面的算法形象地稱為“撿豆子”：
  1. 首先將第一顆豆子放入口袋中。
  2. 從第二顆豆子開始檢查，如果正在檢查的豆子比口袋中的還大，則將它撿起放入口袋中，同時丟掉原先口袋中的豆子。反之則繼續下一顆豆子。直到最後一顆豆子。
  3. 最後口袋中的豆子就是所有的豆子中最大的一顆。
以上算法在中國大陸的教科書中通常被叫做“打擂法”或者“循環打擂”：在一個for循環中，每輪循環都有新的挑戰者。若挑戰者勝的話，挑戰者做新擂主，否則擂主衞冕。for循環結束後輸出最後的擂主。
下面是一個形式算法，用ANSI C代碼表示
int max(int *array, int size){  int mval = *array;  int i;  for (i = 1; i < size; i++)    if (array[i] > mval)      mval = array[i];  return mval;}

algorithm求最大公約數算法

求兩個自然數的最大公約數設兩個變量{\displaystyle M}和{\displaystyle N}
  1. 如果{\displaystyle M<N}，則交換{\displaystyle M}和{\displaystyle N}
  2. {\displaystyle M}被{\displaystyle N}除，得到餘數{\displaystyle R}
  3. 判斷{\displaystyle R=0}，正確則{\displaystyle N}即為“最大公約數”，否則下一步
  4. 將{\displaystyle N}賦值給{\displaystyle M}，將{\displaystyle R}賦值給{\displaystyle N}，重做第一步。
用ANSI C代碼表示
//交換2數void swapi(int *x, int *y){  int tmp = *x;  *x = *y;  *y = tmp;}int gcd(int m, int n){  int r;  do  {    if (m < n)      swapi(&m, &n);    r = m % n;    m = n;    n = r;  } while (r);  return m;}
利用if函數以及遞歸則能做出更為精簡的代碼，更可省去交換的麻煩。（但是也因為遞歸調用，其空間複雜度提高）
int gcd(int a,int b){    if(a%b)        return gcd(b,a%b);    return b;}

algorithm分類

參考資料
  • 1.    劉波, 王凌, 金以慧. 差分進化算法研究進展[J]. 控制與決策, 2007, 22(7):721-729.