我在考試中遇到了這個問題，
我有一臺非常慢的計算機，它需要一秒鐘在具有 1,000（一千）個元素的陣列上進行二進制搜索。我應該期望計算機在具有 1,000,000（一百萬）個元素的陣列上進行二分搜索需要多長時間？
我很難理解這一點，搜索 100 萬個元素比搜索 1000 個元素需要更長的時間還是取決于計算機？
uj5u.com熱心網友回復：
它確實取決于計算機，也取決于陣列的大小。由于在這個問題中使用的是同一臺計算機，我們可以抽象計算機的影響并關注樣本量。
二分搜索具有對數時間復雜度。如果您采用 log(1_000) 和 log(1_000_000) 之間的差異，您會發現在 100 萬個元素陣列中搜索的時間幾乎是兩倍。
這是假設最壞的情況。對于一般情況，計算會變得更復雜，您可以查看此維基百科頁面以進行更深入的分析。
uj5u.com熱心網友回復：
首先，二分查找需要對串列或陣列進行排序。并且由于您將每個串列/子串列一分為二，因此需要log2(N)搜索才能找到正確的專案log2記錄到base 2.
所以對于1_000_000物品，它應該只需要20 comparisons回到物品上。所以它應該非常快（沒有時間對串列進行排序）。
1000專案將需要大約10 comparisons。一秒鐘，imo，在任何現代處理器上進行如此簡單的搜索都需要很長時間。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/355670.html