파이썬 시간 복잡도 (Big-O) 정리

백전능 JeonNeung Baek·2024년 9월 6일

복잡도 비교

$O(1) < O\big(log(n)\big) < O(n) < O\big(nlog(n)\big) < O(n^2) < O(2^n)$

리스트

	기능	예시	복잡도	설명
1	Index	arr[i]	$O(1)$	인덱스로 값 찾기
2	Store	arr[i] = 0	$O(1)$	인덱스로 데이터 저장
3	Length	len(arr)	$O(1)$	리스트 길이
4	Append	arr.append(x)	$O(1)$	리스트 뒤에 데이터 저장
5	Pop	arr.pop()	$O(1)$	리스트 가장 뒤의 데이터 pop
6	Clear	arr.clear()	$O(1)$	리스트를 비워 []으로 만듦
7	Slice	arr[a:b]	$O(b-a)$	슬라이싱 되는 요소의 수 만큼 비례
8	Extend	arr.extend(...)	$O(len(...))$	확장되는 길이에 비례
9	Construction	list(...)	$O(len(...))$	리스트 길이에 비례
10	check ==, !=	arr1==arr2	$O(n)$	리스트가 동일한지 확인
11	Insert	arr[a:b]=...	$O(n)$	데이터 삽입
12	Delete	del arr[i]	$O(n)$	인덱스 활용 데이터 제거
13	Containment	x in arr	$O(n)$	포함여부 확인
14	Copy	arr.copy()	$O(n)$	복제
15	Remove	arr.remove(...)	$O(n)$	값 활용 데이터 제거, 한 번에 하나만
16	Pop	arr.pop(i)	$O(n)$	제거된 값 이후를 전부 한칸씩 당겨줘야함
17	Extreme Value	max(arr),min(arr)	$O(n)$	전체 데이터 확인 필요
18	Reverse	arr.reverse()	$O(n)$	리스트 순서 뒤집기
19	Iteration	for x in arr:	$O(n)$	전체 데이터 확인
20	Sort	arr.sort()	$O(n*log(n))$	파이썬 기본 정렬 알고리즘
21	Multiply	k*arr	$O(k*n)$	리스트 곱

집합
딕셔너리
튜플

백전능 JeonNeung Baek

Image Restoration, Video Coding, Computer Vision

이전 포스트

OpenCL 병렬프로그래밍을 활용한 CNN 가속화

0개의 댓글