Big-O 표기법이란?

참고 영상

 

Big-O는 알고리즘의 성능을 수학적으로 표현해주는 표기법.

이걸로 알고리즘의 시간과 공간 복잡도를 표현할 수 있음.

 

쉽게 말해 빅오 표기법은 "입력 데이터가 엄청나게 커질 때, 이 프로그램이 얼마나 느려질까?"를 표현한 성능 성적표

 

대표적인 빅오 표기법 (빠른 순서대로)

• O(1) (상수 시간): 데이터가 1개든 1억 개든 항상 같은 시간이 걸림. 
  
  • 예시: 배열에서 5번째 값을 바로 꺼내올 때 (arr[4])

F(int[] n) 
{
	return (n[0] == 0) ? true : false;
}

 

첫번째 배열방의 값이 0인지만 확인하는 코드이기 때문에  인자가 받는 배열방의 크기가 얼마인지와 상관없이 언제나 일정한 속도로 결과를 반환함. 

 

-> 이런 걸 보고 O(1)의 시간 복잡도를 가진다고 표현함. 

 

• O(log N) (로그 시간): 데이터가 늘어나도 시간이 아주 천천히 늘어남. '업다운 게임'처럼 매번 탐색 범위를 절반씩 쪼개며 찾는 방식.
  • 예시: 정렬된 사전에서 단어 찾기 (이진 탐색)

ex) 일렬로 정렬된 array {1,2,3,4,5,6,7,8,9} 안에서 key 값이 6인 걸 찾는다고 할 때, 정렬이 되어있으니까 이진 검색을 하려면 가운데 값(5)를 찾아서 key값과 비교. key값이 더 크니까 오른쪽에 있다는 뜻 -> 1~5까지는 안 봐도 됨. -> 뒷쪽의 데이터의 중간값 (7)과 key값을 비교 -> key값이 더 작으니 앞쪽에 있다는 뜻 -> 원하는 데이터 찾음

 

한 번 처리가 진행될 때마다 검색해야하는 데이터의 양이 절반씩 떨어짐! 이걸 O(log n) 알고리즘이라고 함.

F(k,arr,s,e)
{
	if(s > e) return -1;
    m = (s + e) / 2;
    if (arr[m] == k) return m;
    else if (arr[m] > k) return F(k,arr,s,m-1);
    else return F(k,arr,m+1,e);
}

 

 

• O(N) (선형 시간): 데이터 개수에 정확히 비례해서 시간이 늘어남. 100개면 100번, 1억 개면 1억 번 확인함.
  • 예시: for문 하나로 처음부터 끝까지 쭉 훑어보기

F(int[] n) 
{
	for i = 0 to n.length
    print i
}

 

위 함수는 n개의 데이터를 받으면 n번 루프를 돎. -> n이 하나 늘어날 때마다 루프가 하나씩 늘어남 -> 결국 n의 크기만큼 처리 시간이 걸리는 셈!

 

• O(N log N) (선형 로그 시간): O(N)보다는 느리지만, 효율적인 프로그래밍의 마지노선으로 불림.
  • 예시: 데이터를 크기순으로 빠르게 정렬할 때 (병합 정렬, 퀵 정렬)

C++에서 흔히 사용하는 std::sort 같은 기본 정렬 함수들이 모두 이 O(N \log N)의 속도로 작동함.

이 개념을 이해하려면 수식을 두 개로 쪼개서 보는 것이 쉬움

O(N log N) = O(N) (전부 훑어보기) X O(log N) (반씩 쪼개기)

 

🥊 O(N^2) 방식 (무식한 리그전)

• 100명이 자기 빼고 나머지 99명과 일일이 다 한 번씩 싸워봅니다.
• 전체 경기 수는 약 10,000번이 됩니다. 시간도 엄청나게 오래 걸리고 선수들도 지치겠죠? 코딩 테스트에서 이러면 '시간 초과'로 탈락합니다.

🏆 O(N log N) 방식 (똑똑한 토너먼트전)

