HashTable, Array, ArrayList, LinkedList 등의 공간의 복잡성은 무엇입니까

Question

인기있는 언어로 된 기본 데이터 구조의 공간 복잡성을 알고 싶습니다.

Answer 1

사실상 모든 데이터 구조는 n의 ORDER에 있습니다.

• 배열 = 정확히 N
• 의 ArrayList = betweenn 및 케이 * 않음 (기본 K = 2)
• LinkedList의 = 정확히 N
• 해시 = 최악의 N/K (기본 K가 0.75이다)은

Answer 2

이들 모두는 공간 복잡성 O (n)을 갖는다. 모든 변경 사항은 계수이며 구현에 완전히 의존합니다. 특히 시간 복잡성을 줄이기 위해 공간을 사전 할당하는 것과 같은 일을 시작하기 시작할 때.

예를 들어, 배열 목록 구조는 일반적으로 여분의 공간을 미리 할당합니다. 따라서 여러 객체에 대한 정확한 복잡성은 실제로 구현에 완전히 의존하는 범위와 생성 및 사용 방법에 달려 있습니다. 예를 들어, 더 많은 공간이 필요할 때마다 항상 3 개의 여분의 공간을 할당하는 배열 목록을 작성하고 5 개 이상의 열린 공간이있을 때 항상 3 개의 열린 공간으로 할당을 해제하면 n의 실제 복잡도는 [n, n + 5] + overhead이됩니다.

프로그래밍 할 때 이러한 항목을 선택하는 데있어 큰 차이점은 일반적으로 사용하기 쉽고 사용법에 얼마나 잘 맞는지입니다. 예를 들어, 링크 된 목록은 무작위 액세스에 대해서는 끔찍하지만 반복에는 좋습니다. 자바에 대한

Answer 3

: (Aproximates)

 
      Memory O(x) | General Case 
Array  |  n  | n 
ArrayList |  n  | 2 * n 
LinkedList|  n  | n * (node size) 
HashTable |  n  | ~n 
Map  |  n  | (n * key_size) + n