빅오, 자료형

빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)와 함께 공간 요구사항(공간 복잡도)가 어떻게 증가하는지를 분류하는 데 사용된다.

빅오

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

빅오는 접근적 실행시간을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나이다.

접근적 실행 시간이란?
입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 함수의 실행 시간의 추이를 의미한다.

디스크에 있는 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자. 파일 크기가 작다면, 즉 n이 작다면 O(n)의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달하는 게 더 빠를 수 있다.

파일이 아무리 커도 비행기를 통한 파일 전송은 O(1)로 항상 일정한 시간이 소요되기 때문이다. 이것이 바로 접근적 실행 시간이며, 빅오는 접근적 실행 시간을 표기하는 방법 중 하나다.

접근적 실행 시간은 달리 말하면 시간 복잡도라 할 수 있다.

시간복잡도란?
어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도
계산 복잡도를 표기하는 대표적인 방법이 빅오

빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다.

예를 들어, 입력값 n에 대해 4n^2+3n+4번만큼 계산하는 함수가 있다면 이 함수의 시간 복잡도는 최고차항인 4n^2만 고려한다. 이 중에서도 상수항은 무시하며 n^2만을 고려한다.

즉, 여기서의 시간 복잡도는 O(n^2)이 된다.

이처럼 시간 복잡도를 표기할 때는 입력값에 따른 알고리즘의 실행 시간의 추이만을 살피게 된다.

O(1)

입력값이 아무리 커도 실행 시간은 일정하다. (최고의 알고리즘)
O(1)에 실행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당한다.

O(log n)

실행 시간은 입력값에 영향을 받지만, 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 이진 검색이 이에 해당한다.

O(n)

입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간 알고리즘이라고 한다.
정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.

O(n log n)

병렬 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n log n)보다 빠를 수 없다. 물론 입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있으며 팀소트가 이런 로직을 갖고 있다.

O(n^2)

버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.

O(2^n)

피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다.

O(n!)

각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당하며 가장 느린 알고리즘이다. 입력값이 조금만 커져도 웬만한 다항시간 내에는 계산이 어렵다.

빅오는 시간 복잡도 외에도 공간 복잡도를 표현하는 데에도 널리 쓰인다. 또한 알고리즘은 흔히 '시간과 공간이 트레이드오프' 관계다. 이 말은 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다는 얘기다.

상한과 최악

빅오(O)는 상한을 의미한다. 이외에도 하한을 나타내는 빅오메(Ω), 평균을 의미하는 빅세타(Θ)가 있는데, 업계에서는 빅세타와 빅오를 하나로 합쳐서 단순화해서 표현하려는 경향이 있다.

※ 상한 : 가장 늦게 실행될 때
※ 하한 : 가장 빨리 실행될 때

여기서 한 가지 중요한 점은 상한을 최악의 경우와 혼동하는 것인데, 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 '적당히 정확하게' 표현하는 방법일 뿐, 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해야한다.

즉, 빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.

분할 상환 분석

시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 분할 상환 분석 방법이 등장하는 계기가 됐다.

분할 상환 분석이란?
'분할 상환' 또는 '상각'이라고 표현하는, 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산할 수 있는 방법


이 경우 동적 배열의 삽입 시 시간 복잡도는 O(1)이 된다.

병렬화

일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있다. 알고리즘 자체의 시간 복잡도 외에도 알고리즘이 병렬화가 가능한지는 근래에 알고리즘의 우수성을 평가하는 매우 중요한 척도 중 하나이기도 한다.

자료형

파이썬 자료형

숫자

파이썬에서는 숫자 정수형으로 int만을 제공한다. bool은 엄밀히 따지면 논리 자료형인데 파이썬 내부적으로 1(True)과 0(False)으로 처리되는 int의 서브 클래스다. int는 object의 하위 클래스이기도 하기 때문에 결국 다음과 같은 구조를 띤다.

object > int > bool

논리 자료형의 값인 True와 정수형의 값인 1을 비교해보면 다음과 같다.

>>> True == 1

True

>>> False == 0

True

매핑

매핑 타입은 키와 자료형으로 구성된 복한 자료형이며, 파이썬에 내장된 유일한 매핑 자료형은 바로 딕셔너리다.

집합

파이썬의 집합 자료형인 set은 중복된 값을 갖지 않는 자료형이다. 파이썬에서 빈 집합은 다음과 같은 형태로 선언한다.

>>> a = set()
>>> a

set()

>>> type(a)

<class 'set'>

빈 집합이 아닌 값이 포함된 집합을 선언할 때는 a = {1, 2, 3} 형태로 하는데, 집합은 딕셔너리와 동일하게 중괄호({})를 사용하므로 이 점에 유의해야 한다.

set은 입력 순서가 유지되지 않으며, 다음처럼 중복된 값이 있을 경우 하나의 값만 유지한다.

>>> a = {3, 2, 3, 5}
>>> a

{2, 3, 5}

시퀀스

시퀀스는 우리말로 하면 '수열' 같은 의미로, 어떤 특정 대상의 순서 있는 나열을 뜻한다. 시퀀스는 불변과 가변으로 구분하는 말 그대로 불변은 값을 변경할 수 없다. 여기에는 str, tuple, bytes가 해당되는데 한번 이 타입으로 선언되는 값은 변경할 수 없다.

