Dictionary的OrderBy方法的大O是多少？

Question

我正在使用OrderBy方法对10,000个元素的Dictionary进行排序,如下所示,并想知道它的大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

Answer 1

在常规字典中添加已排序的集合是没有意义的,因为字典不保证保留订单.这只是阻止您在问题中显示的代码:它可能在某些情况下有效,但相信我这是不正确的.有必要指出这样一个事实:通过将有序集合添加回字典只会消除您之前所做的排序.您可以按某种顺序枚举KeyValuePairs并添加常规列表,这将保留插入顺序,或者更好地使用其他一些数据结构.在排序字典中查看示例.当然,这种类型的数据结构在插入阶段需要更多时间,而排序通常很快,因为它们是"自然"排序的.根据文档,排序的字典插入时间是"最好的" O(log(n)),我建议你研究几乎有序的输入集的性能,因为有时基于树的数据结构将由于不平衡的树形成而遭受这种情况.如果是这种情况(我不知道如何在内部实现)并且性能变得至关重要,另一个有趣的数据结构是B树.