빅-오(Big-O) 표기법

알고리즘에서 중요한 속성

• 정확성 : 주어진 입력을 모두 처리하며 올바르게 출력해야 한다.
• 효율성 : 문제를 효율적으로 해결해야 한다.

- 시간 복잡도 : 알고리즘이 얼마나 빠르게 결과를 출력하는지 측정, 입력 크기 n에 대한 시간 함수 T(n)으로 표현

- 공간 복잡도 : 원하는 결과를 얻기 위해 알고리즘이 얼마나 메모리를 사용하는지 측정, 입력 크기 n에 대한 메모리 사용 함수 S(n)으로 표현

 

알고리즘의 시간 복잡도(Time Complexity)

알고리즘의 복잡도를 판단하는 척도로는 시간 복잡도와 공간 복잡도 두 가지가 있는데, Big-O 표기법은 시간 복잡도를 다룬다. 당연하게도 알고리즘은 연산이 많아질수록 그 속도가 느리다. 따라서 시간 복잡도는 알고리즘 내 연산의 횟수와 관계가 있다.

 

점근 표기법(asymptotic notation)

알고리즘의 성능을 수학적으로 표현하는 방법이다. 즉 알고리즘의 효율성을 평가하는 수학적 도구이며 최선의 경우, 평균의 경우, 최악의 경우를 표현한다. 가장 큰 영향력이 있는 항만 표시한다는 점과 상수항은 무시한다는 특징이 있다.

 

• 빅 오 표기법 : 최악의 경우 배열의 길이만큼 걸릴 때 -> Big O: O - 상한 점근
• 빅 오메가 표기법 : 최선의 경우 한 번에 찾을 때 -> Big Omega: Ω - 하한 점근
• 빅 세타 표기법 : 평균의 경우 배열의 길이 중간만큼 걸릴 때 -> Big Theta: Θ - 상한/하한 점근

 

빅-오 표기법(Big-O notation)

프로그램은 대부분 입력값이 최선의 경우일 가능성이 적을뿐더러 항상 최악의 경우를 대비해야 하기 때문에 시간 복잡도를 확인할 때 빅오 표기법을 사용한다. 현업에서 복잡도에 대한 얘기를 나눈다면 항상 빅오 표기법을 기준으로 얘기한다고 생각하면 된다.

 

빅-오 표기법의 특징

• 상수항을 무시한다.
• 입력 크기가 클 때 계수를 무시한다.
• 가장 큰 영향력이 있는 항, 최고차 항만 표기한다.
• 지수가 아닌 수는 생략한다.

 

빅-오 표기법으로 표기하기

가장 큰 영향력이 있는 항만 남긴다.

 

Big-O Time Complexity Chart

빅-오(Big-O)의 종류와 예제

1. 상수 시간 O(1)
   입력 크기와 상관없이 고정된 시간으로 계산한다면 알고리즘이 상수 시간(constrant time)에 실행된다.
   
   - 배열의 n번째 원소에 접근
   - 스택에 push/pop
   - 큐에 삽입/삭제
   - 해시 테이블의 원소에 접근
   
   

   

2. 선형 시간 O(n)
   알고리즘의 실행 시간이 입력 크기에 정비례
   
   - 배열에서 검색, 최소/최댓값 찾기 등 연산
   - 연결 리스트에서 순회, 최소/최대값 찾기 등 연산
   
   

   

3. 로그 시간 O(log n)
   알고리즘의 실행 시간이 입력 크기의 로그에 비례
   알고리즘의 각 단계에서 입력의 상당 부분을 방문하지 않고 지나간다.
   

   

4. 선형 로그 시간 O(n log n)
   알고리즘의 실행 시간이 입력 크기와 입력 크기의 로그 곱에 비례
   이런 알고리즘은 입력의 절반(또는 일부)으로 나눌 때마다 각 부분을 독립적으로 처리
   
   - 병합 정렬(merge sort)
   - 퀵 정렬(quick sort) - 평균적인 성능, 최악의 시간 복잡도는 O(n^2)
   - 힙 정렬(heap sort)
   
   

   

5. 2차 시간 O(n^2)
   알고리즘의 실행 시간이 입력 크기의 제곱에 비례
   이런 알고리즘은 각 원소를 다른 모든 원소와 비교
   
   - 버블 정렬(bubble sort)
   - 선택 정렬(selection sort)
   - 삽입 정렬(insertion sort)
   

   

6. 지수 시간 O(2^n)
   입력 데이터들의 원소들로 만들 수 있는 모든 부분 집합을 생성
   
   
7. 계승 시간 O(n!)
   입력 데이터의 원소들로 만들 수 있는 모든 순열을 생성

 

함께 읽으면 좋은 글

O(log n) 시간 복잡도란 무엇인가?

 

참고 사이트

[알고리즘] 시간 복잡도와 Big O 표기법