컴퓨터 과학에서 빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용되며, 알고리즘의 효율성을 분석하는 데에도 매우 유용하게 활용된다.
빅오란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.
시간 복잡도: 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미하며 계산 복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다.
빅오 표기법의 종류
O(1) : 입력값이 아무리 커도 실행 시간은 일정하다. 최고의 알고리즘
O(1)에 실행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당한다.
O(logn) : 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편이므로 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 이진 검색이 이에 해당한다.
O(n) : 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다.이러한 알고리즘을 선형 시간 알골즘이라고 한다. 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야한다.
O(nlong) : 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한번 이상은 비교해야 하는 비교 기간 정렬 알고리즘은 아무리 좋은 알고리즘도 O(nlogn)보다 빠를 수 없다. 물론 입력값이 최선인 경우 비교를 건너 뛰어 O(n)이 될 수 있으며 팀소트가 이런 로직을 가지고 있다.
O(n2) : 버블 정렬같은 비효율적인 정렬 알고리즘이 이에 해당한다.
O(2N) : 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. 간혹 N2과 혼동 하는 경우가 있는데 처음에는 비슷해 보이지만 2N이 훨씬 더 크다.
O(N!) : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(TSP)를 브루트 포스로 풀이할 때가 이에 해당하며 가장 느린 알고리즘으로 입력값이 조금만 커져도 웬만한 다항시간 내에서는 계산이 어렵다.
상한과 최악
빅오(O)는 상한(Upper bound)을 의미한다. 하한을 의미하는 빅오메가, 평균을 의미하는 빅세타가 있는데, 학계와 달리 업계에서는 빅세타와 빅오를 합쳐서 단순화해서 표현하려는 경향이 있다.
상한을 최악으로 혼동하는 경우가 있는데 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 적당히 정확하게 표현하는 방법일 뿐, 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해야 한다.
상한: 알고리즘이 가장 늦게 실행될 때
하한: 알고리즘이 가장 빨리 실행될 때
분할 상한 분석
시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 분할 상환 분석 방법이 등장하는 계기가 됐다.
분할 상환 또는 상각이라고 표현하는 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산할 수 있다.
병렬화
일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있다.
알고리즘의 시간 복잡도 외에도 알고리즘이 병렬화가 가능한 지는 근래에 알고리즘의 우수성을 평가하는 매우 중요한 척도 중 하나이기 때문이다.
불변 - 문자열/튜플/바이트
숫자
int보다 더 큰 값은 어떤 자료형에 보관해야 할까? 파이썬에는 long이 없을까? 파이썬 2에는 long이 있었고 int는 C스타일의 고정 정밀도(Fixed Precision) 정수형이었꼬 long은 임의 정밀도(Arbitrary-Precision) 정수형이었다. PEP237을 통해 버전 2.4부터는 int가 충분하지 않으면 자동으로 long 타입으로 변경되는 구조가 됐으며 덕분에 C와 달리 오버플로가 발생하는 일은 사라졌다.
버전 3부터는 아예 int 단일형으로 통합됐다. int는 임의 정밀도를 지원하며 더이상 고정 정밀도 정수형은 지원하지 않게 됐다.
object > int > bool (int의 서브클래스)
논리 자료형은 내부적으로 정수값 (0,1)을 갖고 있다.
임의 정밀도
임의 정밀도 정수형이란 쉽게 말해 무제한 자릿수를 제공하는 정수형을 말한다. 정수를 숫자의 배열로 간주하며 즉 자릿수 단위로 쪼개어 배열 형태로 표현한다.
숫자를 임의 정밀도로 처리하면 계산 속도가 저하된다. 그러나 숫자를 단일형으로 처리할 수 있으므로 언어를 매우 단순한 구조로 만들 수 있을 뿐만 아니라 언어를 사용하는 입장에서도 더이상 오버플로를 고민할 필요가 없어 잘못된 계산 오류를 방지 할 수 있다. 자바의 경우에도 기본 정수형 외에 이렇게 임의 정밀도 연산을 지원하는 BigInteger라는 자료형을 별도로 제공하며 파이썬의 경우 기본 정수형인 int가 임의 정밀도 연산까지 수행한다.
매핑
키와 자료형으로 구성된 복합 자료형이며, 파이썬에 내장된 유일한 매핑 자료형은 바로 딕셔너리이다.
집합
파이썬의 집합 자료형인 set은 중복된 값을 갖지 않는 자료형이다.
set은 입력 순서가 유지되지 않으며, 중복된 값이 있으면 하나의 값만 유지한다.
>>> a = {1,2,3}
>>> type(a)
<class 'set'>
>>> a = {'a':1,'b':2,'c':3}
>>> a
{'a': 1, 'b': 2, 'c': 3}
>>> type(a)
<class 'dict'>
>>>시퀀스
어떤 특정 대상의 순서 있는 나열
예를들어 str은 문자의 순서 있는 나열로 문자열을 이루는 자료형이며, list는 다양한 값들을 배열 형태의 순서 있는 나열로 구성하는 자료형이다. 파이썬에서는 list라는 시퀀스 타입이 사실상 배열의 역할을 수행한다.
시퀀스는 불변(immutable)과 가변(Mutable)로 구분하는 데 말 그대로 불변을 값을 변경할 수 없다. 여기에는 str, tuple,byte가 해당되는데
>>> a = 'abc'
>>> a = 'def'
>>> type(a)
<class 'str'>
>>> a = 'abc'
>>> id(a)
2618379778800
>>> a = 'def'
>>> id(a)
2618380202096
>>> id('def')
2618380202096
>>> a[1]='d'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment
>>>원시타입
C나 자바 같은 대표적인 프로그래밍 언어들은 기본적으로 원시 타입을 제공한다. C언어는 동일한 정수형이라도 크기나 부호에 따라 매우 다양한 원시 타입을 제공한다.
원시 타입은 메모리에 정확하게 타입 크기만큼의 공간을 할당하고 그 공간을 오로지 값으로 채워넣는다. 만약 배열이라면 이 그림처럼 물리 메모리에 자료형의 크기만큼 공간을 갖는 요소가 연속된 순서로 배치되는 형태가 된다.
C: 원시타입
자바: 원시타입, 객체
파이썬: 객체
파이썬은 모든 것이 객체다. 파이썬에서 변수를 할당하는 작업은 해당 객체에 대해 참조를 한다는 의미다. 여기에는 예외가 없으며 심지어 문자와 숫자도 모두 객체다. 다만 문자와 숫자는 불변 객체라는 차이가 있다.
>>> 10
10
>>> a = 10
>>> b = a
>>> id(10), id(a), id(b)
(2618374449744, 2618374449744, 2618374449744)
>>>10이라는 숫자는 a라는 변수에 할당하고 다시 b라는 변수에 a를 할당했다.
만약 모두 원시 타입이라면 각각의 값들은 각 메모리의 다른 영역에 위치할 것이다. 하지만 파이썬은 모든 것이 객체이므로 메모리 상에 위치한 객체의 주소를 얻어오는 id() 함수를 실행한 결과는 모두 동일하다.
만약 10이 11이 된다면 a 변수와 b 변수 모두 값이 11로 바뀌게 될 것이다. 하지만 문자와 숫자는 불변 객체이기 때문에 값을 변경할 수 없다.
값을 담고 있는 변수는 사실은 참조일 뿐이고 실제로 값을 갖고 있는 int와 str은 모두 불변 객체다. 이외에도 불변 객체로 tuple이 있다. 상수처럼 read-only 용도로 사용하거나 무엇보다 값이 변하지 않기 때문에 dict의 키나 set의 값으로도 사용할 수 있다.
가변객체
>>> a = [1,2,3,4,5]
>>> b = a
>>> b
[1, 2, 3, 4, 5]
>>> a[2]=4
>>> a
[1, 2, 4, 4, 5]
>>> b
[1, 2, 4, 4, 5]
>>>is ==
is는 객체의 id()값을 비교하는 함수다. None은 null로서 값 자체가 정의되어 있지 않으므로 ==로 비교가 불가능하다. 따라서 다음과 같이 is로만 비교가 가능하다
if a is None:
pass
>>> a= [1,2,3]
>>> a == a
True
>>> a == list(a)
True
>>> list(a)
[1, 2, 3]
>>> id(a)
2618379817984
>>> list(a)
[1, 2, 3]
>>> id(list(a))
2618380202368
>>> a is list(a)
False
// 값은 동일하지만 list()로 한번 더 묶어주면
// 별도의 객체로 복사가 되고 다른 ID를 갖게 된다. 따라서 is는 False가 된다.
>>> import copy
>>> a == copy.deepcopy(a)
True
>>> a is copy.deepcopy(a)
False
>>>
copy.deepcopy()로 복사한 결과 또한 값이 같지만 ID는 다르기 때문에 ==로 비교하면
True is로 비교할 경우 False가 된다.
항상 입력 순서가 유지되는 collections.OrderedDict()
조회시 항상 디폴트 값을 생성해 키 오류를 방지하는 collections.defaultDict()
요소의 값을 키로 하고 개수를 값 형태로 만들어 카운팅하는
collections.Counter()등이 있다.
IndexError 처리
try:
print(a['key4'])
except KeyError:
print("존재하지 않는키")
if 'key4' in a:
print("존재하는 키")
else:
print("존재하지 않는 키")defaultdict()
존재하지 않는 키를 조회할 경우 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해준다.
마찬가지로 실제로는 collections.defaultdict()클래스를 갖는다
Counter 객체
a = [1,2,3,4,5,6,6]
b = collections.Counter(a)
Counter 객체는 이처럼 키에는 아이템 값이 값에는 해당 아이템의 개수가 들어간 딕셔너리를 생성한다. 실제로는 다음과 같이 딕셔너리를 한 번 더 래핑한
collections.Counter 클래스를 갖는다.
b.most_common(2)
가장 빈도가 높은 2개의 요소 출력
OrderedDict
대부분의 언어에서 해시 테이블을 이용한 자료형은 입력 순서가 유지되지 않는다.
