[파이썬 101] List, Set, Dictionary 연산과 메서드의 시간복잡도

 

List 연산/메서드 의 시간복잡도

연산 / 메서드	예시		복잡도	비고
Index	list[i]		O(1)
Store	list[i] = value		O(1)
Length	len(list)		O(1)
Append	list.append(value)		O(1)
Pop	list.pop()		O(1)	list.pop(-1)
Clear	list.clear()		O(1)	list = list(), list= []
Slice	list[a:b]		O(b-a)	slicing 되는 개수에 비례 : O(N)
Extend	list.extend(other_list)		O(len(...))	other_list의 크기에 비례 : O(N)
Construction	list()		O(len(...))	초기화되는 크기에 비례 : O(N)
Equality	list == other_list		O(N)
Insert	list.insert(i, value)		O(N)
Delete	del list[i]		O(N)
Containment	x in list		O(N)	x not in list
Copy	list.copy()		O(N)	list[:]
Remove	list.remove(value)		O(N)
Pop	list.pop(i)		O(N)	O(N - i)
Extreme val	min(list), max(list)		O(N)
Reverse	list(reverse)		O(N)
Iteration	for item in list		O(N)
Sort	list.sort()		O(NlogN)
Multiply	list * k		O(k * N)	O(N)

 

 

 

Set 메서드의 시간복잡도

연산 / 메서드	예시		복잡도	비고
Length	len(set)		O(1)
Add	set.add(value)		O(1)
Containment	value in set		O(1)	value not in set. worst case O(N)
Remove	set.remove(value)		O(1)
Discard	set.discard(value)		O(1)
Pop	set.pop()		O(1)
Clear	set.clear()		O(1)
Construction	set()		O(len(...))	초기화되는 크기에 비례 : O(N)
Equality	set == other_set		O(N)	set != other_set
Subset	set <= other_set		O(N)	set >= other_set
Union	set | other_set		O(N+N')	set 와 other_set의 N만큼 : O(N)
Intersection	set & other_set		O(min(N,N'))	set 와 other_set의 N만큼 : O(N). worst case O(N * N')
Deifference	set - other_set		O(N)	set 와 other_set의 N만큼 : O(N)
Sym Diff	set ^ other_set		O(N)	set 와 other_set의 N만큼 : O(N). worst case O(N * N')
Iteration	for item in set		O(N)
Copy	set.copy()		O(N)

 

 

 

Dictionary 메서드의 시간복잡도

연산 / 메서드	예시		복잡도	비고
Index	dict[i]		O(1)
Store	dict[i] = value		O(1)
Containment	value in dict		O(1)
Length	len(dict)		O(1)
Delete	del dict[i]		O(1)
Pop	dict.pop(i)		O(1)
Pop item	dict.popitem()		O(1)
Clear	dict.clear()		O(1)	dict = {}
View	dict.keys()		O(1)	dict.values()
Construction	dict(...)		O(len(...))	O(N)
Iteration	for item in dict		O(N)

 

 

 

 

 

 

 

참조
 - https://wiki.python.org/moin/TimeComplexity
 - https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt