[파이썬 알고리즘 인터뷰] - 4장 (빅오, 자료형)

 

 

 

 

 

 

 점근적 실행 시간(Asymptotic Running Time)

 

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

 

 

 

 

 

 

 시간복잡도(Time Complexity)

 

- 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)

 

 

 

 

 

 

 빅오 별 특징

 

- O(1) : 1초가 걸린다는  것이 아니라 입력값이 아무리 커도 실행 시간이 일정하다는 뜻이다. 상수 시간이라는 것이 빠르다고 생각이 들 수 있지만 일정하다는 것이 포인트이므로 이 상수값 자체가 엄청나게 크다면 사실상 일정한 시간의 의미가 없다. 해시테이블의 조회 및 삽입이 이에 해당한다.

 

- O(logN) : 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다. 이진 검색이 이에 해당한다.

 

- O(N) : 선형시간 알고리즘(Linear-Time)이라고도 하며 수행 시간이 입력값에 비례한다. 정렬되지 않은 리스트에서 최대값 또는 최솟값 경우가 이에 해당한다.

 

- O(NlogN) : 병합 정렬을 비롯한 대부분의 효율적인 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 Comparison Algorithm은 아무리 좋은 알고리즘도 O(NlogN)보다 빠를 수 없다. 물론 입력값이 최선인 경우, 비교를 건너뛰어 O(N)이 되며 Tim Sort가 이에 해당한다.

 

- O(N^2) : 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.

 

- O(2^N) : 피보나치를 재귀로 계산하는 알고리즘이 이에 해당한다.

 

- O(N!) : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(Traveling Salesman Problem)를 Brute Force로 풀이할 때가 이에 해당한다.

 

 

 

 

 

 

 

 

 

 빅오(O), 빅오메가(Ω), 빅세타(Θ)

 

- 빅오 : 상한(Upper Bound)를 의미한다. 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.

 

- 빅오메가 : 하한(Lower Bound)를 의미한다.

 

- 빅세타 : 평균을 의미한다.

 

- 학계와 달리 업계에서는 빅세타와 빅오를 하나로 합쳐서 단순화해 표현한다. 평균적인 시간보다 상한 시간으로 단순화해서 표현한다.

 

- 상한은 최악의 경우와 다르다. 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 적당히 정확하게 표현하는 것이다. 

 

 

 

 

 

 

 

 로무토 파티션(Lomuto Partition)

 

- 퀵 정렬(Quick Sort)시, 피벗을 정할 때 가장 우측을 택하는 가장 단순한 피벗 선택 방식이다.

 

 

 

 

 

 

 

 파이썬 정수형

 

- C언어와 달리 파이썬은 int의 범위를 넘어서는 정수형 데이터가 들어오면 오버플로우가 발생하는 것이 아니라 자동으로 long 타입으로 변경된다. 그래서 long 타입 선언없이 파이썬은 정수형 자료형으로 int만 가지고 있다. 

 

 

 

 

 

 파이썬 bool 타입

 

- bool은 엄밀히 따지면 논리 자료형이지만 파이썬에서는 내부적으로 1과 0으로 처리되는 int의 서브 클래스이다. 

 

 

 

 

 

 임의 정밀도

 

- 임의 정밀도 정수형이란 무제한 자릿수를 제공하는 정수형을 말한다. 정수를 숫자의 배열로 간주하고 자릿수 단위로 쪼개어 배열 형태로 표현한다.

 

 

 

 

 

 원시 타입

 

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

 

- C언어는 원시 타입만을 제공하며 JAVA는 원시타입과 객체를 동시에 제공한다.

 

- 파이썬은 애초에 편리한 기능 제공이 우선순위 이므로 느린 속도와 더 많은 메모리를 차지하더라도 다양한 기능을 제공하는 객체만 제공하고 원시 타입은 지원하지 않는다.

 

 

 

 

 

 

 가변 객체(mutable object) vs 불변 객체(immutable object)

 

클래스	불변 객체
bool	O
int	O
float	O
list	X
tuple	O
str	O
set	X
dict	X

 

 

 

 

 

 

 is vs ==

 

- 파이썬의 비교 연산자 중 is와 ==가 있다. 

 

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

 

- == : 값을 비교하는 연산자이다.