計(jì)算機(jī)算法

計(jì)算機(jī)算法

計(jì)算機(jī)算法，簡稱“算法”，代表用計(jì)算機(jī)解一類問題的精確、有效的方法。算法+數(shù)據(jù)結(jié)構(gòu)=程序，求解一個(gè)給定的可計(jì)算或可解的問題，不同的人可以編寫出不同的程序，來解決同一個(gè)問題。

算法是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運(yùn)算，是對(duì)解題方案的準(zhǔn)確與完整的描述。制定一個(gè)算法，一般要經(jīng)過設(shè)計(jì)、確認(rèn)、分析、編碼、測試、調(diào)試、計(jì)時(shí)等階段。

目錄

• 1 算法的特性
• 2 算法的描述
• 3 算法的評(píng)價(jià)
• 4 相關(guān)條目
• 5 參考來源

算法的特性

算法的特性包括：

1. 確定性。算法的每一種運(yùn)算必須有確定的意義，該種運(yùn)算應(yīng)執(zhí)行何種動(dòng)作應(yīng)無二義性，目的明確；
2. 能行性。要求算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的，每種運(yùn)算至少在原理上能由人用紙和筆在有限的時(shí)間內(nèi)完成；
3. 輸入。一個(gè)算法有0個(gè)或多個(gè)輸入，在算法運(yùn)算開始之前給出算法所需數(shù)據(jù)的初值，這些輸入取自特定的對(duì)象集合；
4. 輸出。作為算法運(yùn)算的結(jié)果，一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，輸出是同輸入有某種特定關(guān)系的量；
5. 有窮性。一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算后終止，即該算法是可達(dá)的。

滿足前四個(gè)特性的一組規(guī)則不能稱為算法，只能稱為計(jì)算過程，操作系統(tǒng)是計(jì)算過程的一個(gè)例子，操作系統(tǒng)用來管理計(jì)算機(jī)資源，控制作業(yè)的運(yùn)行，沒有作業(yè)運(yùn)行時(shí)，計(jì)算過程并不停止，而是處于等待狀態(tài)。

算法的描述

算法的描述方法可以歸納為以下幾種：

1. 自然語言；
2. 圖形，如N-S圖、流程圖，圖的描述與算法語言的描述對(duì)應(yīng)；
3. 算法語言，即計(jì)算機(jī)語言、程序設(shè)計(jì)語言、偽代碼；
4. 形式語言，用數(shù)學(xué)的方法，可以避免自然語言的二義性。

用各種算法描述方法所描述的同一算法，該算法的功用是一樣的，允許在算法的描述和實(shí)現(xiàn)方法上有所不同。

算法的評(píng)價(jià)

一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。

• 算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。一般來說，計(jì)算機(jī)算法是問題規(guī)模n 的函數(shù)f(n)，算法執(zhí)行的時(shí)間的增長率與f(n) 的增長率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度（Asymptotic Time Complexity）。時(shí)間復(fù)雜度用“O（數(shù)量級(jí)）”來表示，稱為“階”。常見的時(shí)間復(fù)雜度有： O（1）常數(shù)階；O（log2n）對(duì)數(shù)階；O（n）線性階；O（n2）平方階。

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

相關(guān)條目

• 計(jì)算機(jī)

參考來源

• 參考來源1
• 參考來源2