티스토리 뷰

파이썬을 이용해서 알고리즘 문제를 풀다보면 언어 자체에서 지원하는 내장 메소드들을 사용하는 경우가 대부분이다. 이 때, 각 메소드들의 시간 복잡도를 정확하게 알고 사용해야 제대로된 알고리즘을 작성할 수 있다. 따라서 파이썬의 기본 타입들이 제공하는 메소드들과 그것들의 시간 복잡도를 정리하는 시간이 필요하다고 생각했다.

우선 변수 할당(바인딩, Binding)의 시간 복잡도는 O(1)이다. 즉, 'a = 1'이라는 할당문은 O(1)라는 시간복잡도를 갖는다. 여기에 산술연산, 값에 대한 비교 연산들 역시 모두 O(1)의 시간복잡도를 갖는다.

list 타입의 메소드와 Big-O

리스트 타입의 내장 메소드들의 리스트와 그것들의 시간 복잡도에 대해서 알아보겠다. 소문자 L은 리스트 객체를 나타냈고 대문자 N은 리스트의 사이즈를 의미한다.

연산

설명

예제

복잡도

비고

Index

n번째 element 접근

l[i]

O(1)

 

Store

n번째에 element 할당

l[i] = 10

O(1)

 

Length

List의 길이 가져옴

len(l)

O(1)

 

Append

List의 뒤쪽에 element 추가

l.append(1)

O(1)

 

Pop

List의 뒤쪽 element 제거

l.pop()

O(1)

l.pop(-1)과 동일한 동작

Clear

List를 비움

l.clear()

O(1)

l = list(), l = [] 과 동일

Slice

List의 일부를 취함

l[a:b]

O(b-a)

복사되는 element의 개수에 비례

Extend

리스트뒤에 리스트를 붙임

l.extend(other_list)

O(len(other_list)

추가되는 list의 size에 비례

Construction

list 객체 생성

list()

O(len(...))

초기화 되는 리스트 Element 개수에 비례

Equality
Check

두 리스트가 같은지 확인

l1 == l2

O(N)

N : list의 size

Insert

특정 위치에 element를 끼워 넣음

l.insert(2, 10)

O(N)

중간에 끼워 넣어야 해서 한칸씩 뒤로 밀려나서 그러는듯?

Delete

특정 위치의 element를 제거함

del l[10]

O(N)

마찬가지로 중간에 제거되고 그 뒤에 있는 Element를 땡겨줘야해서 그러는듯?

Containment

특정 Element가 list 내에 있는지 확인

x in l, x not in l

O(N)

Searching Overhead

Copy

list를 복사

l.copy()

O(N)

l[:]와 동일한 결과

Remove

list에서 Element를 제거

l.remove(10)

O(N)

10이라는 값을 제거

Pop

List의 i번째 element를 제거

l.pop(1)

O(N)

O(N - i).

Extreme 
Value

min/max 값 찾기

min(l), max(l)

O(N)

전체를 한번씩 탐색 필요

Reverse

리스트를 역순으로 변경

l.reverse()

O(N)

 

Iteration

리스트의 element들을 한번씩 순회

for item in l :

O(N)

 

Sort

정렬 수행

l.sort()

O(N * log N)

 

Multiply

리스트의 element들을 k번 반복해서 리스트를 생성

k * l

O(k * l)

3 * [0] -> [0,0,0]

각 연산들이 파이썬 내부에서 어떻게 동작하는지 잘 생각해보면, 각 시간 복잡도를 쉽게 유추할 수 있다.

Set 타입의 메소드와 Big-O

집합(set) 타입의 메소드들과 그들의 시간 복잡도를 정리해보자. 리스트와 비슷하게 소문자 S와 소문자 T는 집합을 나타내고, N은 집합에 있는 엘리먼트의 개수를 의미한다.

연산

설명

예제

복잡도

비고

Length

집합 element들의 개수

len(s)

O(1)

 

Add

집합에 element 추가

s.add(10)

O(1)

 

Containment

집합에 특정 Element가 있는지 확인

10 in s, 10 not in s

O(1)

List/Tuple은 O(N)임과 비교

Remove

집합에서 특정 Element를 제거

s.remove(10)

O(1)

List/tuple의 경우 O(N)

Discard

집합에서 특정  Element를 제거

s.discard(10)

O(1)

 

Pop

집합에서 임의의 element하나를 제거

s.pop()

O(1)

 

Clear

집합을 공집합(empty)으로 만들어버림

s.clear()

O(1)

s = set() 과 동일

Construction

집합을 생성

set(...)

O(len(...))

새로 생성되는 집합 요소(Element)의 개수에 비례

Equality
Check

동일한 집합인지 연산

s == t, s != t

O(len(s))

모든 element가 동일하면 동일한 집합

Subset
Check

Subset인지 여부를 확인

s <= t, s >= t

O(len(s))
O(len(t))

Subset 쪽의 모든 element가 superset에 존재하는지 확인

Union

합집합

s | t

O(len(s) + len(t))

 

Intersection

교집합

s & t

O(len(s) + len(t))

 

Difference

차집합

s - t

O(len(s) + len(t))

 

Symmetric
Diff

두 집합의 상대 여집합의 합

s ^ t

O(len(s) + len(t))

 

Iteration

집합의 모든 element들을 순회

for v in s:

O(N)

 

Copy

집합을 복사

s.copy()

O(N)

 

집합 연산은 리스트에 비해 순서를 보장하지 않아도 되기 때문에 O(1)에 끝나는 연산들이 더 있다. 따라서 순서를 보장하지 않아도 되는 경우 리스트 대신 집합 타입을 사용해서 시간 복잡도를 줄일 수 있다.

dict 타입의 메소드와 Big-O

마지막으로 dict 타입의 메소드들과 그것들의 시간 복잡도를 정리해보겠다. 소문자 D는 dict 타입을 의미하며, 소문자 K는 키 값을 의미한다.

연산

설명

예제

복잡도

비고

Index

특정 Element에 접근

d[k]

O(1)

 

Store

특정 Element에값을 설정

d[k] = v

O(1)

 

Length

Dict에 들어있는 Element 개수

len(d)

O(1)

 

Delete

특정 Element를 지움

del d[k]

O(1)

 

Pop

특정 Element를 지움

d.pop(k)

O(1)

 

Pop item

무작위로 Element 하나를 지움

d.popitem()

O(1)

 

Clear

Dict를 초기화

d.clear()

O(1)

d = {}와 동일함

View

Dict의 Key들을 List형태로 가져옴

d.keys()

O(1)

d.values()도 동일

Construction

Dictionary를 생성

dict(...)

O(len(...))

새로 생성되는 Dict의 element 개수에 비례

Iteration

Dict 내의 element들을 순회

for k in d:

O(N)

 

각 타입마다 메소드들의 시간 복잡도가 약간씩 다르다. 각 타입별로 메소드들의 시간복잡도를 이해하고 적절한 자료구조를 사용하여 불필요하게 낭비되는 시간 복잡도를 줄여 더 효율적인 알고리즘을 작성할 수 있도록 하자.

Reference

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

댓글
댓글쓰기 폼
공지사항
Total
33,434
Today
89
Yesterday
258
링크
«   2020/10   »
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함