Какова пространственная сложность итерации ключей в NSMutableDictionary?

Question

Пытаясь определить время выполнения и пространства сложность HashTable (NSMutableDictionary) на основе решения следующих вопроса:

Implement a TwoSum interface that has 2 methods: Store and Test. Store adds an integer to an internal data store and Test checks if an integer passed to Test is the sum of any two integers in the internal data store.

Там, кажется, много ответов с различными хранения и тестирования сложности. Один многообещающий -

Имейте Hashtable под названием StoreDict. То есть NSMutableDictionary <NSNumber *, NSNumber *> *StoreDict как внутренняя структура данных

1. Store(N) реализован как

   • Проверьте, если StoreDict[@(N)] существует. Если да, то отсчет прироста, то есть: StoreDict[@(N)] = @([StoreDict[@(N)] intValue]++)

2. Test(N) реализован как

   • перебрать все ключи. Для каждого ключа, K,

     Если [K intValue] != N/2 проверить, если StoreDict[@(N-[K intValue])] существует

     Если [K intValue] == N/2 проверить, если [StoreDict[@(K)] intValue] >= 2

Похоже store является O (1) и Тест O(N) времени выполнения сложность. Вопрос только в том, что такое сложность пространства при повторении всех ключей, O(1) или O(N)? I.e - это ключи, заданные один за другим (o (1) пробел) или все N помещены в некоторый временной массив (o (N))?

EDIT

Я имею в виду, используя следующий код, чтобы получить ключи

NSEnumerator *enumerator = [StoreDict keyEnumerator]; 
id key; 

while ((key = [enumerator nextObject])) { 
    /* code that uses the returned key */ 
} 

Если O(N) пространство сложность, лучше решение, которое получает O(1) время и пространство сложности для этого вопрос?

или keyEnumerator похоже на использование [StoreDict allKeys], что является сложностью пространства O (N)?

Answer 1

NS(Mutable)Dictionary является мостом до CFDictionary, и разумно ли предположить, что методы первого реализованы с точки зрения функций на последнем. Вы можете проверить эту гипотезу, поставив точки останова на функции CFDictionary, а затем называя методы NS(Mutable)Dictionary.

Куда вы это получите? Ну, источник CFDictionary - available from Apple, и с этим вы должны быть в состоянии выяснить сложности, которые вы испытываете.

HTH