빅오(big-O) (시간복잡도)

목차

빅오

• 빅오(O, big-O)란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법입니다. 이를 이용하여 알고리즘의 실행 시간(시간복잡도)이나 메모리(공간복잡도)가 입력 크기에 따라 어떻게 변화하는지를 대략적으로 표현할 수 있습니다. 
  • 알고리즘을 평가할 때는 최악의 경우, 평균적인 경우, 최선의 경우를 고려할 수 있는데, 빅오 표기법은 주로 최악의 경우(worst-case) 시나리오에 초점을 맞춥니다.

빅오 표기법을 사용할 때의 주의 사항

• 빅오 표기법은 최악의 경우를 나타내므로, 실제 실행 시간을 정확하게 예측하지는 않습니다.
• 빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 계수는 무시합니다.
  • 예를 들어 4n^2 + 3n + 4 번만큼 계산하는 함수가 있다면 이 함수의 시간 복잡도는 최고차항인 4n^2만을 고려합니다. 이 중에서도 계수는 또 무시하고 n^2만을 고려합니다. → O(n^2)

시간복잡도의 예시

• 시간복잡도의 예시
  • O(1)
    • 상수 시간 
    • 입력 크기와 관계없이 알고리즘의 실행시간이 일정합니다.
    • ex. 배열에서 특정 인덱스 요소 접근 array[num]
  • O(logN)
    • 로그 시간
    • 입력 크기가 커질수록 실행 시간이 로그 함수의 비율로 증가합니다.
    • ex. 이진 검색(Binary search)
  • O(N)
    • 선형 시간
    • 알고리즘의 실행 시간이 입력 크기에 비례하여 증가합니다.
    • ex. 배열의 모든 요소를 순회하기
  • O(NlogN)
    • 선형 로그 시간
    • 많은 효율적인 정렬 알고리즘이 이 범주에 속합니다.
    • ex. 병합 정렬(Merge sort), 퀵 정렬(Quick sort)
  • O(N^2)
    • 제곱 시간
    • 입력 크기의 제곱에 비례하여 실행 시간이 증가합니다. 일반적으로 두개의 중첩 루프를 포함하는 알고리즘입니다.
    • ex. 버블 정렬(Bubble sort), 선택 정렬(Selection sort)

시간복잡도를 고려한 알고리즘 선택하기

• 보통 알고리즘 문제를 보면 입력값의 범위가 주어져있습니다. 이를 통해 시간복잡도를 고려해서 어떤 알고리즘을 적용해야겠다는 것을 대략적으로 알 수 있습니다.
• 파이썬의 경우 1초에 1000만번 연산합니다. 따라서 문제의 시간제한이 1초일 경우 주어진 입력값의 범위를 보고 아래와 같이 시간복잡도를 생각해 알고리즘을 선택해볼 수 있습니다.
  • 입력값의 범위가 10까지 주어진 경우 →  O(1) ~  O(n!)안에 문제를 해결해야합니다.
  • 입력값의 범위가 20까지 주어진 경우  → O(1) ~  O(2^n)안에 문제를 해결해야합니다.
  • 입력값의 범위가 200까지 주어진 경우  → O(1) ~  O(n^3)안에 문제를 해결해야합니다.
  • 입력값의 범위가 3000까지 주어진 경우  → O(1) ~  O(n^2)안에 문제를 해결해야합니다.
  • 입력값의 범위가 100만까지 주어진 경우  → O(1) ~  O(nlogn)안에 문제를 해결해야합니다.
  • 입력값의 범위가 1000만까지 주어진 경우  → O(1) ~ O(n)안에 문제를 해결해야합니다.
  • 입력값의 범위가 10억까지 주어진 경우  → O(1) ~ O(logn)안에 문제를 해결해야합니다.
• 소요 시간 : O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)  (앞으로 갈수록 효율이 더 좋습니다.)