Python与C#词典

Question

我已经在Python中编写了一段时间,我已经习惯于认为字典具有最坏的O(n)时间复杂度(源代码).但是,在工作中我必须使用C#,而我最近才发现C#中的字典具有更好的时间复杂度(源代码).这是为什么？python词典比C#词汇有什么优势？

顺便问一下,哪种实施更常见？如果我不得不使用其他语言的标准库中的词典,他们最有可能具有什么时间复杂度？

谢谢!

Answer 1

MSDN文档讲述了平均时间复杂度(更具体地说,他们说复杂性"接近"给定的函数),这些与Python文档中提供的相同.Python还提供最坏情况的复杂性.对于某些操作,MSDN还提供最坏情况估计(例如:http://msdn.microsoft.com/en-us/library/k7z0zy8k%28v=vs.110%29.aspx).

将平均情况与最坏情况进行比较是没有意义的.

在实践中跳过理论:平均情况描述了在执行操作时您应该期望的一般情况.最糟糕的情况通知您,有时,在某些特定条件和/或某些特定数据中,操作可能执行得较慢.

此外,最好关注一个特定的操作.一般来说,讨论"字典的复杂性"也没有多大意义.