演算法設計與分析

簡答

以比較為基礎的檢索演算法的時間下界是O(logn);Ω還是O?
以比較為基礎的分類演算法的時間下界是Ω(nlogn);
簡要說明理由：理由
演算法的五大特性：確定性，能行性，輸入，輸出，有窮性，
而計算程序只滿足前4條特性，不滿足有窮性
最優性原理：
無論程序的初始狀態或者初始決策是什么，其余的決策都必須相對于初始決策所產生的狀態構成一個最優決策序列，
最優性原理成立的例子：流水線調度問題，貨郎擔問題；
最優性原理不成立的例子：多段圖問題（以乘法作為路徑長度且出現負權邊時或包含負長度環的任意兩點間最短路徑問題；
貪心方法不一定能得到01背包問題的最優解，舉例
c^(x)<=c(x)
問題狀態：樹中每一個節點確定所求解問題的一個問題狀態；
狀態空間：由根節點到其他節點的所有路徑確定了這個問題的狀態空間；
解狀態：解狀態是這樣一些問題狀態S，對于這些問題狀態，由根到S的那條路徑確定了這解空間中的一個元組；
答案狀態：答案狀態是這樣一些解狀態S，對于這些解狀態，由根到S的那條路徑確定了這問題的一個解，
解空間的樹結構即為狀態空間樹；
4皇后問題的問題狀態一共有65個
分治法的三個基本步驟：
分：將n個輸入分成k個不同的可獨立求解的子問題；
治：求出這些問題的解；
合：通過適當的方法將每個問題的解合并成整個問題的解，
Q.回溯法和分支限界法的狀態空間生成方式有何不同？簡述兩種方法的基本思想
1. 回溯法：當前結點的E-結點R一旦生成一個新的兒子結點C,這個C結點就變成新的E-結點，生成下一個兒子結點
2. 分支-限界法：一個E-結點一直保持到變成死節點為止
3. 回溯法：加限界的深度優先生成方法稱為回溯法，回溯法在包含問題的所有解的解空間樹中，按深度優先的策略，從根節點出發搜索解空間樹，搜索至解空間樹的任一結點時，先判斷改結點是否肯定不包含問題的解，如果肯定不包含，就跳過以該結點為根的子樹，逐層向其祖先結點回溯，否則就進入該子樹，繼續按深度優先的策略進行搜索
4. 分支-限界法：生成當前E-結點的全部兒子后，再生成其他活結點的兒子；使用限界函式幫助避免生成不包含答案結點子樹的狀態空間，
P類問題：所有已經找到多項式演算法的問題的集合
NP類問題：所有可在多項式時間內由不確定演算法驗證的判定問題的集合
可滿足性問題：對于變數的任一一組真值指派確定公式是否為真
COOK定理：可滿足性在P內，當且僅當P=NP
NP難度：如果可滿足性約化為一個問題L，則稱此問題是NP難的
NP完全：如果L是NP難的而且L屬于NP，則稱問題L是NP完全的
最優二分檢索樹Knuth的優化方法:將k限制在區間R(i,j-1)~R(i+1,j)

證明題

證明以比較為基礎的分類演算法的最壞情況的時間下界為Ω(nlogn)
- 假設參加分類的n個關鍵字A(1),A(2),...,A(n),各不相同，因此任意兩個關鍵字A(i)和A(j)的比較必然導致A(i)<A(j) or A(i)>A(j)的結果，在比較樹中，一個進入左分支，另一個進入右分支，各外部結點表示演算法終止，由于n個關鍵字共有n!個排列，而每種排列可以是某種特定輸入下的分類結果，因此比較樹必有至少n!個外節點，
  由根到外節點的路徑長度即為生成該分類序列的比較長度，最壞情況的比較次數即為根到外節點的最長路徑，設T(n)是為這些演算法對應的比較樹的最小高度，設一棵二元樹的所有內節點的級數均<=k,
  n!<=2^T(n)
  當n>1時有 n!>=n(n-1)(n-2)...(n/2)>=(n/2)^n/2
  對于n>=4有 T(n)>=(n/2)log(n/2)>=(n/4)logn
  因此以比較為基礎的分類演算法的最壞情況的時間下界為Ω(nlogn)
證明FIND(n)>=[log(n+1)]
- 在比較樹中可知，FIND(n)不大于樹中根到一個葉子的最長路徑的距離，在這所有的樹中都必定有n個內節點與x在A中可能得n種出現情況相對應，
  如果一棵二元樹的所有內節點所在的級數小于或等于級數k，則最多有2^k-1個內節點，因此 n<=2^k-1，即FIND(n)=k>=[log(n+1)]
定理5.3:設J是k個作業的集合，σ=i₁i₂i₃...i_k是J中作業的一種排列，它使得d_i1<=d_i2<=d_i3<=...<=d_ik.J是一種可行解，當且僅當J中的作業可以按照σ的次序而又不違反任何一個期限的情況來處理，
- 筆記圖片

計算題

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/552137.html

標籤：其他

上一篇：一位27歲軟體測驗員，測驗在職近5年，月薪不到2W，擔心被應屆生取代

下一篇：返回列表