什麼是字典的OrderBy方法的大O？

我正在使用OrderBy方法對10,000個元素的字典進行排序，如下所示，並且想知道它的大O.有人知道嗎？在訂購它們之後，我將它們按照該順序添加到新的Dictionary中。這樣做可能有更好的方法，但它適用於我的目的。什麼是字典的OrderBy方法的大O？

這是我的例子：

 m_sortedItems = new Dictionary<int,string>(); 
     foreach(KeyValuePair<int,string> item in collection.OrderBy(key => key.Value)){ 
      m_sortedItems.Add(item.Key, item.Value); 
     }

我查MSDN上，但它沒有列出： http://msdn.microsoft.com/en-us/library/bb534966.aspx

來源

2012-10-12 I plus plus

字典沒有OrderBy;可枚舉。由於字典沒有定義的順序，所以沒有什麼特別的要報告。 –

根據http://stackoverflow.com/questions/2799427/what-guarantees-are-there-on-the-run-time-complexity-big-o-of-linq-methods，Linq的OrderBy使用快速排序O（N日誌N）。 –

詞典沒有定義的順序，所以按特定順序添加項目並不是你應該做的事情。 O（NlogN）將成爲您將遇到的大多數排序算法的基準。

來源

2012-10-12 18:15:39 NominSim

謝謝，這是我正在尋找的答案 –

添加分類收集普通的字典裏是沒有意義的，因爲字典不保證以保持順序。這只是阻止你在問題中顯示的代碼：它可能在某些情況下起作用，但相信我這是不正確的。有必要指出這樣一個事實，即通過將有序集合添加回字典將只是您以前完成的排序變爲。您可以按某種順序枚舉KeyValuePairs並添加到常規列表中，這將保留插入順序，或者更好地使用其他數據結構。看看sorted dictionary的例子。當然這樣的數據結構在插入階段需要更多的時間，而排序通常很快，因爲它們是「自然」排序的。根據文檔，排序後的字典插入時間「最好」爲O（log（n）），我建議您調查一下幾乎有序的輸入集的性能，因爲有時基於樹的數據結構會因爲不平衡而遭受這種情況樹形成。如果是這種情況（我不知道內部是如何實現的）並且性能變得至關重要，另一個相互影響的數據結構就是B-Tree。

來源

2012-10-12 18:15:38

「一些其他數據結構」可能作爲'SortedDictionary'有意義。 – Servy

我做錯了。我使用的數據已經按順序硬編碼了，密鑰沒有混淆，所以數據似乎是按順序排列的。我現在把它們放在一個列表中，並在列表中排列它們。 –

什麼是字典的OrderBy方法的大O？

回答

相關問題