這是O（N）表示中需要一個常數的情況嗎？

在這個link中，作者說get(index)在Java ArrayList中爲O（1），而在LinkedList中爲O（n/2），因爲它需要遍歷該條目。 ArrayList中的get操作需要一段時間，因爲ArrayList可以訪問所有索引。但是，我不明白O（n/2）的LinkedList。我被教導的方式是，當你使用大哦符號時，你應該寫下它，而不用常數，以便更容易地向其他人解釋;即O（n）而不是O（2n）。是不是O（n）也是最壞情況下運行時間的界限？這樣，使用O（n）對我來說更有意義，因爲您正在搜索的元素可能處於最後。有誰知道作者爲什麼包含n/2？這是O（N）表示中需要一個常數的情況嗎？

來源

2014-09-18 committedandroider

是的，O（n/2）與O（n）完全一樣。不要相信你在互聯網上閱讀的所有內容。 ;） – 2014-09-18 18:57:15

雖然這篇文章寫得很好。我想他知道，因爲他在另一部分使用了O（n）。只是好奇他爲什麼包括n/2而不是n。他一定有這樣做的理由 – committedandroider 2014-09-18 19:00:10

作爲一個評論：當你想說關於n/2元素，但不想大驚小怪的條款，這是非常頻繁地濫用符號和寫的東西，如n/2 + O（1）個元素，甚至n/2 + o（n）。 – 2014-09-18 19:12:56

你說得對，O（n/2）與O（n）完全一樣。博客文章作者可能試圖傳達一些關於如何平均穿過n/2元素以獲得任何特定（隨機選擇）索引的方法。但這是對大O符號的濫用。

公平地給筆者，他或她似乎非常清楚，爲O（n）= O（N/2）：

爲了從一個特定的索引中刪除元素... ArrayList執行復制操作，這使得它接近爲O（n），同時LinkedList需要遍歷到該點，這也使得它爲O（n/2）

通過使用「也」，海報似乎是承認這一點。

來源

2014-09-18 19:01:15

謝謝，這是有道理的 – committedandroider 2014-09-18 19:05:06

這是O（N）表示中需要一個常數的情況嗎？

回答

相關問題