[파이썬/Python] 리스트(list)의 메소드 시간 복잡도(Big-O) 정리

파이썬으로 코딩테스트를 진행하며 가장 많이 쓰는 기본 자료형은 리스트(list)와 문자열(string), 딕셔너리(dictionary), 집합(set) 정도이다. 기본 자료형을 벗어난 것 중 많이 쓰는 것은 collections 모듈의 Counter와 deque 정도가 있겠고, 아주 가끔 itertools 모듈의 permutations 혹은 combinations 정도를 쓰는 것 같다(사실 이 둘은 시간복잡도가 터져버리기 때문에 거의 안 쓴다).

 

약간 난이도가 있는 코딩테스트 문제들은 항상 시간복잡도와 공간복잡도에 대한 제약이 주어진다. 특히 시간복잡도에 대한 제약은 아주 중요하며, 이를 고려하기 위해서는 이용하는 자료형의 메소드 별 시간 복잡도를 알고 있어야 한다. 그래서 이번 기회에 정리를 해볼까 한다. 우선 리스트와 딕셔너리, 집합에 관한 메소드들에 대해 각각의 글로 정리해보고, cheat sheet 느낌으로 정리된 것만 하나 더 포스팅할까 생각 중이다. 오늘은 리스트부터 정리해보자.

 

아래 표에서 사용하는 약자 혹은 용어에 대한 설명은 다음과 같다.

• l : list의 약자로, 리스트를 의미한다. l1과 l2가 등장한다면 서로 다른 리스트를 의미한다.
• i : index의 약자로, 리스트 내 특정 인덱스를 의미한다.
• a, b : 특정 인덱스를 의미하는 임의의 알파벳으로, 특정 인덱스부터 특정 인덱스까지의 범위를 지정할 때 사용했다.
• x : 하나의 요소(혹은 객체)다.
• item : x와 마찬가지이며, 리스트 안에 있는 요소들을 순회할 때 각 요소를 지칭하기 위해 쓴 용어이다.
• k : 임의의 양의 정수이다.
• 시간 복잡도에서의 N : number의 약자로, 리스트 내 원소 개수이다.

 

메소드 혹은 연산 이름 (Method or Operation)	사용 예시 (Example)	시간 복잡도 (Time Complexity) * Big-O Notation 기준	설명
Index	l[i]	O(1)
Store (or Assignment)	l[i] = x	O(1)	l[a:b] = [...] 의 시간 복잡도 : O(b-a) * Slice의 시간 복잡도와 동일하다.
Length	len(l)	O(1)
Append	l.append(x)	O(1)
Pop	l.pop()	O(1)
Clear	l.clear()	O(1)	l = [ ] 와 같다.
Slice	l[a:b]	O(b-a)
Extend	l1.extend(l2) (= l1+l2)	O(len(l2))
Construction (or Casting)	list(iterable object)	O(len(iterable object))
Check	l1 == l2 l1 != l2	O(N)	각 리스트의 모든 원소가 동일한 인덱스에  위치한지 linear하게 순회하며 확인함.
Insert	l(i, x)	O(N)	리스트의 i번째 인덱스에 x를 삽입하고, 기존 리스트의 [i:]를 모두 한 칸씩 뒤로 미뤄야 함.
Delete	del l[i]	O(N)	리스트의 i번째 인덱스에 위치한 원소를 삭제하고, 그 뒤의 원소를 모두 한 칸씩 앞으로 당겨야 함.
Containment	x in l x not in l	O(N)	x가 리스트 안에 있는지 (혹은 없는지) 확인하기 위해 리스트를 linear하게 순회하며 확인함.
Copy	l.copy() ( =  l[:])	O(N)	리스트 l에 있는 모든 원소를 카피하기 위해 리스트를 linear하게 순회함.
Remove	l.remove(x)	O(N)	리스트에 x가 존재하는지 0번째 인덱스부터  linear하게 순회하다가, 최초의 x가 발견되면 그것을 삭제하고 그 뒤의 요소들을 모두 한 칸씩 앞으로 당김. x가 없다고 하더라도 x를 찾기 위해 리스트의 끝까지 순회함.
Pop for specific element	l.pop([i])	O(N)	Delete와 동일한 원리이며, 그저 Store 기능이 추가된 것일 뿐임.
Extreme Value	min(l) max(l)	O(N)	리스트를 linear하게 순회하며 어떤 원소가 가장 작은지 (혹은 가장 큰지) 확인함.
Reverse	l.reverse() ( = l[::-1])	O(N)
Itertation	for item in l: ...	O(N)
Sort	l.sort() sorted(l)	O(N logN)	Tim Sort 원리에 따라 O(N logN).
Multiply	k*l	O(k N)

참고로 각 메소드에 대한 기능 설명은 아래의 링크를 참고하자. 본 글에서는 시간 복잡도에 대해 주안점을 두었기 때문에 각 메소드에 대한 기능 설명은 생략하도록 한다.

1. 점프 투 파이썬

2. 공식 문서 (1)

3. 공식 문서 (2)

 

 

 

Source : https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt