我目前正在學習搜索演算法，我遇到了跳躍搜索，它的時間復雜度為O(√n)。為什么√n是跳轉搜索演算法中m（跳轉大小）的最佳值，它是如何影響時間復雜度的？
uj5u.com熱心網友回復：
設m為跳轉大小，n為元素數量。
在最壞的情況下，你要檢查的最大元素數是最大的跳轉數（n/m - 1）加上跳轉之間的元素數（m），你所花的時間大約與你檢查的總元素數成正比。
因此，選擇m的目標是最小化。(n/m) m-1。
通過m的導數是1-(n/m2)，最小值出現在導數為0的地方：
1 - (n/m2) = 0
（n/m2）=1
n = m2
m = √n
uj5u.com熱心網友回復：
假設區塊大小為k，最壞的情況下，尋找區塊大約需要n / k次迭代，尋找區塊中的元素需要k次迭代。
為了最小化 n / k k，其中 n 是一個常數，我們可以使用微分法（見 Matt 的答案）或 AM-GM 不等式來得到：
n / k k >= 2sqrt(n)
我們可以清楚地看到，2sqrt(n)是最小的迭代次數，并且當k=sqrt(n)時可以達到。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/308842.html
標籤：