獲取運行時間T（n）

算法核心如下所示。獲取運行時間T（n）

CHECK_VALUE_IN_ARRAY(array, n, value) 
for i = 1 to n 
    binary_search(array, i, n, value)

而且已經知道binary_search（陣列，1，N，值）的T（N）=西塔（LGN）如何讓T（n）的？

PS：我的步驟：

T(n) = t(n) + t(n-1) + ... + t(1) 
     = lg(n) + lg(n-1) + ... + lg(1) 
     = lgn!

這是正確的？

2014-02-12 xren

CHECK_VALUE_IN_ARRAY（array，n，value）for i = 1 to n binary_search（array，i，n，value） – xren

你卡在什麼部分？你有沒有嘗試總結二進制搜索的運行時間爲我的每個值？ –

'binary_search'做什麼？它的運行時依賴於「我」嗎？ – user2357112

如果binary_search(array, i, n, value)使用二分搜索搜索value的陣列元素i ... n，那麼是的，你的分析是正確的。運行時會

Θ（日誌1 +登錄2 +原木3 + ... + log n）的= Θ（日誌N！）

注意通過Stirling's approximation，登錄N！ = Θ（n log n），因此總運行時間爲Θ（n log n）。

希望這會有所幫助！

2014-02-12 01:49:43 templatetypedef

回答