빅오 표기법

연산 횟수를 대략적으로 표기한 것 - 함수의 상한을 의미

https://chang-aistory.tistory.com/16?category=934781

빅오표기의 성질

• $2n^2-5n+7=O(n^2),O(n^3),O(n^4),...$
• $f_1(n) = O(g_1(n)), f_2(n) = O(g_2(n))$일 경우
  1. $f_1(n)+f_2(n) = O(g_1(n)+g_2(n))=O(max(g_1(n), g_2(n)))$
  2. $f_1(n) \cdot f_2(n) = O(g_1(n)\cdot g_2(n))$

$$ O(1)<O(\log{n})<O(n)<O(n\log{n})<O(n^2)<O(n^3)<...<O(2^n) $$

빅오 이외의 표기법

1. 빅오메가 - 함수의 하한
2. 빅세타 - 함수의 평균

실무를 수행할 때에는, n≥n_0인 모든 구간에서 어떤 알고리즘이 항상 우세한 것이 아닐 경우가 많고, 구간별로 성능이 다를 때가 많기 때문에, 우리가 사용할 구간에 따라서 알고리즘을 선택해야 하겠다.

최선/평균/최악의 경우 성능

알고리즘 수행시간은 입력자료집합이 어떠냐에 따라 다를 수 있음

(예시) 순차탐색

• best case

  찾고자 하는 숫자가 맨 앞에 있는 경우 O(1)

• worst case

  찾고자하는 숫자가 맨 뒤에 있는 경우 O(n)

• average case

  각 요소들이 균일하게 탐색된다고 가정 즉, n개의 자리 각각에 찾는 숫자가 놓일 확률이 동일하다고 가정하면 (1+2+...+n)/n = (n+1)/2 → O(n)

최선의 경우는 대부분 의미가 없고, 평균같은 경우는 매 case마다의 확률과 연산 횟수를 고려해야하기 때문에 계산이 매우 어렵기 때문에