我想知道通过 NSSet 进行迭代的大 O 表示法是什么。 NSArray 的答案显然是 O(n) - 但 NSSet 的答案是什么？ 另外 - 我假设相同的答案适用于 NSDictionary？
最佳答案
您可以通过查看其桥接的 Core Foundation 等效项的 header 中的注释来了解 Apple 数据结构的计算复杂性(因为它们实际上在幕后使用相同的代码)。
有趣的是，CFArray 的时间复杂度不实际上保证为 O(n):
Computational Complexity
The access time for a value in the array is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time). Linear search operations similarly have a worst case complexity of O(N*lg N), though typically the bounds will be tighter, and so on. Insertion or deletion operations will typically be linear in the number of values in the array, but may be O(N*lg N) clearly in the worst case in some implementations. There are no favored positions within the array for performance; that is, it is not necessarily faster to access values with low indices, or to insert or delete values with high indices, or whatever.
这些时间复杂性表明 CFArray(因此 NSArray)实际上可能被实现为一棵树(测试表明它甚至可能在多个底层数据结构之间切换) .
与 CFDictionary 类似，给定的边界范围很广:
Computational Complexity
The access time for a value in the dictionary is guaranteed to be at worst O(N) for any implementation, current and future, but will often be O(1) (constant time). Insertion or deletion operations will typically be constant time as well, but are O(N*N) in the worst case in some implementations. Access of values through a key is faster than accessing values directly (if there are any such operations). Dictionaries will tend to use significantly more memory than a array with the same number of values.
我无法在 CFSet 的 Core Foundation header 中找到类似的注释，但检查源代码表明它基于 CFBasicHash ，这是一个哈希表，因此时间复杂度对于哈希表来说是典型的——通常是 O(1) 插入、删除和测试，最坏情况下是 O(n)。
如果您真的有兴趣了解这些数据结构的确切工作原理，Core Foundation 是开源的，因此您可以在 Apple's website 上阅读源代码。 .
关于ios - 通过 NSSet 和 NSDictionary 进行迭代的大 O 表示法是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26194100/