我想知道通过NSSet进行迭代的big-O表示法是什么。
NSArray的答案显然是O(n)-但是NSSet的答案是什么？
另外-我假设相同的答案将适用于NSDictionary吗？
最佳答案
通过查看其桥接的Core Foundation等效项的标题中的注释，您可以对Apple数据结构的计算复杂性有所了解(因为它们实质上是在后台使用相同的代码)。
有趣的是，实际上不能保证CFArray的时间复杂度为O(n):
这些时间上的复杂性表明CFArray(以及NSArray)实际上可以实现为树(测试表明它甚至可能在多个基础数据结构之间切换)。
类似地，对于CFDictionary，给定的范围范围很广:
我没有在CFSet的Core Foundation header 中找到类似的注释，但是对源代码的检查显示，它基于 CFBasicHash (这是一个哈希表)，因此时间复杂度与哈希表的典型时间相同-O (1)通常是插入，删除和测试，最坏的情况是O(n)。
如果您真的想确切了解这些数据结构的工作方式，那么Core Foundation是开源的，因此您可以阅读Apple's website上的源代码。
关于ios - 通过NSSet和NSDictionary进行迭代的big-O表示法是什么，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26194100/