알고리즘의 효율성을 분석하는데 사용하는 빅오와 파이썬에서 제공하는 자료형의 종류와 특징을 설명한다.
빅오
빅오란?
: 입력값이 무한으로 계속해서 들어올 때, 함수의 실행 시간의 추이를 판단하는 수학적 표기법(점근적 실행시간 = 시간 복잡도). 어떠한 알고리즘을 실행할 때 걸리는 시간을 설명.
컴퓨터는 속도가 매우 빠르기 때문에 입력의 크기가 작을 때는 상관이 없지만, 입력의 크기가 매우 커지면 수행 시간에 차이가 많이 날 수 있다.
계수는 모두 무시하고, 최고차항만 표시한다.
빅오 표기법 종류
O(1)
입력되는 값이 아무리 커져도 알고리즘 실행 시간은 쭉 일정하다.
최고의 알고리즘이지만 찾아내기 어렵다.
ex) 해시 테이블의 조회/삽입
O(log n)
ex) 이진 검색
O(n)
선형 시간 알고리즘
ex) 정렬되어 있지 않은 리스트에서 최대값/최솟값 찾기
O(n log n)
대부분의 효율이 좋은 알고리즘이 여기에 해당한다.
ex) 병합정렬
O()
비효율적인 정렬 알고리즘이 여기에 해당한다.
ex) 버블정렬
O()
재귀 알고리즘이 여기에 해당한다.
ex) 피보나치
O(n!)
가장 느린 알고리즘으로, 입력되는 값이 조금만 커져도 알고리즘 실행 시간이 매우 느려진다.
ex) TSP 문제를 브루트 포스로 풀이하는 경우
시간 복잡도와 공간 복잡도 관계
: 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 실행 시간이 느린 알고리즘은 공간을 적게 사용한다.
상한과 최악
- 빅오 : 상한
- 빅오메가 : 하한
- 빅세타 : 평균
빅오 표기법은 알고리즘의 적당한 시간 복잡도를 표현하는 방법이기 때문에, 최악/평균적 시간 복잡도와는 다르다는 것을 기억해야 한다.
분할 상환 분석
: 최악의 경우를 여러 번에 나누어서 시간 복잡도를 계산한다.
알고리즘이 실행될 때, 최악의 경우가 발생하는 것이 매우 드문 경우에는 빅오(최악의 상황을 살피는 것)는 정확하지 않을 수 있다. 이 이유로 분할 상환 분석이 등장하였다.
병렬화
새롭게 알고리즘의 우수성을 평가하는 척도로 주목받고 있다.
자료형
숫자
정수형
- 정수 - int
- 불리언 - bool
: int의 서브 클래스로 구분된다.
True와 False를 1,0과 비교가 가능하다.
실수
- 실수 - float
매핑
딕셔너리
- 딕셔너리 - dict
: 키와 자료형으로 구성되어 있다.
집합형
집합
- 집합 - set
: 중복된 값을 가지지 않는다. 중괄호를 사용해서 선언한다. 입력된 순서가 유지되지 않고, 중복된 값이 입력되면 하나만 유지된다.
sample_set = set()
sample_set = {'a', 'b', 'c'}시퀀스
: 순서있는 나열을 뜻한다.
불변
: 값을 변경할 수 없다.
- 문자열 - str
- 튜플 - tuple
- 바이트 - bytes
가변
: 값을 변경할 수 있다.
- 리스트 - list
객체
파이썬은 모든 것이 객체로 이루어져 있다. 크게 두 객체로 분류할 수 있다.
불변 객체
: 메모리 상에 위치한 객체의 주소를 받아와서 사용한다. 불변 객체들은 dict의 키나 set의 값으로 사용될 수 있다.
- bool, int, float, tuple, str
가변 객체
: 가변 객체가 다른 가변 객체를 참조하고 있을 때 값이 바뀌면 함께 값이 변경된다.
- list, set, dict
파이썬 is와 ==
is는 id() 값을 비교하는 함수이고, ==은 값을 비교하는 연산자이다.
