[알고리즘] 빅오(Big-O) 표기법

 

What is Big-O?

알고리즘의 실제 실행 시간을 표기하는 것보다는 데이터 또는 사용자의 증가율에 따라 알고리즘의 성능을 예측하는 것이 목표

• Mathematical notation that describes algorithm efficiency
• Time & Space complexity
• Describes the growth rate of algorithms

---

용어 정리

n, m: 함수의 매개변수로 입력의 크기를 의미할 때 사용.

 

 

O(1) - const time

• 인자로 받는 데이터의 크기 상관없이 일관되게 0의 위치에 있는 값을 확인

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

 

 

O(n) - 선형 시간(linear time)

• 인자로 n개의 데이터를 받으면 n번 루프(loop)를 반복하게 된다.
• 즉, n의 크기만큼 처리 시간이 소요된다.

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

 

 

O(n^2) - 이차 시간(quadratic time)

• 인자로 n개의 데이터를 받는데 인자의 각 요소마다 n번씩 더 반복하게 된다.

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

 

 

 

O(nm) - 다항 시간(polynomial time)

• 코드가 O(n^2)이랑 비슷하다.
• n을 두 번 반복하는게 아니라, n의 요소마다 m만큼 반복하게 된다.

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

 

 

 

O(n^3) - 삼차 시간(Cubic time)

• 데이터가 늘어남에 따라 급격하게 시간도 늘어난다.

 

 

O(2^n) - exponential time

• 피보나치 수열
  • 1, 1, 2, 3, 5, 8 ..
• 매 번 함수가 호출 될 때마다 또 두 번씩 호출 된다.

F(n, r) {
    if (n <= 0) return 0;
    else if (n == 1) return r[n] = 1;
    return r[n] = F(n-1, r) + F(n-2, r);
}

 

 

 

O(m^n) - exponential time

• m개 씩 n 번 늘어날 때.

 

O(log n) - binary search

• 한 번 처리가 진행 될 때마다, 검색 해야하는 데이터 양이 절반씩 줄어드는 알고리즘

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(sqrt(n))

• 정사각형에 n을 다 채우고, 맨 위의 한 줄만 돌리는 알고리즘

 

 

확인사항

• 빅오에서는 상수는 과감하게 버린다.
  • O(2n) => O(n)
  • O(n^2 + n^2) => O(n^2)
  • 실제 알고리즘의 러닝(running) 시간을 계산하려고 만든 것이 아니다.
  • 장기적으로 데이터가 증가함에 따라 처리시간 증가율을 예측하기 위해 만든 것이다.
  • 상수는 고정되어 있기 때문에 증가하지 않아서 무시한다.

---

참고 영상

https://youtu.be/6Iq5iMCVsXA?si=kJPI10mQYvUXtj3b