Chapter. 1 빅 오
단순히 어떤 알고리즘을 2단계 알고리즘 100단계 알고리즘이라 표기할 수 없다. 서로 간의 시간 복잡도(연산 속도)를 쉽게 소통할 목적으로 수학적 개념인 빅 오를 차용했다. 빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려해 일관성을 유지한다.
1. O(1)
"빅 오 1" 차수 1이라고도 부른다. 데이터의 크기에 상관없이 알고리즘에 필요한 단계 수가 일정하다는 의미이다.
2. 선형 검색 O(N)
데이터가 하나씩 추가될 때마다 알고리즘이 한 단계식 더 걸린다. O(N)은 데이터가 증가할수록 O(1)보다 덜 효율적인 지점에 반드시 다다른다. O(N)이 반드시 선형 검색은 아니다. 원하는 항목의 배열의 첫 단계에서 찾았다면 O(1)이라 할 수 있다. 그러나 별도 표기가 없으면 최악의 시나리오를 의미한다.
3. 이분 탐색 O(log N)
로그 시간의 연산속도라고도 말한다. 데이터가 두 배로 늘어 날 수록 한 단계 늘어나는 알고리즘이다.
logarithm은 로그의 줄임말이다. algorithm과 비슷하게 보이지만 관련이 없다.
로그는 지수와 역의 관계
은 을 줄여 쓴 것이다.
마치며
이 포스트는 도서 누구나 자료 구조와 알고리즘을 읽고 정리한 내용을 작성한 글입니다.
Action!