Python list 연산에 따른 시간 복잡도

python list 연산에 따른 시간 복잡도

 

시간 복잡도가 O(1)인 연산

 

len(a)

len(a)는 리스트 전체 요소의 개수를 리턴합니다. 사용 예시는 다음과 같습니다.

a = [1,2,3,4,5]
print(len(a))

## 출력값
# 5

 

a[i]

a[i]는 리스트중에서 해당 인덱스에 해당하는 값을 가져옵니다.

a = [1,2,3,4,5]
print(a[3])

## 출력 값
# 4

 

a.append(x)

a.append(x)는 해당 리스트 맨뒤에 x를 추가해 줍니다.

a = [1,2,3]
print(a)
a.append(4)
print(a)

## 출력 값
# [1,2,3]
# [1,2,3,4]

 

a.pop()

a.pop()는 해당 리스트 맨 뒤에 있는 값을 pop 해줍니다. (스택의 연산 pop)

a = [1,2,3,4,5]
print(a.pop())

## 출력 값
# 5

 

시간 복잡도가 O(k)인 연산

 

시간 복잡도가 O(k)인 연산은 하나 입니다.

a[i:j]

리스트 a에서 i부터 j까지 슬라이싱 합니다. 객체 k개를 조회 해야 하므로 시간복잡도가 k입니다.

a = [1,2,3,4,5]
print(a[1:3])

## 출력 값
# [3,4]

 

시간 복잡도가 O(n)인 연산

 

x in a

x 값이 list a에 있는지 확인하는 연산 입니다. x가 있는지확인하기 위해 리스트 a를 전체 탐색 해야 하므로 시간의 복잡도가 n 입니다.

a = [1,3,5,7,9]
print(2 in a)

## 출력 값
# False

 

a. count(x)

리스트 a에서 x가 몇개 있는지 count해줍니다. 마찬가지로 몇개 있는지 확인하기 위해 a를 전체 탐색 해야 하므로 시간의 복잡도가 n입니다.

a = [1,1,1,2,3,4,5,5,5,6]
print(a.count(1))

## 출력 값
# 3

 

a.index(x)

리스트 a에서 x의 인덱스가 어디에 있는지 출력해 줍니다.

a = [5,4,3,2,1]
print(a.index(5))

## 출력 값
# 0

 

a.pop(0)

리스트의 첫번째 값을 출력해 주는 연산입니다. 맨뒤에 값을 빼내는 pop는 복잡도가 O(1)인데 이것은 O(N)인 이유는 맨앞에 있는 값을 출력 해주기 위해 전체 복사를 해주기 위해서 입니다.

따라서 리스트 말고 deque를 이용하면 O(1)이 나옵니다. 백준에서 이 문제도 pop이 아닌 deque로 해결해야 시간초과 오류가 나지 않습니다.

백준 문제 : https://www.acmicpc.net/problem/18258 (큐2)

 

a = [5,4,3,2,1]
print(a.pop(0))
print(a)
## 출력 값
# 5
# [4, 3, 2, 1]
 

 

del a[i]

해당 인덱스에 있는 값을 지워줍니다. 만약 최악의 경우 O(n)이 나옵니다.

a = [1,2,3,4,5]
del a[2]
print(a)
## 출력 값
# [1, 2, 4, 5]

 

min(a), max(a)

최솟값/최댓값을 계산하기 위해 리스트를 전체 탐색한 후 최대 최소를 구합니다.

a = [1,3,5,7,9,112,12,-3]
print(min(a))
print(max(a))
## 출력 값
# -3
# 112

 

a.reverse()

모든 리스트의 값들을 뒤집습니다.

a = [1,2,3,4,5]
a.reverse()
print(a)
## 출력 값
# [5,4,3,2,1]

 

시간 복잡도가 O(nlogn)인 연산

 

a.sort( )

배열을 정리 하기 위해 TimSort ( Merge Sort + Insert Sort )를 이용합니다. 이것은 최소 O(n)이고 최악은 O(nlogn)입니다.

a = [5,3,2,3,1,11,9,0]
a.sort()
print(a)
## 출력 값
# [0, 1, 2, 3, 3, 5, 9, 11]