BIg-O

Big-O?

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

• 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도 / 계산 복잡도),

• 공간 요구사항(공간 복잡도)이

• 어떻게 증가하는지 분류하는 데 사용된다

• 빅오는 정확한 값을 표현하는 것이 아니라 적당히 정확하게 표현하는 방식이다

• 알고리즘의 효율성 분석에 유용하다

• 보통 점근적 실행 시간 표기에 쓰인다 == 시간 복잡도를 계산할 때 big-O를 쓴다

  입력의 크기가 충분히 클 때(컴퓨터가 처리하기에도 오래 걸릴 때), 알고리즘의 효율성에 따른 수행 시간의 차이를 분석하는 것.

• 시간 복잡도를 표현할 때는 최고차항만 표시한다. 상수항도 무시한다.

  2n² + 3n + 4 => 2n² => O(n²)

알고리즘의 big-O 표기

밑으로 갈수록 시간이 오래 걸린다

1. O(1): 입력값과 무관하게 일정한 실행 시간을 유지한다.

   해시테이블의 조회 및 삽입

2. O(logn): n의 크기에 대해 시간이 크게 영향 받지 않는다.

   이진 검색

3. O(n): 입력값과 실행 시간이 비례한다. 선형 시간 알고리즘.

   정렬되지 않은 리스트에서 최댓값이나 최솟값 탐색

4. O(nlogn): 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘. 대부분의 효율 좋은 정렬 알고리즘이 이에 속한다.

5. O(n²): 비효율적인 정렬 알고리즘

   버블 정렬

6. O(2n): n² 보다 훨씬 큰 숫자이니 헷갈리지 말자.

   피보나치 수를 재귀로 계산하는 알고리즘

7. O(n!): 입력값이 조금만 커져도 굉장한 시간을 필요로 한다. 가장 느린 알고리즘.

   TSP(짧은 경로를 찾는 외판원) 문제를 brute force로 푸는 알고리즘

빅오, 빅오메가, 빅세타

• 빅오(O): 상한을 표시한다. 가장 늦게 실행될 때!
• 빅오메가(Ω): 하한을 표시한다. 가장 빨리 실행될 때!
• 빅세타(θ): 평균값을 표시한다. 실행 시간의 평균!

알고리즘은 시간과 공간의 Tradeoff