[科普中國(guó)]-有效算法

概述

對(duì)于那些不熟悉計(jì)算機(jī)的人來(lái)說(shuō)，可以使用別人已設(shè)計(jì)好的現(xiàn)成算法，只需根據(jù)算法的要求給予必要的輸入，就能得到輸出的結(jié)果。對(duì)他們來(lái)說(shuō)，算法如同一個(gè)“黑箱子”一樣，他們可以不了解“黑箱子”中的結(jié)構(gòu)，只是從外部特性上了解算法的作用，即可方便地使用算法。例如，對(duì)一個(gè)“輸入3個(gè)數(shù)，求其中最大值”的算法，只要輸入a,b,c這三個(gè)數(shù)，執(zhí)行算法后就能得到其中最大的數(shù)。但對(duì)于程序設(shè)計(jì)人員來(lái)說(shuō)，必須會(huì)設(shè)計(jì)算法，并且根據(jù)算法編寫(xiě)程序1。

正確認(rèn)識(shí)存在這樣一類(lèi)問(wèn)題，其目前最快算法所需計(jì)算次數(shù)是n的指數(shù)函數(shù)而非多項(xiàng)式，所以n略大時(shí)，計(jì)算機(jī)就不能勝任，故以其在計(jì)算上難于對(duì)付而聞名，被稱為NP-Complete問(wèn)題，如旅行售貨員問(wèn)題、時(shí)間表問(wèn)題等。數(shù)學(xué)家強(qiáng)烈的認(rèn)為：人們不可能找出一個(gè)有效算法這一事實(shí)是NP-Complete問(wèn)題的固有性質(zhì)。他們相信，不會(huì)有有效算法存在（如其一具有有效算法，余者皆然）。因此，對(duì)這類(lèi)問(wèn)題，尋找近似解的有效算法便自然成為人們追求的方向。

然而，對(duì)算法的認(rèn)識(shí)并未到此結(jié)束，人們很快發(fā)現(xiàn)上述復(fù)雜性概念涉及到算法在最壞的情況下的性態(tài)。而這種最壞情況在實(shí)際中發(fā)生的概率究竟有多大并未予以考慮，以致出現(xiàn)了多項(xiàng)式算法反倒不如非多項(xiàng)式算法在實(shí)算中的奇怪現(xiàn)象。例如，單純形算法已被證明是普遍實(shí)用和非常有效的，但人們也舉例證明了它不是多項(xiàng)式算法，哈奇楊算法已被證明是多項(xiàng)式算法，但在許多實(shí)踐中，其計(jì)算速度反比單純性算法慢得多。這說(shuō)明用算法在最壞的情況下的性態(tài)來(lái)區(qū)別好壞不是科學(xué)的，而算法的平均性態(tài)才是衡量算法好壞的最有說(shuō)服力、最重要的標(biāo)志。因此，那種近憑一、兩個(gè)并不具有代表性的例子來(lái)肯定或否定一種的算法的思想和行為是不可取的。

對(duì)于解決同一類(lèi)問(wèn)題的各種算法，優(yōu)劣立判的算法并不常見(jiàn)，往往是尺短寸長(zhǎng)，各有特點(diǎn)。方法一可能在解決A類(lèi)問(wèn)題上更有效，方法二可能在解決B子類(lèi)問(wèn)題上更優(yōu)越，應(yīng)當(dāng)實(shí)事求是的進(jìn)行具體分析，不宜簡(jiǎn)單肯定而否定另一種。那種認(rèn)為某類(lèi)問(wèn)題已有有效算法，從而對(duì)新提出的算法一概采取輕視，過(guò)于挑剔甚至懷疑的態(tài)度，這對(duì)算法的發(fā)展是有害的。對(duì)算法也應(yīng)采取”百花齊放，推陳出新“的方針，特別是對(duì)比較成熟的領(lǐng)域的算法，哪怕是稍微有所改進(jìn)，也可能產(chǎn)生較大的經(jīng)濟(jì)效益，因此更加不能忽視。

算法的發(fā)展是沒(méi)有窮盡的，人們對(duì)算法的認(rèn)識(shí)也在逐漸深入，期待著有更好的好算法出現(xiàn)，為社會(huì)服務(wù)，為人類(lèi)造福2。

其他特點(diǎn)出了有效性，算法還應(yīng)該具備一下特點(diǎn)：

1、有窮性。一個(gè)算法應(yīng)包含有限的操作步驟，而不是無(wú)限的。

2、確定性。算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)是含糊的、模棱兩可的。

3、有零個(gè)或多個(gè)輸入。所謂輸入指在執(zhí)行算法時(shí)需要從外界取得必要的信息。

4、有一個(gè)或多個(gè)輸出。算法的目的就是為了求解，”解“就是輸出。