問答題考慮在序列A[1..n]中找最大最小元素的問題。一個分治算法描述如下：如果n≤2就直接求解。否則，將序列等分成兩個子序列A[1..n/2]和A[n/2+1..n]，分別找出這兩子序列的最大最小元素x1，y1和x2，y2；然后據(jù)此求出A[1..n]的最大元素x=max{x1，x2}及最小元素y=min{y1，y2}。請給出該算法計算時間T（n）滿足的遞歸方程，并解方程來確定算法的時間復(fù)雜度。假定n=2k（k為正整數(shù)）。
您可能感興趣的試卷
你可能感興趣的試題
最新試題
0-1背包問題與部分背包問題的區(qū)別在于（）。
題型：多項選擇題
?優(yōu)先隊列式分支限界法解決0-1背包問題時，下面描述正確的是（）。
題型：多項選擇題
Prim算法適合稀疏圖，其時間復(fù)雜度只與邊的數(shù)目有關(guān)。
題型：判斷題
?有這樣一種算法，運行一次可能找不到問題的解，運行多次就一定能找到問題的解，且運行次數(shù)有界，這種算法是（）。
題型：單項選擇題
回溯法采用的搜索策略是（）。
題型：單項選擇題
已知某樓房共20層，如果采用二分查找，最多猜（）次就能猜出任意一個樓層。
題型：單項選擇題
序列（1，7，3，4，9，2，3）的最長遞增子序列的長度為（）。
題型：單項選擇題
關(guān)于使用回溯法求解0-1背包問題，以下說法正確的是（）。
題型：多項選擇題
關(guān)于分支限界法的基本思想，下列描述正確的是（）。
題型：多項選擇題
在求解部分背包問題時采用的貪心策略是（）。
題型：單項選擇題