資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究遞迴關係練習集
遞迴關係是透過遞迴定義多維陣列的方程式。
接下來我們將基於遞迴關係解決一些問題。
Solve the recurrence reation:T(n) = 12T(n/2) + 9n2 + 2. T(n) = 12T(n/2) + 9n2 + 2. Here, a = 12 and b = 2 and f(n) = 9(n)2 + 2 It is of the form f(n) = O(n^c), where c = 2
它屬於主定理條件，
So, logb(a) = log2(12) = 3.58 Using case 1 of the masters theorm, T(n) = θ(n3.58).
Solve the recurrence reation:T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3. T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3
簡化後，在較大值 n，n/2 >> 23 時，忽略 23。
T(n) = 5T(n/2) + 5n2 + 7n - 5/3. Further, we can take 5n2 + 7n - 5 ≃0(n2). So, T(n) = 5T(n/2) + O(n2)
它屬於主定理的情況 2，
So, T(n) = O(n2).
檢查以下情況是否屬於主定理的任何情況。
T(n) = 2T(n/3) + 5n
否，主定理的應用要求函式是一個多項式函式。
T(n) = 2T(n/5) + tan(n)
否，三角函式不屬於主定理。
T(n) = 5T(n+1) + log(n)
否，對數函式不屬於主定理。
T(n) = T(n-7) + en
否，指數函式不屬於主定理。
T(n) = 9n(n/2+1 ) + 4(n2) - 17 Yes, as solved above.
更新於：2020-02-04
337 次瀏覽
廣告