>>> a = 'abc'
>>> id('abc')

4317530408

>>>id(a)

4317530408

>>> a = 'def'
>>> id('def')

4318831648

>>> id(a)

4318831648

각각의 메모리 주소를 출력해보면 a 변수는 처음에는 abc를 참조했다가 이후에는 def를 참조하도록 변경되었을 뿐이고, a 변수에 할당된 str타입인 abc와 def는 변경된 적이 없다.

반면 list는 가변이다. 리스트는 자유롭게 값을 추가, 삭제할 수 있는 동적 배열이다.

원시 타입

파이썬은 원시 타입을 지원하지 않는다. 파이썬은 애초에 편리한 기능 제공에 우선 순위를 둔 만큼 느린 속도와 더 많은 메모리를 차지하더라도 훨씬 더 다양한 기능을 제공할 수 있는 객체에 관심을 둔다. 파이썬은 원시 타입의 속도를 포기하는 대신 객체의 다양한 기능과 편의성을 택했다.

객체

파이썬은 모든 것이 객체다. 이 중에서 크게 불변 객체와 가변 객체로 구분할 수 있는데, 이미 시퀀스의 경우 불변과 가변을 구분해 정리한 바 있다. 이외에도 파이썬의 각 자료형에 대해 불변 여부는 아래와 같다.

불변 객체

파이썬은 모든 것이 객체기 때문에 변수를 할당하는 작업은 해당 객체에 대해 참조한다는 의미다. 여기에는 예외가 없으며 심지어 문자와 숫자도 모두 객체다. 다만, 문자와 숫자는 불변 객체라는 차이만 있을 뿐이다.

>>> 10
>>> a = 10
>>> b = a
>>> id(10), id(a), id(b)

(4393858752, 4393858752, 4393858752)

만약 모두가 원시 타입이라면 각각의 값들은 각 메모리의 다른 영역에 위치할 것이다. 그러나 파이썬은 모든 것이 객체이므로, 메모리 상에 위치한 객체의 주소를 얻어오는 id() 함수를 실행한 결과는 놀랍게도 모두 동일하다. 하지만 10이 11이 된다면 a 변수와 b 변수 모두 값이 11로 바뀌게 될 것이라고 생각하겠지만 값을 담고 있는 변수는 사실은 참조일 뿐이고 실제로 값을 갖고 있는 int와 str은 모두 불변객체이기 때문에 값이 변하지 않는다.

이외에도 불변 객체로 tuple이 있다. 말 그대로 한 번 값을 담아두면 더 이상 값을 변경할 수 없다. 상수처럼 read-only 용도로 사용하거나 무엇보다 값이 변하지 않기 때문에 dict의 키나 set의 값으로도 사용할 수 있다. list는 언제든 값이 변할 수 있기 때문에 dict의 키로 정하거나 set의 값으로는 추가할 수 없다.

가변 객체

가변 시퀀스 중 하나로 리스트가 있다. int, str과 달리 list는 값이 바뀔 수 있으며, 이 말은 다른 변수가 참조하고 있을 때 그 변수의 값 또한 변경된다는 얘기다.

>>> 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와 ==가 있다. 이 둘의 관계는 파이썬 객체 구조와 관련이 깊다.
is는 id()값을 비교하는 함수다. None은 널(null)로서 값 자체가 정의되어 있지 않으므로 ==로 비교가 불가능하다.

if a is None:
    pass

==는 잘 알다시피 값을 비교하는 연산자이다. 다음과 같이 리스트를 생성해서 비교해보면 ==와 is의 차이에 대해서는 금방 이해가 될 것이다.

>> a = [1, 2, 3]
>> a == a
True
>> a == list(a)
True
>> a is a
True 
>> a is list(a)
True

값은 동일하지만 list()로 한 번 더 묶어주면, 별도의 객체로 복사가 되고 다른 ID를 갖게 된다. 따라서 is는 False가 된다.

>> a = [1, 2, 3]
>> a == copy.deepcopy(a)
True
>> a is copy.deepcopy(a)
False

copy.deepcopy()로 복사한 결과 또한 값은 같지만 ID는 다르기 때문에, ==로 비교하면 True, is로 비교할 경우 False가 된다.

속도

파이썬의 객체 구조는 파이썬이 C나 자바 같은 다른 언어에 비해 느린 중요한 이유 중 하나다.

단수히 정수형의 덧셈 연산을 하는 경우에도 메모리에서 값을 꺼내 한번 연사하면 끝인 원시 타입에 비해, 파이썬의 객체는 값을 꺼내는 데만 해도 var->PyObject_HEAD에서 타입코드를 찾는 등 여러 단계의 부가 작업이 필요하다.

자료구조, 자료형, 추상 자료형


자료구조란?
데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장구조


자료형이란?
컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지를 알려주는 일종의 데이터 속성


추상 자료형이란?


줄여서 ADT라 부르며 자료형에 대한 수학적 모델을 지칭한다. 쉽게 정리하자면, 해당 유형의 자료에 대한 연산들을 명기한 것이다.