算法分析與設計論文-背包問題的算法設計策略對比與分析(已修改)
2025-06-20 10:51 本頁面
【正文】 算法設計與分析論文 題 目 01 背包問題的算法設計策略對比與分析 專 業(yè) 班 級 學 號 姓 名 引言 對于計算機科學來說， 算法（ Algorithm） 的概念是至關重要的。算法 是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優(yōu)劣可以用空間復雜度與 時間復雜度 來衡量。 算法可以理解為有基本運算及規(guī)定的運算順序所構(gòu)成的完整的解題 步驟?；蛘呖闯砂凑找笤O計好的有限的確切的計算序列，并且這樣的步驟和序列可以解決一類問題。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。 一個算法應該具有以下五個重要的特征： 有窮性 ： 一個算法必須保證執(zhí)行有限步之后結(jié)束； 確切性 ： 算法的每一步驟必須有確切的定義； 輸入 ： 一個算法有 0 個或多個輸入，以刻畫運算對象的初始情況，所謂 0 個輸入是指算法本身定除了初始條件； 輸出 ： 一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的； 可行性 ： 算法原則上能夠精確地運行，而 且人們用筆和紙做有限次運算后即可完成。 計算機科學 家尼克勞斯 沃思曾著過一本著名的書《數(shù)據(jù)結(jié)構(gòu)十算法 = 程序》，可見算法在計算機科學界與計算機應用界的地位。 1 算法復雜性分析的方法介紹 算法的復雜性是算法效率的度量，是評價算法優(yōu)劣的重要依據(jù)。一個算法的復雜性的高低體現(xiàn)在運行該算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該算法的復雜性越高；反之，所需 的資源越低，則該算法的復雜性越低。 計算機的資源，最重要的是時間和空間（即存儲器）資源。因而，算法的復雜性有時間復雜性和空間復雜性之分。 不言而喻，對于任意給定的問題，設計出復雜性盡可能地的算法是我們在設計算法是追求的一個重要目標；另一方面，當給定的問題已有多種算法時，選擇其中復雜性最低者，是我們在選用算法適應遵循的一個重要準則。因此，算法的復雜性分析對算法的設計或選用有著重要的指導意義和實用價值。 關于算法的復雜性，有兩個問題要弄清楚 ： 用怎樣的一個量來表達一個算法的復雜性；對于給定的一個算法，怎樣具 體計算它的復雜性。 讓我們從比較兩對具體算法的效率開始。 比較兩對算法的效率 考慮問題 1：已知不重復且已經(jīng)按從小到大排好的 m 個整數(shù)的數(shù)組 A[1..m]（為簡單起見。還設 m=2 k， k 是一個確定的非負整數(shù)）。對于給定的整數(shù) c，要求尋找一個下標 i，使得 A[i]=c；若找不到，則返回一個 0。 問題 1 的一個簡單的算法是：從頭到尾掃描數(shù)組 A。照此，或者掃到 A 的第 i 個分量，經(jīng)檢測滿足 A[i]=c；或者掃到 A 的最后一個分量，經(jīng)檢測仍不滿足A[i]=c。我們用一個函數(shù) Search 來表達這個算法： Function Search (c:integer):integer。 Var J:integer。 Begin J:=1。 {初始化 } {在還沒有到達 A 的最后一個分量且等于 c 的分量還沒有找到時， 查找下一個分量并且進行檢測 } While (A[i]c)and(jm) do j:=j+1。 If A[j]=c then search:=j {在數(shù)組 A 中找到等于 c 的分量，且此分量的下標為 j} else Search:=0。 {在數(shù)組中找不到等于 c 的分量 } End。 容易看出，在最壞的情況下，這個 算法要檢測 A 的所有 m 個分量才能判斷在 A 中找不到等于 c 的分量。 解決問題 1 的另一個算法利用到已知條件中 A 已排好序的性質(zhì)。它首先拿 A的中間分量 A[m/2]與 c 比較，如果 A[m/2]=c 則解已找到。如果 A[m/2]c，則 c只可能在 A[1],A[2],..,A[m/21]之中，因而下一步只要在 A[1], A[2], .. ， A[m/21]中繼續(xù)查找；如果 A[m/2]c，則 c 只可能在 A[m/2+1],A[m/2+2],..,A[m]之中，因而下一步只要在 A[m/2+1],A[m/2+2],..,A[m]中繼續(xù) 查找。不管哪一種情形，都把下一步需要繼續(xù)查找的范圍縮小了一半。再拿這一半的子數(shù)組的中間分量與 c比較，重復上述步驟。照此重復下去，總有
畢業(yè)設計相關推薦
鄂ICP備17016276號-1