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

아래 책을 보고 공부한 내용이다.

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기

github.com/onlybooks/algorithm-interview

빅오

 

빅오	내용
O(1)	최고의 시간복잡도, 입력이 아무리 커도 실행시간은 같음
O(log n)	이진검색
O(n)	입력갑만큼 영향을 받음, 정렬되지 않은 리스트에서 max, min찾는 등 모든 값을 한번씩 봐야하는 경우
O(n log n)	병합정렬 등과 같은 효율 좋은 정렬 알고리즘(Timsort는 O(n))
O(n^2)	버블정렬 등과 같은 비효율적인 정렬 알고리즘
O(2^n)	피보나치 재귀 계산
O(n!)	외판원 문제를 브루트 포스로 풀이, 입력 값이 조금만 커져도 터짐

선생님~ 제가 상수 시간복잡도 알고리즘을 하나 제안하려는데요~~!! 잠시 시간좀 내주세요

hcn1519.github.io/articles/2017-05/amortized_analysis

하지만 빅오는 항상 최악의 경우를 가정하고 계산하기때문에 분할상환 분석 방법이 등장했다. 해당 정의에 대해서는 아래 블로그에 굉장하게 자세하고 쉽게 설명되어있다. 

Amortized Analysis(분할상환 분석)

 

자료형

갑자기 왜 빅오 다음에 이게 있는지 잘모르겠다. 2부 뒤에 붙여야 하는것이 아닌가?.. 한번 읽어보도록하자. 뜻이 있을것이다.

파이썬은 모든 것이 객체이다..!

클래스	불변
bool	o
int	o
float	o
tuple	o
str	o
list	x
dic	x
set	x

 

• 3.7부터는 딕셔너리가 순서가 유지됨(하지만 그냥 유지가 안된다고 생각하고 진행하는 것이 안전)
  • collections.OrderDictionary() 를 사용하면 순서유지
  • collections.defaultdict() : 조회 시 항상 디폴트 값을 생성해 오류방지
  • collections.count