[241211] TIL - 시간복잡도 정리

배열 (리스트) : 같은 타입(객체의 주소값)의 변수들로 이루어진 집합. 메모리의 연속공간에 값이 채워져 있는 형태

• 장점: 검색 성능이 좋다 O(1)
• 단점: 값의 삽입과 삭제에서 비효율적 O(n). 메모리 활용에 비효율적

연결리스트 (deque) : 값과 주소를 묶은 노드를 주소로 연결한 자료구조 (deque는 이중 연결리스트)

• 장점: 주소로 연결되어 있어 값을 삽입하거나 삭제하는 연산의 속도가 빠름 O(1)
• 단점: 원소로 바로 접근이 불가능함. Head부터 차례대로 접근 O(n)

리스트에서 pop(0)을 할 경우 O(n), insert(0, x)을 할 경우 O(n)

deque에서 popleft()을 할 경우 O(1), appendleft(x)을 할 경우 O(1)

 

deque의 roate(k) 는 시간복잡도 O(k)를 갖는다

 

리스트에서 in 연산자는 O(n)의 시간복잡도를 갖는다. in 연산이 선형 탐색을 통해 이루어지기 때문

→ 집합이나 딕셔너리를 사용하면 O(1)의 복잡도를 가진다

 

리스트의 index 함수는 처음으로 나타나는 값의 인덱스 반환 O(n) → 발견되지 않으면 ValueError 예외 발생. 순차적으로 요소를 순회하면 찾는 값과 일치하면 즉시 반환

---

n이 10만 이상이면 효율성을 따지는 것이고 O(n^2)으로는 안된다. 최소 n log n으로 접근하자.

---

 

enumerate는 리스트를 순회하면서 인덱스와 값을 반환한다. 호출시 O(1) (이터레이터 생성만 수행)

→ C언어로 구현된 최적화된 이터레이터 객체를 반환하여 range(n)으로 인덱스와 값을 가져오는 것보다 빠르다. 인덱스를 기반으로 리스트를 수정할 때나 특정 인덱스 조건에 따라 리스트를 조작해야 할 때 range(n)을 사용한다

 

len 함수는 O(1) → Python 객체는 길이를 저장하는 내부 속성을 가지고 있음. 객체의 __len__ 메서드를 호출하거나 내부에 저장된 길이 속성 값 반환 (C언어로 구현됨)

 

min, max 함수는 입력 데이터를 한번씩 순회한다 O(n) → C로 구현되어 있어서 빠르다 (내장 함수들은 대부분 그런듯)

sorted 함수는 정렬 결과를 새 리스트로 반환하며 모든 이터러블을 정렬할 수 있다. key 매개변수로 정렬 순서를 커스터마이징할 수 있다

리스트의 sort 메서드는 제자리에서(in-place) 정렬하며, 새 리스트를 반환하지 않는다. 마찬가지로 key와 reverse 매개변수를 지원한다

둘 다 동일한 정렬 알고리즘인 Timsort(병합정렬 + 삽입정렬)를 사용한다. 시간복잡도는 O(n log n) 이다. (정렬된 데이터에서는 O(n))

key 매개변수는 각 요소마다 한 번씩만 호출되고, 각 요소의 key 값을 미리 계산 한 뒤 정렬은 미리 계산된 key 값을 사용하여 비교 작업을 수행. 따라서 key 함수 호출은 정렬 과정과 독립적으로 추가 작업을 수행하므로 전체 시간 복잡도에 선형적으로만 영향을 줌

 

reversed 함수는 데이터를 복사하지 않고 이터레이터를 반환하므로 추가 메모리 사용 없이 효율적으로 동작.

그냥 호출(이터레이터 생성)하는건 O(1)이고 전체 순회는 O(n)

 

list, tuple, set 함수는 모든 요소를 순회하므로 O(n)의 시간복잡도를 가짐

---

해시테이블(dict, defaultdict, Counter) : 해시함수를 사용해 키를 해시값으로 매핑하고, 이 해시값을 index로 해서 데이터 값을 키와 함께 저장. 저장되는 곳을 버킷 또는 슬롯이라 함

탐색, 삽입, 삭제의 시간복잡도는 평균적으로 O(1) → 해시충돌이 빈번하게 일어나면 최악의 경우 O(n)가 될 수 있다

Open addressing 방식을 사용하며 구체적으로 이중 해싱(double hashing) 기법을 활용

 

Direct-address table : 키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블 (충돌X)

전체 키 중 실제 사용되는 키가 적을 경우 메모리 효율성 ↓

 

Counter - Counter 하면 키가 일치하는 애들끼리 값을 뺀다