演算法的問題規模

⑴ 什麼是演算法

一、什麼是演算法
演算法是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。演算法常常含有重復的步驟和一些比較或邏輯判斷。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。時間復雜度用「O（數量級）」來表示，稱為「階」。常見的時間復雜度有： O（1）常數階；O（log2n）對數階；O（n）線性階；O（n2）平方階。
演算法的空間復雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。
[font class="Apple-style-span" style="font-weight: bold;" id="bks_etfhxykd"]演算法 Algorithm [/font]
演算法是在有限步驟內求解某一問題所使用的一組定義明確的規則。通俗點說，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種演算法。前者是推理實現的演算法，後者是操作實現的演算法。
一個演算法應該具有以下五個重要的特徵：
1、有窮性： 一個演算法必須保證執行有限步之後結束；
2、確切性： 演算法的每一步驟必須有確切的定義；
3、輸入：一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定除了初始條件；
4、輸出：一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的；
5、可行性： 演算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算後即可完成。
演算法的設計要求
1）正確性（Correctness）
有4個層次：
A．程序不含語法錯誤；
B．程序對幾組輸入數據能夠得出滿足規格要求的結果；
C．程序對精心選擇的、典型的、苛刻的、帶有刁難性的幾組輸入數據能夠得出滿足規格要求的結果；
D．程序對一切合法的輸入數據都能產生滿足規格要求的結果。
2）可讀性（Readability）
演算法的第一目的是為了閱讀和交流；
可讀性有助於對演算法的理解；
可讀性有助於對演算法的調試和修改。
3）高效率與低存儲量
處理速度快；存儲容量小
時間和空間是矛盾的、實際問題的求解往往是求得時間和空間的統一、折中。
演算法的描述 演算法的描述方式（常用的）
演算法描述 自然語言
流程圖 特定的表示演算法的圖形符號
偽語言 包括程序設計語言的三大基本結構及自然語言的一種語言
類語言 類似高級語言的語言，例如，類PASCAL、類C語言。
演算法的評價 演算法評價的標准：時間復雜度和空間復雜度。
1）時間復雜度 指在計算機上運行該演算法所花費的時間。用「O（數量級）」來表示，稱為「階」。
常見的時間復雜度有： O（1）常數階；O（logn）對數階；O（n）線性階；O（n＾2）平方階
2）空間復雜度 指演算法在計算機上運行所佔用的存儲空間。度量同時間復雜度。
時間復雜度舉例
（a） X：=X+1 ； O（1）
（b） FOR I：=1 TO n DO
X：= X+1； O（n）
（c） FOR I：= 1 TO n DO
FOR J：= 1 TO n DO
X：= X+1； O（n＾2）
「演算法」一詞最早來自公元 9世紀 波斯數學家比阿勒·霍瓦里松的一本影響深遠的著作《代數對話錄》。20世紀的 英國 數學家 圖靈 提出了著名的圖靈論點，並抽象出了一台機器，這台機器被我們稱之為 圖靈機 。圖靈的思想對演算法的發展起到了重要的作用。
演算法是 計算機 處理信息的本質，因為 計算機程序 本質上是一個演算法，告訴計算機確切的步驟來執行一個指定的任務，如計算職工的薪水或列印學生的成績單。 一般地，當演算法在處理信息時，數據會從輸入設備讀取，寫入輸出設備，可能保存起來以供以後使用。
這是演算法的一個簡單的例子。
我們有一串隨機數列。我們的目的是找到這個數列中最大的數。如果將數列中的每一個數字看成是一顆豆子的大小 可以將下面的演算法形象地稱為「撿豆子」：
首先將第一顆豆子（數列中的第一個數字）放入口袋中。
從第二顆豆子開始檢查，直到最後一顆豆子。如果正在檢查的豆子比口袋中的還大，則將它撿起放入口袋中，同時丟掉原先的豆子。 最後口袋中的豆子就是所有的豆子中最大的一顆。
下面是一個形式演算法，用近似於 編程語言 的 偽代碼 表示
給定：一個數列「list"，以及數列的長度"length(list)" largest = list[1] for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest
符號說明:
= 用於表示賦值。即：右邊的值被賦予給左邊的變數。
List[counter] 用於表示數列中的第 counter 項。例如：如果 counter 的值是5，那麼 List[counter] 表示數列中的第5項。
<= 用於表示「小於或等於」。

⑵ 編程演算法是什麼

程序演算法是對特定問題求解過程的描述，是指令的有限序列，每條指令完成一個或多個操作。通俗地講，就是為解決某一特定問題而採取的具體有限的操作步驟。

