[자바 알고리즘 인터뷰] 5장 빅오

1. 빅오 

 

- 빅오 표기법이란 입력 크기가 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법으로, 점근적 실행 시간(Asymptotic Running Time)을 표기할 때, 가장 널리 쓰이는 수학적 표기법 중 하나이다. 

- 점근적 실행시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 lim->무한대 함수의 실행 시간 추이를 의미한다. 

 

- 시간복잡도(Time Complexity)의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)이며, 이와 같은 계산 복잡도를 표기하는 데 대표적인 방법이 바로 빅오다. 

- 빅오로 시간 복잡도를 표현할 때는 최고차 항만을 표기하며, 계수는 무시한다. 

- 시간 복잡도를 표기할 때는 구체적인 연산 횟수가 아니라 입력값에 따른 알고리즘 실행 시간의 추이만을 살피게 된다. 

 

1) O(1)

 

 - 입력값이 아무리 커도 실행시간이 일정하다. 

 

ex)

public int fn(int n) {
	return 42;
}

 

 

2) O(log n)

 

ex)

public int fn(int n) {
    while(n>1)
    	n/=2;
    return n;
}

 

- 이 함수는 n의 값을 계속해서 반으로 나누는데, 연산 횟수가 log2N의 계산결과와 동일하다. 

- 컴퓨터 과학에서는 주로 밑인 2를 생략하여 log n으로 표현한다. 

- 대표 알고리즘은  이진 검색(Binary Search)

 

3) O(n)

 

- 정확히 입력값(n)의 크기만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 

 

ex)

public int fn(int n) {
    int r = 0;
    for(int i=0; i<n; i++)
    	r++;
    return r;
}

 

- 실행 시간이 선형(Linear)으로 증가하기 때문에 O(n) 알고리즘을 선형 시간(Linear-Time) 알고리즘이라고도 한다. 

- 정렬되지 않은 리스트에서 최대값 또는 최솟값을 찾는 경우가 이에 해당됨 

 

 

4) O(n log n)

 

- 입력값만큼 순회하며 log n의 연산이 곱해진다. 

- 다음은 입력값만큼 순회하면서 각 순서에 해당하는 값을 반으로 나눠가며 연산하는 함수이다. 

 

ex)

public int fn(int n) {
    int r = n;
    for(int i=0; i<n; i++) {
    	while(n>1)
        	n/=2;
        n=r;
    }
    return r;
}

 

- 이 함수는 입력값 n의 크기만큼 순회하면서, 다시 입력값을 반으로 나눠가며 log n의 연산을 진행한다 

- 대표적인 알고리즘은 병합정렬(Merge Sort)

 

5) O(n^2)

 

- 입력값의 제곱만큼 연산한다. 

 

ex)

- 입력값을 중첩으로 반복하면서 연산하는 함수 

- n의 크기만큼 다시 n번 연산을 진행 

public int fn(int n) {
    int r =0;
    for(int i=0; i<n; i++) {
    	for(int j=0; j<n; j++) {
        	r +=j;
        }
        return r;
     }
}

 

- 버블 정렬(Bubble Sort)와 같은 비효율적인 정렬 알고리즘이 여기 해당한다. 

 

6) O(2^n)

 

- 입력값의 크기만큼 2배씩 연산한다. 

 

ex)

- 피보나치 수를 재귀로 구현한 함수 

- 이 함수는 2^n번만큼 연산을 진행한다. 

public int fn(int n) {
    if(n<=1)
    	return n;
    else
    	return fn(n-1) + fn(n-2);
}

 

 

7) O(n!)

 

- 입력값을 1씩 줄여가며 곱셈연산을 한다. 

- 다음은 입력값의 크기만큼 순회하면서, 다시 입력값을 1씩 줄여가며 재귀 호출하는 함수이다. 

 

ex)

public int fn(int n) {
	for(int i=0; i<n; i++)
    	fn(n-1);
     return n;
}

 

- 가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어렵다. 

 

 

2. 상한과 최악 

 

- 빅오 표기는 복잡한 함수 f(n)이 있을 경우, 이 함수의 실행 상한과 하한을 의미한다. 

- 즉 가장 빨리 실행될 때(하한)와 가장 늦게 실행될 때 (상한)를 뜻하며 이 중 가장 늦게 실행될 때를 빅오, 가장 빨리 실행될 때를 빅오메가, 평균적으로 빅세타로 지칭한다.