[개념정리] Big - O 시간복잡도 표기

 

알고리즘 문제를 풀면서 언젠간 한 번쯤 마주할 시간초과를 계산해내기 위한 Big-O 표기법이다.

 

시간복잡도란

 

•  실행시간으로 알고리즘의 효율을 측정한다.
•  연산 Step 의 수

ex 1부터 N 까지 더할 때

int summ(){
    int result = 0;
    for(int i=1; i<=N; i++){
    	result += 0;
    }
    return result;
}

위와 같이 하나씩 수를 더해갈 경우에는 총 N 번 연산을 수행해야 한다.

 

따라서 T(N)=N 의 시간복잡도를 갖게 된다.

 

---

 

Big-O

 

• 시간복잡도를 나타냄에 있어, 가장 큰 영향을 미치는 항으로 시간복잡도를 나타내는 것
• O(복잡도) 로 표기한다.

ex)

 

T(n) = n^2 + 2n => O(n^2)

 

T(n) = n^4 + n^3 + n^2 + 1 => O(n^4)

 

T(n) = 5n^3 + 10n^2 => O(n^3)

 

 

---

 

Big-O 표기법의 종류

• 1
• log n
• n
• n log n
• n^2
• n^3
• 2^n

O(1) :

- 데이터의 양과 상관없이 일정한 실행시간을 가진다

- 상수그래프의 모양을 그린다.

 

O(log n) :

- 위와 같은 그래프의 모양을 보인다.

- 따라서 데이터양이 많아져도 시간이 조금씩 늘어난다.

- binary search의 시간복잡도를 이와 같이 나타낼 수 있다.

 

O(n) :

- Linear 한 그래프가 그려진다.

- 데이터 양에 시간이 정비례한다.

- for문을 통한 탐색

 

O(n log n) : 

- 데이터 양이 n배 많아진다면 실행시간은 n배보다 log n 배 더 많아진다.

- Quick sort, merge sort

 

O(n^2) :

- 데이터 양에 따라 걸리는 시간은 n의 제곱에 비례하게 된다.

- 2중 for문

- bubble sort, insertion sort

- 대개 이와 같은 경우에는 시간 초과가 발생한다.

void re(){
    for (int i=0;i<N;i++){
    	for (int j=0;j<N;j++){
        	i++;
        }
    }
}

 

O(2^n) : 

- 급격하게 복잡도가 증가한다

- 피보나치 수열이 그 예

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

 

---

 

시간복잡도 별 그래프이다.

출처 : https://www.zerocho.com/category/Algorithm/post/57ea2987fdea850015313534

성능 순서 : O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)

 

---

문제 1 : 

만약 이진트리에서 최악의 경우 시간 복잡도는?

 

 

최악의 경우에는 O(N) 의 시간 복잡도를 갖게된다.

 

문제 2 :

아래 함수의 시간복잡도는?

int summ (int n) {
    int sum =0;
    while(n>0){
    	sum += n%10;
        n /= 10;
    }
}

- O(n/10) 으로 오해할 수 있지만 계속해서 1/10 로 데이터가 줄어들어가므로 O(log n) 이다.