파이썬의 빅오, 자료형

도서 파이썬 알고리즘 인터뷰 4장 중

빅오 

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

시간 복잡도 Time Complexity(점근적 실행 시간)의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도 Computational Complexity를 의미. 계산 복잡도를 표기하는 대표적인 방법이 빅오이다. 

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

 

- O(1)

입력값이 아무리 커도 실행 시간은 일정하다.  

 

- O(log n):

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

 

- O(n):

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

 

- O(n log n):

적어도 모든 수에 대해 한번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n log n)보다 빠를 수 없다. 물론 입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있으며 팀소트Timesort가 이런 로직을 갖고 있다. 

 

- O(n^2):

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

 

- O(2^n):

피보나치 수를 재귀로 계산하는 알고리즘이 해당된다. n^2과 처음에는 비슷해 보이지만 2^n이 훨씬 더 크다.

 

- O(n!) :

가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 다항시간 내에는 계산이 어렵다.

 

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

 

| 상한과 최악

빅오(O)는 상한 Upper Bound 의미. 하한 Lower Bound을 나타내는 빅오메가(Ω), 평균을 의미하는 빅세타 (θ) 

평균적인 시간보다는 상한 시간으로 단순화해서 주로 표현한다.

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

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

 

| 분할 상환 분석

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

 

| 병렬화

일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있다. 

 

 

자료형

| 파이썬 자료형 

...

| 숫자 

파이썬에서는 숫자 정수형으로 int 만을 제공한다. int는 임의 정밀도를 지원하며, 더 이상 파이썬에서 고정 정밀도 정수형을 지원하지 않게 됐다. 

bool은 엄밀히 따지면 논리 자료형인데 파이썬에서는 1(ture)과 0(false)로 처리되는 int의 서브 클래스 

int는 object의 하위 클래스이기도 하다. object > int > bool 

 

임의 정밀도 정수형이란 무제한 자릿수를 제공하는 정수형을 말한다. 

 

| 매핑 Mapping 

키와 자료형으로 구성된 복합 자료형. 딕셔너리

| 집합

파이썬의 집합 자료형인 set은 중복된 값을 갖지 않는 자료형. 

| 시퀀스 Sequence 

'수열' 같은 의미로, 어떤 특정 대상의 순서 있는 나열을 뜻함. 불변과 가변으로 구분하는데 말 그대로 불변은 값을 변경할 수 없다. srt,tuple,bytes가 불변으로 해당된다.

| 원시 타입 Primitive Type 

원시 타입은 메모리에 정확하게 타입 크기만큼의 공간을 할당하고 그 공간을 오로지 값으로 채워넣는다. 

언어	지원 타입 형태
C	원시 타입
자바	원시 타입, 객체
파이썬	객체

| 객체 

파이썬은 모든 것이 객체다. 이 중에서 불변 객체와 가변 객체로 구분할 수 있다. ...

 

- is 와 == 

비교 연산자 중 is와 ==가 있다. 이 둘읜 파이썬의 객체 구조와 관련이 깊다. 

is는 id()값을 비교하는 함수다. None은 널null로서 값 자체가 정의되어 있지 않으므로 ==로 비교가 불가능하다. 

따라서 is로만 비교가 가능하다. 

 

| 속도 

...