빅오 표기법

• 빅오 표기법은 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다.
• 알고리즘이 처리해야할 데이터의 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다.
• 알고리즘의 정확한 실행 시간을 계산하는 것에 초점을 두지 말고, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하자.

빅오 표기법 그래프

출처: 인프런 김영한님의 강의 PDF

빅오 표기법의 예시

• O(1) - 상수시간
  • 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정하다.
  • ex) 배열에서 인덱스를 사용해서 값을 가져오는 경우

• O(n) - 선형시간
  • 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.
  • ex) 배열의 검색, 배열의 모든 요소를 순회하는 경우

• O(n^2) - 제곱시간
  • 알고리즘의 실행 시간이 입력 데이터 크기의 제곱에 비례하여 증가한다.
  • n^2 는 n * n 을 뜻한다.
  • ex) 보통 이중 루프를 사용하는 알고리즘에서 나타난다.

• O(log n) - 로그시간
  • 알고리즘의 실행 시간이 데이터 크기의 로그값에 비례하여 증가한다.
  • ex) 이진 탐색

• O(n log n) - 선형 로그 시간
  • 알고리즘의 실행 시간이 데이터 크기의 n * (logn) 에 비례하여 증가한다.
  • ex) 많은 효율적인 정렬 알고리즘

• 빅오 표기법은 큰 데이터를 입력한다고 가정하고, 데이터 양 증가에 따른 성능 변화 추세를 비교하는데 사용된다.
• 정확한 성능을 측정하는 것이 목표가 아니라 매우 큰 데이터가 들어왔을때의 대략적인 추세를 비교하는 것이 목적이다.
• 따라서 데이터가 매우 많이 들어오면 추세를 보는데 상수는 여기에서 크게 의미가 없어진다.
• 위와 같은 이유로 빅오 표기법에서는 상수를 제거한다.
• ex) O(n + 2), O(n / 2) 도 모두 O(n) 으로 나타낸다.

여러가지 표기법

• 빅오 표기법은 별도의 이야기가 없으면 보통 최악의 상황을 가정해서 표기한다.
• 물론 최적, 평균, 최악의 경우로 나누어 표기하는 경우도 있다.

예시로 배열의 순차 검색의 경우를 나누어 살펴보자.

최적의 경우(빅-오메가)

• 배열의 첫 째 항목에서 원하는 값을 바로 찾으면 O(1) 이 된다.

평균의 경우(빅-세타)

• 평균적으로 보면 보통 중간쯤에서 데이터를 발견한다. O(n/2) 지만, 상수를 제외하여 O(n) 으로 표기한다.
• 최악과 비교를 위해 O(n/2) 로 표기하는 경우도 있다.

최악의 경우(빅-오)

• 마지막 항목에 있거나 항목이 없는 경우 전체 요소를 순회한다. 이 경우 O(n) 이 된다.