使用二進制搜索的循環雙向鏈表的複雜性是什麼？

它是O（n log n）還是O（log n）？使用二進制搜索的循環雙向鏈表的複雜性是什麼？

2010-08-18 Saif

@Frustrated - 你爲什麼用'homework'標記這個？賽義夫說[這裏]（http://stackoverflow.com/questions/2326831/a-list-of-java-errors-and-warnings/2326876#2326876），他正在開發Java到阿拉伯語的翻譯，不完全是學生級任務。 – 2010-08-18 15:59:00

@reemrevnivek：我把它標記爲'家庭作業'，因爲它看起來非常像一個家庭作業問題：沒有問題的背景，沒有解釋*爲什麼*他想使用循環雙向鏈表進行二進制搜索，它*看起來*像我收到並看到別人收到的家庭作業問題。 @Saif：對不起，如果它不是作業，但它有它的外觀。 – FrustratedWithFormsDesigner 2010-08-18 17:03:14

@Frustrated：多數民衆贊成。其實我很好奇，沒有想到它，我已經被教過（不是一個家庭作業，雖然：P），它是低效率的，但我想爲什麼會這樣，如果我使用緩存指針，我不好意思通過雖然。 – Saif 2010-08-18 17:43:53

我想說它不是O（log n），因爲二進制搜索在鏈接列表上不能很好地工作 - 您沒有高效的隨機訪問。

如果你真的試圖做二分搜索，它會花費O（log n）步，但在每一步中，你需要一個O（n）遍歷來訪問所需的元素。所以你可以說它是O（nlog（n））。

你應該做一個O（n）線性搜索來代替。

來源

2010-08-18 15:53:17 muddybruin

您沒有*任何*隨機存取;所有訪問都是線性的。但是，是的，我同意你的回答。 – 2010-08-18 15:54:11

二進制搜索需要隨機訪問，因此它不可能在鏈接列表中。你堅持使用O（n）線性搜索。

來源

2010-08-18 15:52:28

使用二進制搜索的循環雙向鏈表的複雜性是什麼？

回答

相關問題