pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 4장 빅오, 자료형 1) 빅오 빅오란? 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기법 = 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나 시간 복잡도(Time Complexity) = 점근적 실행 시간 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity) 빅오로 시간 복잡도를 표현할 때는 최고차항만 표기, 계수 무시 (ex) $$4n^2+3n+4 \approx O(n^2)$$ 빅오의 종류 1 O(1) 해시 테이블 상수 시간 매우 가치있음 2 O(log n) 이진 탐색 입력에 영..

상한보다 최악이 있는가 헷갈리는 부분이라 고민을 해보고 싶어서 작성한다. 먼저 시간 복잡도에서 빅오는 충분히 큰 입력을 가정하며, 입력에 대한 연산수로 알고리즘의 실행 시간을 표기하는 방법이다. 이 때 빅오는 상한, 빅오메가는 하한, 빅세타는 평균의 의미로 사용한다. 그런데 나는 상한(Upper Bound)라는 말이 왜 최악과 같지 않은지 와닿지 않았다. 위와 아래로 일정한 범위를 이루고 있을 때, 위쪽의 한계 상한의 정의는 위쪽의 한계. 이보다 더 높을 수 없기 때문에 시간을 기준으로 가장 오래걸리는 최악이다. 그런데 왜 최악과 상한을 분리시켜 봐야하는가? 그림을 그려보았다. 알고리즘에는 입력 데이터의 수, 그리고 정렬의 경우 데이터 배열에 의해 최선/최악의 연산수가 결정된다. 어떤 알고리즘의 연산수가..