objective-c - 我如何理解 Cocoa 库类中的性能权衡？

Question

今天有人问我，如果该字典包含 1,000,000 个元素，那么 NSMutableDictionary 插入需要多长时间。我没有计算机科学背景，所以完全不知道。我很惊讶地发现它在(我现在理解为)O(n) 时间内完成。伟大的。太棒了。

有人怎么可能确切地知道这一点？

显然，人们可以针对每个 Cocoa 类编写数十个测试并绘制出所有时间数据。当我有几周的空闲时间时，我一定会抽出时间来解决这个问题。排除所有这些......

• 这对于计算机科学专业的人来说是不是太明显了？背景？
• Apple 是否发布了解释文档这个？
• 他的知识是否意味着他是一台计算机科学专家，他自己测试发现了这一点吗？

Answer 1

您所询问的内容称为 "complexity" of an algorithm 。它与语言无关； NSDictionary 时间复杂度与任何其他关联字典(例如 C++ std::map)没有什么不同。但是，这并不意味着填充某些对象的 NSDictionary 保证能够执行 insert、search 或 删除操作的速度与std::map一样快；这意味着执行这些操作所花费的时间是线性 (O(n))，在最坏的情况下，与元素的数量相关( em>n O(n)) 的一部分。字典插入可能 O(1)，这是常数时间(操作花费相同的时间，与字典中的元素数量无关)如果没有哈希碰撞。

NSDictionary 使用的“算法”称为 Hash Table 。哈希表通过对键输入进行哈希处理(恒定时间操作)来进行插入，然后解决冲突，这是一个 O(n) 操作。希望您能够看到，在最坏的情况下，所有您的插入操作都会发生冲突，即 O(n)。

表/哈希算法当然可以专门用于减少特定数据集中的冲突，但 NSDictionary 仅使用键的对象 hash 方法 对象，如果您需要某种特化(可能不需要)，您可以为您的 NSObject 子类覆盖这些对象。

由于它是一个通用字典，并不专门针对特定的数据集，因此我们不一定需要了解 NSDictionary 的实现细节(Apple 的 documentation for NSDictionary 没有提及具体细节)知道这些操作将是 O(n)。我们也不必运行“测试”来发现复杂性。