컴퓨터 과학에서 빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용되며, 알고리즘의 효율성을 분석하는 데에도 매우 유용하게 활용된다.
빅오
빅오 (O, big-O)란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법이다.
먼저 빅오는 점근적 실행 시간을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나다. 점근적 실행 시간이란 입력값 n이 커질 때 즉 입력값이 무한대를 향할 때 lim 함수의 실행 시간의 추이를 의미한다.
점근적 실행시간은 달리 말하면 시간 복잡도라 할 수 있다. 시간 복잡도의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오다. 빅오로 시간복잡도를 표현할 때는 최고차양만을 표기하며, 상수항을 무시한다.
예를 들어 입력값 n에 대해 4n^2+3n+4번 만큼 계산하는 함수가 있다면 이 함수의 시간 복잡도는 최고차항인 4n^2만을 고려한다.
· O(1) :입력값이 아무리 커도 실행 시간을 일정하다. 최고의 알고리즘이라고 할 수 있다. 또한 상수 시간에 실행된다 해도 상수값이 상상을 넘어설 정도로 크다면 사실상 일정한 시간의 의미가 없다.
· O(log n) :여기서부터 실행 시간은 입력값에 영향을 받는다. 그러나 로그는 매우 큰 입력값에도 크게 영향을받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다.
· O(n) :입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간 알고리즘이라고 한다.
· O(nlogn) :병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(nlogn)보다 빠를 수 없다.
· O(n^2) :버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.
· O(2^n) :피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. 간혹 n^2과 혼동하는 경우가 있는데 처음에는 비슷해 보이지만 2^n이 훨씬 더 크다.
· O(n!) :가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어렵다.
지금까지 시간복잡도를 표현하는 빅오에 대해서 알아봤다. 빅오는 시간 복잡도 외에도 공간 복잡도를 표현하는 데에도 널리 쓰인다. 또한 알고리즘은 흔히 '시간과 공간 트레이드오프 관계' 라고 불린다. 이 말은 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행시간이 느리다는 얘기이다.
상한과 하한
빅오는 상한을 의미한다. 이외에도 하한을 나타내는 빅오메가, 평균을 의미하는 빅세타가 있는데, 학계와 달리 업계에서는 빅세타와 빅오를 하나로 합쳐서 단순화해서 표현하려는 경향이 있다.
자료형
이번에는 파이썬이 어떤 자료형을 제공하는지, 이를 자료형에는 어떠한 특징이 있는지 알아보자.
파이썬 자료형
모든 자료형을 일일이 언급하기엔 너무 많기 때문에 여기서는 주요 자료형을 중심으로 몇 가지만 살펴본다.
- 숫자
- 파이썬에서는 숫자 정수형으로 int만을 제공한다. PEP 237을 통해 버전 2.4부터는 int가 충분하지 않으면 자동으로 long 타입으로 변경되는 구조가 됐으며 덕분에 오버플로가 발생하는 일은 사라졌다.
- bool은 엄밀히 따지면 논리 자료형인데 파이썬에서는 내부적으로 1(True)과 0(False)으로 처리되는 int의 서브 클래스다.
- 매핑
- 매핑 타입은 키와 자료형으로 구성된 복합 자료형이며, 파이썬에 내장된 유일한 매핑 자료형은 딕셔너리다.
- 집합
- 파이썬의 집합 자료형은 set은 중복된 값을 갖지 않는 자료형이다.
- 시퀀스
- 시퀀스는 우리말로 하면 '수열'같은 의미로, 어떤 대상의 순서 있는 나열을 뜻한다. 예를 들어 str은 문자의 순서 있는 나열로 문자열을 이루는 자료형이며, list는 다양한 값들을 배열 형태의 순서 있는 나열로구성하는 자료형이다. 파이썬에서는 list라는 시퀀스 타입이 사실상 배열의 역할을 수행한다.
