我在某處讀到它在未排序的陣列中洗掉元素更快，但我不確定這是否正確。根據我的理解，如果我們想洗掉某個特定元素，那么在排序陣列的情況下，搜索它并最終洗掉它需要 O(log N) 時間，但在未排序陣列的情況下，它可能需要最壞的情況在我們最終洗掉它之前線性搜索它的時間為 O(N)。那么這怎么可能呢？
uj5u.com熱心網友回復：
在排序陣列中洗掉元素比在未排序陣列中更快。
這是因為您可以對已排序陣列進行二分搜索以找到指定的元素。
未排序的陣列必須一一檢查每個元素（線性搜索）以找到要洗掉的元素。
兩者的洗掉操作本身的時間復雜度相同。
為O（log N）花費更少的比O（N）執行時間。
uj5u.com熱心網友回復：
O(n)如果您從陣列中物理洗掉該元素，則從陣列中洗掉元素是一項操作。那是因為必須移動被洗掉元素右側的所有元素。O(1)如果元素位于陣列的末尾，這只是一個操作，所以我們可以彈出它。
現在，在一個未排序的陣列中，您可以將找到的元素與陣列末尾的元素交換，O(1)并從末尾彈出一個元素，也是在恒定時間內。
但是在排序陣列中，如果要保持排序，則不能這樣做。您必須物理洗掉元素以保持陣列排序。
因此，為了清楚起見，您需要明確說明從已排序陣列中洗掉元素并保持排序是O(n). 如果你不關心它被排序，你可以在O(1). 搜索是對數的，所以這變成了對數。但是你只能這樣做一次。因為之后陣列不再排序，并且您無法在 log n 時間內搜索您的元素。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391642.html