NSMutableDictionary에서 키를 반복하는 공간의 복잡성은 무엇입니까? 질문 다음 해시 테이블 (NSMutableDictionary) 기반 솔루션의 실행 시간과 공간의 복잡성을 결정하기 위해 노력

Question

:

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.

는 다양한 저장 및 테스트 복잡성 많은 답변을 것 같다. 유망한 것이 하나 있습니다

StoreDict라는 Hashtable이 있습니다. 나는. StoreDict[@(N)]가 있으면 NSMutableDictionary <NSNumber *, NSNumber *> *StoreDict 내부 데이터 구조로

1. Store(N)는

   • 검사로서 구현된다. 예, 증가 수, 즉이 경우 StoreDict[@(N)] = @([StoreDict[@(N)] intValue]++)

2. Test(N) 모든 키를 통해

   • 반복 처리로 구현. 각 키, K, 들어

     StoreDict[@(N-[K intValue])]이

     하면 [K intValue] == N/2 체크하면 [StoreDict[@(K)] intValue] >= 2

있는 경우 [K intValue] != N/2 검사가 store처럼 보이는 경우

는 O (1) 및 테스트 O(N) 실행 시간 복잡성. 유일한 문제는 모든 키를 반복하는 공간의 복잡성은 무엇입니까? O(1) 또는 O(N)입니까? 즉, 하나씩 (o (1) 공간) 주어진 키 또는 모든 임시 배열 (o (N) 공간)에있는 N입니까? 나는 그것이 O(N) 공간의 복잡성,이를 위해 O(1) 시간과 공간 복잡도를 얻을 수있는 더 나은 솔루션의 경우 키

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

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

를 얻기 위해 다음 코드를 사용하여 참조하고

편집

문제?

이거나 [StoreDict allKeys]과 유사한 keyEnumerator인데, 이는 O (N) 공간 복잡도입니까?

Answer 1

NS(Mutable)Dictionary은 CFDictionary에 가설되며, 전자의 방법은 후자에 대한 기능의 측면에서 구현된다고 가정하는 것이 합리적입니다. CFDictionary 함수에 중단 점을 배치하고 NS(Mutable)Dictionary 메서드를 호출하여이 가설을 테스트 할 수 있습니다.

어디서 얻을 수 있습니까? 음, CFDictionary의 출처는 available from Apple이며 그로 인해 당신은 당신이 가진 복잡성을 파악할 수 있습니다.

HTH