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

빅오( big - O )

- 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법

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

 

- 점근적 실행 시간을 표기할 때 사용하는 수학적 표기법

* 점근적 실행 시간 : 입력값 n이 무한대로 커질 때, 함수의 실행 시간의 추이를 의미함

시간 복잡도(점근적 실행시간)

- 어떤 알고리즘을 수행하는 데 걸리는 시간, Computational Complexity

- 빅오로 시간 복잡도를 표현할때, 최고차항만 표기, 계수는 무시

- 예를 들어, 4n^2 + 3n + 4의 시간 복잡도는 O(n^2)

 

- 공간복잡도를 표현하는 데에도 사용

- 시간과 공간이 트레이드오프 관계

- 실행 시간이 빠른 알고리즘은 공간을 많이 사용, 공간을 적게 차지하는 알고리즘은 실행 시간이 느림

O(1)	- 입력값이 아무리 커도 실행 시간을 일정 - 상수값이 매우 크다면 일정한 시간의 의미는 없음 - 해시 테이블의 조회 및 삽입이 이에 해당
O(log n)	- 실행 시간은 입력값에 영향을 받음 - 로그는 매우 큰 입력값에도 크게 영향을 받지 않은 편 - 검색 알고리즘이 이에 해당
O(n)	- 입력값만큼 실행 시간에 영향을 받음 - 알고리즘 수행하는데 걸리는 시간은 입력값에 비례 - 선형 시간 알고리즘 - 정렬되지 않은 리스트에서 최댓값 혹은 최솟값을 찾는 경우가 해당 - 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴 봐야함
O(n log n)	- 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당 - 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘 중에서 가장 빠른 알고리즘에 해당 - 입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있으며 팀소트가 이런 로직을 가짐
O(n^2)	- 버블정렬같은 비효율적인 알고리즘이 이에 해당
O(2^n)	- 피보나치 수를 재귀로 계싼하는 알고리즘이 해당 - O(n^2)와 비교했을 때 O(2^n)이 훨씬 큼
O(n!)	- 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때 해당 - 가장 느린 알고리즘 ( 입력값이 조금만 커져도 다항 시간 내에는 계산이 어려움)

상한과 최악

- 빅오 : 상한을 의미

- 빅오메가 : 하한

- 빅세타 : 평균

 

- 상한을 최악의 경우와 혼동 X 

- 복잡한 함수를 '적당히 정확하게' 표현하는 방법

- 주어진(최선/최악/평균) 경우의 수행 시간의 상한

분할 상환 분석

- 분할 상환 분석은 빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나

- 대표적인 예로, 동적 배열이 있음

자료형

시퀀스

불변어 - 문자열, 튜플, 바이트

* 문자열은 값이 변경되는 것이 아니리 참조하는 것임

가변어 - 리스트

객체

- 파이썬은 모든 것이 객체

- 불변 객체와 가변 객체로 구분할 수 있음

클래스	설명	불변객체
bool	부울	O
int	정수	O
float	실수	O
tuple	리스트와 튜플의 차이는 불변의 여부이며 이외에는 거의 동일	O
str	문자	O
set

불변객체

- 변수를 할당하는 작업 : 해당 객체에 대해 참조를 한다라는 의미

- 예외가 없으며 문자와 숫자도 모두 객체

 

- 10을 a에 할당하고 b는 a변수를 할당함

- 만약 10이 11이 된다면 a 변수와 b변수는 모두 11로 변경 X

- 왜? 숫자와 문자는 불변 객체이므로

 

- 값을 담고 있는 변수는 사실 참조이며, 실제로 값을 갖고 있는 int와 str은 모두 불변객체임

- 이외의  불변 객체에는 tuple이 있음 - 한 번 값을 담아두면 더 이상 값을 변경 X

- 값이 변하지 않기 때문에 dict의 키나 set의 값으로 사용가능

가변객체

- 리스트

- 변수가 참조했을 때 그 변수의 값 또한 변경

비교연산자 is와 ==

- is 는 id( ) 값을 비교하는 함수

- None과 같은 경우(널로서 값 자체가 정의되어 있지 않는 경우) is로만 비교가 가능함

 

- == 는 값을 비교하는 연산자

 

if a is None:
	pass
    
a = [1,2,3]
a == a
> True

a == list(a)
>> True

a is a
>> True

a is list(a)
>>False

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

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

a is copy.deepcopy(a)
>> False

# copy.deepcopy( )로 복사한 결과 또한 값은 같지만 
# ID는 다르기 때문에 is로 비교하면 False