2021-03-20(Sat)

항목	내용
학습 날짜	2021-03-20(토)
학습 시간	11:00~24:00
학습 범위 및 주제	빅오, python
학습 목표	빅오와 python의 헷갈리는 부분을 파악한다.
동료 학습 방법	-

상세 학습 내용

코딩테스트 문제를 풀던 중 시간복잡도가 애매한 지점이 있어서 다시 한번 학습을 진행하였다. 이후 프로그래머스 코딩테스트 연습의 해시, 스택 문제를 풀었다.

시간 복잡도란?

알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다. 알고리즘은 '시간과 공간이 트레이드오프' 관계이기 때문에, 수행시간과 메모리 사용량을 평가기준으로 둔다.

• 시간 복잡도(Time Complexity): 수행시간에 해당

• 공간 복잡도(Space Complexity): 메모리 사용량에 해당

위 복잡도들은 입력의 크기가 충분히 클 때 의미있다.

빅오

빅오(O, big-O)란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법이다.

빅오는 가장 늦게 실행될 때, 즉 상한(Upper Bound)을 의미한다. 이외에도 가장 빨리 실행될 때, 즉 하한(Lower Bound)을 나타내는 빅오메가, 평균을 의미하는 빅세타가 있는데, 보통 평균적인 시간보다는 상한 시간으로 단순화해서 주로 표현한다.

상한을 최악의 경우와 혼동하지 말자. 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 '적당히 정확하게' 표현하는 방법일 뿐, 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해야 한다. 최선의 경우에도 상한이 존재하고, 역시 평균, 최악의 경우에도 상한이 존재한다. 빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.

분할 상환 분석

빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나이다. 시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 분할 상환 분석 방법이 등장하는 계기가 됐다. 가령 '동적 배열'의 경우 더블링이 일어나는 일은 어쩌다 한 번뿐이지만, 이로 인해 '아이템 삽입 시 시간 복잡도는 O(n)이다.'라고 얘기하는 건 지나치게 비관적이고 정확하지도 않다. 분할 상환은 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산할 수 있다.

자 이제 파이썬 연산들의 시간 복잡도를 확인해보자.

리스트

연산	시간 복잡도
len(a)	O(1)
a[i]	O(1)
a[i:j]	O(j-i)
elem in a	O(n)
a.count(elem)	O(n)
a.index(elem)	O(n)
a.append(elem)	O(1)
a.pop()	O(1)
a.pop(0)	O(n)
del a[i]	O(n)
a.sort()	O(nlogn)
min(a), max(a)	O(n)
a.reverse()	O(n)

딕셔너리

연산	시간 복잡도
len(a)	O(1)
a[key]	O(1)
a[key] = value	O(1)
key in a	O(1)

물론 최악의 경우엔 O(n)이 될 수 있다.

학습 내용에 대한 개인적인 총평

코딩 테스트 문제를 푸는게 즐겁다. 그 동안 프로젝트를 하느라 꾸준히 하지 못했는데 이제는 정말 매일 문제를 풀어야겠다 :) python 메서드들이 너무 편하고 내부 동작도 예측은 되지만 시간 복잡도를 정확히 꾀고 있는 느낌이 들지 않았다. 애초에 시간 복잡도란 뭐지? 내가 정말 제대로 답변할 수 있나? 하는 의문이 들어서 다시 학습했는데 만족스럽다. 이런식으로 내가 모르는 부분을 다시금 돌아보고 제대로 학습해 나가야겠다.

다음 학습 계획

• 디자인패턴 학습