[알고리즘] 알고리즘의 시간 복잡도를 표현하는 빅오 표기법 (Big O)

빅오(Big O) 란?

알고리즘에서 '시간 복잡도'란 주어진 문제를 해결하기 위한 연산 횟수를 말한다.

빅오는 이 시간 복잡도를 정의하여 표현하는 방법 중 하나이며, 최악(worst case)일 때 연산 횟수를 나타내는 표기법이다.

 

*빅-오메가 : 최선(best case)일 때 연산 횟수를 나타내는 표기법

*빅-세타 : 보통(average case)일 때 연산 횟수를 나타내는 표기법

 

빅오 차수

n : 입력 데이터의 크기

O : 차수 또는 대략의 차수

알고리즘의 시간복잡도에 따라 아래와 같이 표기할 수 있다.

• O(1), 상수 시간 (가장 낮은 차수)
• O(log n), 로그 시간
• O(n), 선형 시간
• O(n log n), 선형로그 시간
• O(n^2), 다항 시간
• O(2^n), 지수 시간
• O(n!), 팩토리얼 시간 (가장 높은 차수)

 

위 예시들을 쉽고 간단하게! 표현해보자면,

• O(1)과 O(log n) 알고리즘은 빠르다.
• O(n)과 O(n log n) 알고리즘은 나쁘지 않은 편이다.
• O(n^2), O(2^n), O(n!) 알고리즘은 느리다.

정도로 표현할 수 있다.

(물론 반례가 있을 수 있다.)

 

예시를 통해 이해하기

각각의 예시를 통해 빅오 차수를 이해해 보자.

 

상수 시간 O(1)

• ex. 책장이 비어있는가?
  • 한번 보기만 하면 바로 알 수 있는 것

로그 시간 O(log n)

• 프로그래밍 분야에서는 대체로 로그의 밑을 2로 가정하는 경우가 많기 때문에, O(log2n) 대신 O(log n)을 쓴다.
• ex. 가나다 순으로 정렬된 책장에서 책A를 찾는 작업
  • 책장 정중앙에 꽂힌 책을 확인한다. → 아니라면, 그 책 앞에 꽂혀있는지 뒤쪽인지 판단한다. → 확인해야 하는 범위를 절반으로 줄여가면서 책을 확인한다.

선형 시간 O(n)

• ex. 책장에 꽂힌 책을 모두 읽는다.
  • n개를 모두 확인한다는 의미이므로, O(n)의 시간이 걸린다.

선형로그 시간 O(n log n)

• O(log n)이 걸리는 작업을 n번 수행하는 상황
• ex. 책들을 가나다 순으로 정렬하는 작업
  • 책 한 권이 책장에 어느 위치에 꽂혀야 하는지 O(log n)의 시간이 걸린다.
  • 책이 n권 있으므로, n번을 반복한다.

다항 시간 O(n^2)

• ex. 정렬되지 않은 책장에서 중복된 책이 있는지 확인하는 작업
  • 책이 100권이 있는 경우, 각각의 책을 나머지 99권과 비교한다.
  • 한 권당 99번의 비교를 수행하며, 이를 100번 반복한다.
• 현업에서..
  • O(n log n) 또는 O(n) 알고리즘이 존재하는데도, O(n^2) 알고리즘을 부주의하게 구현하는 상황을 피하기 위해 빅오 분석을 사용하면 좋다.

지수 시간 O(2^n)

• ex. 책장의 사진을 찍을 때, 가능한 모든 책의 조합을 담아 찍는 작업
  • 1권 : {}, {a} → 2^1
  • 2권 : {}, {a}, {b}, {a,b} → 2^2
  • 3권 : {}, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c} → 2^3
• 지수 작업의 실행 시간은 매우 빠르게 증가한다.
  • ex. 책 6권은 O(2^6), 32개의 조합이 만들어진다.
  • ex. 책 32권은 O(2^32), 약 42억개 이상의 조합이 만들어진다.

팩토리얼 시간 O(n!)

• ex. 책 n권으로 배치 가능한 모든 순서
  • 첫번째 위치에 놓는 경우의 수 : n
  • 두 번째 위치에 놓은 경우의 수 : n-1 ..
  • 마지막 위치에 놓는 경우의 수 : 1 ⇒ n * n-1 * … * 1
• 잘 알려진 예시
  • 외판원 문제
    • n개의 도시를 방문하며, 가능한 모든 N! 순서에 대해 이동 거리를 계산하는 상황
    • 가장 짧은 이동 거리를 찾을 수 있다.

 

앞으로

알고리즘을 공부하고 문제들을 풀어보면서 각 해결 방법의 시간복잡도를 정의하고

더 나은 알고리즘이 없는지, 더 빠른 방법이 없는지 고민하는 시간을 가져보려고 한다.

 

현업에서 일을 하다 보면

빠르게 문제를 해결해야 하고, 빠르게 서비스 개발을 진행해야 될 때가 있는데

간혹 시간이 오래 걸리고, 높은 시간 복잡도를 가지는 코드를 작성하게 될 때가 있는 것 같다.

그래서 개인 공부로 알고리즘을 꾸준히 공부를 하며 이러한 부분에 대해 고민하는 습관을 들이려고 한다.

 

현업에서 일하시는 모든 개발자 분들, 화이팅 ! 😎