• 무작정 다 싸우게 하지 않고, 일단 그룹을 반씩 쪼개서 작은 토너먼트부터 시킵니다.
• 2명씩 짝지어서 싸우게 하고, 이긴 사람과 진 사람을 정렬합니다. 그다음엔 4명 그룹을 만들고, 8명 그룹을 만들며 위로 합쳐 올라갑니다.
• 이렇게 "반씩 쪼갠 다음, 정렬하면서 다시 합치는" 방식을 쓰면 전체 경기 수가 약 700번으로 확 줄어듭니다.

1단계: 완전히 혼자가 될 때까지 쪼개기 (분할)

우선 이들을 모두 1명짜리 그룹으로 뿔뿔이 흩어놓습니다.

• 현재 상태: [40] [10] [30] [20]

2단계: 2명씩 짝지어서 정렬하기 (1차 병합)

이제 옆에 있는 사람과 딱 1번만 싸워서(비교해서) 2명짜리 그룹을 만듭니다.

• A와 B가 싸웁니다 (40 vs 10): B가 약하니까 앞에 섭니다. $\rightarrow$ [10, 40] 그룹 완성
• C와 D가 싸웁니다 (30 vs 20): D가 약하니까 앞에 섭니다. $\rightarrow$ [20, 30] 그룹 완성

3단계: 4명 그룹으로 합치기 (2차 병합) - 핵심 포인트 🌟

이제 [10, 40] 그룹과 [20, 30] 그룹을 하나로 합쳐야 합니다. 여기서 무식하게 $O(N^2)$처럼 처음부터 다 다시 싸우게 하지 않습니다. 각 그룹의 맨 앞에 있는 사람(가장 약한 사람)끼리만 대결을 시킵니다.

1. 각 그룹의 1등 출전: 10 vs 20이 대결합니다. $\rightarrow$ 10이 더 약하므로 최종 그룹의 1번 자리에 들어갑니다. (현재 정렬: [10])
2. 다음 타자 출전: 첫 번째 그룹에선 10이 나갔으니 다음 타자인 40이 나옵니다. 두 번째 그룹은 여전히 20이 대기 중입니다.
3. 다시 대결: 40 vs 20이 대결합니다. $\rightarrow$ 20이 이겼으므로 최종 그룹의 2번 자리에 들어갑니다. (현재 정렬: [10, 20])
4. 다음 타자 출전: 두 번째 그룹에서 20이 나갔으니 30이 나옵니다.
5. 다시 대결: 40 vs 30이 대결합니다. $\rightarrow$ 30이 이겼으므로 3번 자리에 들어갑니다. (현재 정렬: [10, 20, 30])
6. 남은 40이 마지막 자리에 들어갑니다. (최종 정렬: [10, 20, 30, 40])

 

• O(N^2) (2차 시간): 데이터가 늘어나면 시간이 기하급수적으로 폭발하여 느려짐. 코딩 테스트에서 무심코 쓰면 '시간 초과'가 나는 주범.
  • 예시: for문 안에 for문이 있는 이중 루프

F(int[] n) 
{
	for i = 0 to n.length
    for j = 0 to n.length
    print i + j;
}

 

n으로 루프를 돌리면서 그 안에서 n으로 루프를 또 돌리는 구조! 

 

 

 

 

 

---

<추가>

• O(N x M) (다중 선형 시간 / 두 독립 변수의 곱): O(N^2)과 이중 루프를 쓴다는 점은 같지만, 출처와 크기가 서로 다른 두 개의 독립적인 데이터 그룹을 서로 모두 짝지어서 처리할 때 걸리는 시간임.
  • 예시: 내 가방에 있는 아이템 N개와 상점에서 파는 아이템 M개를 각각 한 번씩 모두 비교해 볼 때 (길이가 서로 다른 두 데이터 리스트에 대한 이중 for문)

F(int[] n, int[] m) 
{
	for i = 0 to n.length
    for j = 0 to m.length
    print i + j;
}

 

 

m을 n만큼 돌리는 것. m이 아주 작은 숫자일 수도, 큰 숫자일 수도 있기 때문에 n제곱이랑 분명하게 다른 거임!

O(n^3)

O(2^n)

O(m^n)

O(sqrt(n))