在有限的操作步驟內完成。有窮性是演算法的重要特性，任何一個問題的解決不論其採取什麼樣的演算法，其終歸是要把問題解決好。如果一種演算法的執行時間是無限的，或在期望的時間內沒有完成，那麼這種演算法就是無用和徒勞的，我們不能稱其為演算法。

相關信息：

演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法的時間復雜度也因此記做T(n)=Ο(f(n))；因此，問題的規模n 越大，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。

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

⑶ 演算法的時間復雜度僅與問題的規模有關

演算法的時間復雜度在大部分題庫中的答案是選擇與問題規模有關的那個選項，同時干擾項往往是計算機硬體性能，編譯程序質量，程序設計語言等等。（直接回答）
其他版本的書中還提到與-待處理數據的初態有關，例如是否已經有序。（補充回答）
演算法的時間復雜度，即效率，通常只與演算法本身的性質有關，演算法本身的性質又包括其涉及的問題規模，還有選擇的何種演算法策略。（個人經驗）
演算法的時間復雜度，即基本操作重復執行的次數，是問題規模n的某個函數f(n)，演算法的時間量度記作T(n) = O(f(n));它表示隨著問題規模n的增大，演算法執行的時間的增長率和f(n)的增長率相同，稱作漸近時間復雜度，也稱時間復雜度。（嚴蔚敏老師書上的相關解釋）

⑷ 演算法里的輸入規模是什麼

不知道你說的是哪種演算法，給你個例子吧。

運算量 n！ 2^n n^3 n^2 nlogn n
最大規模 11 26 464 10000 4.5*10^6 1000000000
速度擴大兩倍 11 27 587 14142 8.6*10^6 2000000000
這個表給出了機器速度擴大兩倍後，演算法所能解決的規模的對比。可以看出，n！和2n不僅能解決的問題規模十分小,而且增長緩慢；最快的nlogn和n演算法不僅解決問題
的規模大，而且增長快。我們把漸進時間復雜為多項式的演算法稱為多項式時間演算法(polymonial-time algorithm)，也稱有效演算法；而n!或者2^n這樣低效演算法稱為指數時間演算法（exponential-time algorithm）.
盡管如此，考慮到目前主流機器的執行速度，多數演算法競賽所選取的數據規模基本符合此表。例如，一些指明n<=8的題目，可能n！的演算法已經足夠，n<=20的題目需要2^n的演算法,而n<=300的題目可能就需要用至少n^3的多項式演算法.

⑸ 數據結構中評價演算法的兩個重要指標是什麼

數據結構中評價演算法的兩個重要指標是時間復雜度和空間復雜度。

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。

1、時間復雜度：

演算法的時間復雜度是指執行演算法所需要的計算工作量。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法的時間復雜度也因此記做。

2、空間復雜度：

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

(5)演算法的問題規模擴展閱讀：

評估演算法效率的方法：

1、事後統計方法

這種方法主要是通過設計好的測試程序和數據，利用計算機計時器對不同演算法編制的程序的運行時間進行比較，從而確定演算法效率的高低。

2、事前分析估算方法

在計算機程序編寫前，依據統計方法對演算法進行估算。經過總結，可以發現一個高級語言編寫的程序在計算機上運行時所消耗的時間取決於下列因素：演算法採用的策略、編譯產生的代碼質量、問題的輸入規模、機器執行指令的速度。

參考資料來源：網路-演算法

⑹ c語言中什麼是演算法有哪些描述演算法的例子

1、有窮性（有限性）。任何一種提出的解題方法都是在有限的操作步驟內可以完成的。
如果在有限的操作步驟內完不成，得不到結果，這樣的演算法將無限的執行下去，永遠不會停止。除非手動停止。例如操作系統就不具有有窮性，它可以一直運行。
2、一個演算法應該具有以下七個重要的特徵：
1）有窮性（finiteness）
演算法的有窮性是指演算法必須能在執行有限個步驟之後終止
2）確切性(definiteness)
演算法的每一步驟必須有確切的定義；
3）輸入項(input)
一個演算法有0個或多個輸入,以刻畫運算對象的初始情況,所謂0個輸入是指演算法本身定出了初始條件；
4）輸出項(output)
一個演算法有一個或多個輸出,以反映對輸入數據加工後的結果.沒有輸出的演算法是毫無意義的；
5）可行性(effectiveness)
演算法中執行的任何計算步都是可以被分解為基本的可執行的操作步,即每個計算步都可以在有限時間內完成；
6）
高效性（high
efficiency）
執行速度快,佔用資源少；
7）
健壯性（robustness）
健壯性又稱魯棒性，是指軟體對於規范要求以外的輸入情況的處理能力。所謂健壯的系統是指對於規范要求以外的輸入能夠判斷出這個輸入不符合規范要求，並能有合理的處理方式。