问Objective数据结构的近似运行时比较

EN

想象一下你有一堆NSArrays。数组都包含包装在CGPoints中的NSValues。并非所有的元素都是独一无二的。所以某些元素可以出现在多个数组中。如何最快地将这些数组组合成一个数组，这样得到的数组只包含唯一的元素？

现在我是这样做的

1. 使用NSSet将每个数组插入setByAddingObjectsFromArray
2. 用集合的内容填充结果数组

另一种选择是：

1. 遍历每个数组一次，并将每个值插入到一个NSDictionary中(如果它还没有在其中)
2. 遍历字典的键一次，并将每个键插入结果数组

传统的运行时分析指出，第一个选项应该使用O(n log n)，其中n是所有初始数组中的元素数(遍历所有元素，并将每个元素插入二进制搜索树或日志时间中类似的元素)。对于第二种方法，运行时是O(n)，因为查找和插入哈希表是在摊销常数时间内运行的。然而，在阅读了一些关于苹果的数据结构之后，认为它们的行为像传统的数据结构似乎是愚蠢的。