[Python 알고리즘] 빅오, 자료형
빅오
빅오
- 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법
- 점근적 실행시간(Asymptotic Running Time) 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나
시간복잡도
- 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산 복잡도. 이를 위한 표현식이 빅오.
- O(1) : 입력값이 아무리 커도 실행 시간은 일정. 최고의 알고리즘이라 할 수 있음. 해시 테이블의 조회 및 삽입이 여기에 해당.
- O(log n) : n의 크기에 대해 매우 견고한 계산 복잡도.
- O(n) : 알고리즘 수행 시간이 입력값에 비례하는 선형 시간 알고리즘. 정렬되지 않은 리스트에서 최댓값 또는 최솟값 찾는 경우가 이에 해당되어 이 값을 찾기 위해 모든 입력값을 적어도 한 번 이상은 살펴봐야함.
- O(n log n) : 병합 정렬을 비롯한 대부분의 효율 좋은 정렬알고리즘이 이에 해당. 입력값이 최선인 경우에만 비교를 건너뛰어 O(n)이 될 수 있으며 팀소트(Timsort)가 이런 로직을 갖고 있음.
- O(n^2) : 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당.
- O(2^n) : 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당.
- O(n!) : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당. 가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 제한 시간 내에 계산이 어려움.
알고리즘은 흔히 '시간과 공간이 트레이드오프' 관계다. 즉, 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다.
빅오메가 : 하한, 빅세타 : 평균
상한과 최악의 경우를 혼동하는 것이 최악이다.
정리하면, 빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.
분할 상환 분석
- 빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나로, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것이 지나치게 비관적이라는 이유로 등장.
- 유용한 대표적인 예는 '동적 배열'이며, 동적 배열에서 더블링이 일어나는 일은 어쩌다 한 번뿐이지만, 이로 인해 '아이템 삽입 시간 복잡도는 O(n)이다'라고 말하는 것은 비관적이고 정확하지도 않다.
- 그래서 이러한 경우 '분할 상환' 또는 '상각'이라고 표현하는 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 계산이 가능하고, 이 때 시간 복잡도는 O(1)이 된다.
자료형
숫자
- 파이썬의 int는 long과의 단일형으로 임의 정밀도를 지원하여, 고정 정밀도인 타 언어의 int에 비해 계산 속도는 저하되지만 더욱 단순한 구조이고, 오버플로도 고민할 필요가 없다.
- bool(1(True) / 0(False))은 엄밀히는 논리 자료형이지만, 파이썬에서는 int의 서브 클래스이다.
매핑
- 키와 자료형으로 구성된 복합 자료형이며, 파이썬에 내장된 유일한 매핑 자료형은 바로 딕셔너리다.
시퀀스
- 어떤 특정 대상의 순서가 있는 자료형
- 불변형 : str, tuple, bytes.
- 가변형 : 리스트
파이썬은 short, float, double 등의 원시 타입을 지원하지 않는다. 원시 타입의 속도를 포기하고 객체의 다양한 기능과 편의성을 택했다
불변객체
- 문자, 숫자형. read-only로 값을 담고 있는 변수는 사실 참조일 뿐이고, 실제 값을 갖고 있는 int 와 str은 모두 불변 객체다.
가변 객체
- list. 내부 값이 언제든 바뀔 수 있다.
is : id()값을 비교하는 함수
== : 실제 값이 같은지 비교하는 함수
속도
- 넘파이는 C로 만든 모듈이며 내부적으로 리스트를 C의 원시 타입으로 처리하여 리스트보다 훨씬 빠르다
자료구조 vs 자료형
- 자료형 : 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지를 알려주는 일종의 데이터 속성. ex ) 정수, 실수, 문자열 등 해당 언어에서 지원하는 원시 자료형까지 포함하는 모든 자료의 유형.
- 자료구조 : 원시 자료형을 기반으로 하는 배열, 연결 리스트, 객체 등을 말하며 원시 자료형을 조합한 자료구조는 복합 자료형. 컴퓨터과학에서는 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조작, 관리, 저장 구조를 말한다.
Reference
[0] 파이썬 알고리즘 인터뷰, 박상길 지음