c# - Python 与 C# 字典

Question

我已经使用 Python 编写代码一段时间了，我习惯于认为字典具有最坏情况下的 O(n) 时间复杂度 ( source )。但是，在工作中我必须使用 C#，我最近才发现 C# 中的字典具有更好的时间复杂度 ( source )。这是为什么？ Python 字典与 C# 字典相比有哪些优势？

顺便问一下，哪种实现更常见？如果我不得不使用另一种语言的标准库中的字典，它们最可能具有的时间复杂度是多少？

谢谢!

Answer 1

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

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

在实践中跳过理论:平均情况描述了您在执行操作时应该期望的一般情况。最坏的情况会告诉您，有时在某些特定条件下和/或对于某些特定数据，操作可能会执行得更慢。

此外，最好专注于一项特定操作。笼统地讨论“字典的复杂性”也没有多大意义。