時間復(fù)雜度分析-資料下載頁
2025-08-07 11:21本頁面
【正文】 在這個遞推關(guān)系式中，算法每次遞歸調(diào)用 3個規(guī)模為 1/2的子問題，那么總的規(guī)模 3/2，大小，所以，粗略估算要在 O(nlogn)、 O(n2)之間。 ???????11)()2/(3)1()(nnnOnTOnT相關(guān)習(xí)題 1. 求下列函數(shù)的漸進(jìn)表達(dá)式： 3n2+10n n2/10+2n 21+1/n logn3 10log3n =O(n2) =O(2n) =O(1) =O(logn) =O(n) O(1)和 O(2)區(qū)別： 定義 1 如果存在兩個正常數(shù) c和 n0，對于所有的 n≥n0，有 |f(n)| ≤ c|g(n)| 則記作 f(n) = Ο(g(n)) O(1) = O(2) 相差的只是常數(shù)因子 （ 1） 假設(shè)某算法在輸入規(guī)模為 n時的計算時間為 T(n)=3*2n。在某臺計算機(jī)上實(shí)現(xiàn)并完成該算法的時間為 t?，F(xiàn)在有另一臺計算機(jī)，其運(yùn)行速度為第一臺的 64倍，那么在這臺新機(jī)器上用同一算法在 t秒內(nèi)能解輸入規(guī)模為多大的問題？ 設(shè)新機(jī)器用統(tǒng)一算法能解輸入規(guī)模為 n1的問題，則： t=3*2n1/64=3*2n16 所以， n1=n+6 (2) 若上述的算法改為 T(n)=n2，其他條件不變，則在新機(jī)器上用 t秒時間能解輸入規(guī)模為多大的問題？ n12=64n2=(8n)2 能解規(guī)模為 8n的問題 (3) 若上述的算法改為 T(n)=8，其他條件不變，則在新機(jī)器上用 t秒時間能解輸入規(guī)模為多大的問題？ 由于 T(n)是常數(shù)，所以可以解任意規(guī)模的問題。 4. 對于下列各組函數(shù) f(n) g(n)，確定 f(n)=O(g(n)，或 f（ n)=?(g(n)，或 f(n)=?(g(n)) (1) f(n) = logn2 g(n)=logn +5 (2) f(n)=logn2 g(n) = (3) f(n)=n g(n)=log2n (4) f(n)= nlogn g(n)=log(n) (5) f(n)=10 g(n)=log10 (6) f(n)=log2n g(n)=logn (7) f(n)=2n g(n)=100n2 (8) f(n)=2n g(n)=3n n 假設(shè)我們有 n個直徑各不相同的螺釘，以及 n個相應(yīng)的螺母。我們一次只能比較一對螺釘和螺母，來判斷螺母是大于螺釘、小于螺釘還是正好合適螺釘。然而，我們不能拿兩個螺母作比較，也不能拿兩個螺釘作比較。我們的問題是要找到每一對匹配的螺釘和螺母，為該問題設(shè)計算法，他的平均效率符合 ?(nlogn) n個不同的整數(shù)排好序后存于 t[0:n1]中。若存在一個下標(biāo) i， 0=i=n1，使得 t[i]=i，設(shè)計一個算法找到這個下標(biāo)，最壞的情況下計算時間 O(logn)。 某石油公司計劃建造一條由東向西的主輸油管道。該管道要穿過一個有 n口油井的油田。從每口油井都要有一條輸油管道沿最短路徑 (或南或北 )與主管道相連。如果給定 n口油井的位置，即它們的 x坐標(biāo)和 y坐標(biāo)，應(yīng)如何確定主管道的最優(yōu)位置，即使各油井到主管道之間的輸油管道長度總和最小的位置？
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1