시간 복잡도, 빅 오 표기법

시간 복잡도 : 서로 다른 알고리즘의 효율성을 비교할 때 사용.

 

 

시간 복잡도의 규칙 5가지

 

1. 입력값(n)은 항상 0보다 크다

: 입력값은 음수일 수 없음

2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 된다

3. 시간 복잡도에서는 모든 상수를 삭제한다

ex. 복잡도가 2n인 알고리즘이 있다면 상수 2는 고려하지 않고 복잡도를 n으로 본다

4. 낮은 차수의 항들은 무시한다

ex. 시간 복잡도가 n, n^2이 있을 경우, n^2가 더 오래 걸리는 알고리즘이라고 판단하여 n은 무시

: 그래프의 (1, 1) 지점 전까지는 n이 더 오래 걸릴 수 있으나 알고리즘에서는 입력값 n이 1보다 작은 값이 아닌 무한으로 커진 경우를 가정하여 비교한다.

5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시한다

: 모든 로그는 서로 배수 관계이므로 밑은 고려하지 않아도 된다.

ex. 복잡도가 log인 알고리즘은 보통 무언가를 반으로 나누거나 2를 곱한 경우에 자주 사용됨.

그래서 for문 반복으로 무언가를 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그가 됨. 

만약 10으로 나누거나 10을 곱하게 되면 밑이 10인 로그가 될 것임. 하지만 시간 복잡도를 표시할 때는 밑은 무시하고

심플하게 log n 복잡도를 가진다고 표현함

6. 등호를 사용하여 표현한다.

ex. 2n = O(n),  2n ∈ O(n)

2n은 O(n)과 같다고 보며, O(n)은 2n이 어떤 함수의 집합에 속한다는 걸 의미하기도 함

 

 

 

빅 오 표기법 : 알고리즘 간의 관계를 수학적으로 표현하는 표기법

시간, 공간 복잡도 표기 가능.

실제 러닝 타임을 표시한다기보단 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 게 목표이기 때문에 상수와 같은 숫자는 모두 1로 여김

 

- O (빅 오 복잡도) 

: 비교 대상인 그래프가 일치 혹은 아래에 있을 때 비교 대상인 다른 알고리즘과 같거나 더 빠르다.

- o (리틀 오 복잡도)

: 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.

- θ (세타 복잡도)

: 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.
- Ω (빅 오메가 복잡도) 

: 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.

- ω (리틀 오메가 복잡도) 

: 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.

시간 공간 복잡도 표현 가능

 

대표적인 알고리즘의 빅 오 표기법

O(1) 알고리즘
: 인자로 받는 n이 얼마나 크든 언제나 일정한 속도로 결과를 반환

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

O(n) 알고리즘
입력 데이터 n을 받으면 n의 크기만큼 비례하여 처리 시간이 늘어남

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

O(n^2) 알고리즘
이중포문처럼 n번 도는데 그 안에서 또 n번씩 도는 것
그래프로 그리면 그래프가 일정하게 늘어나다가 어느순간부터 수직상승함

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

O(nm) 알고리즘
n스퀘어(= O(n^2)) 와는 다름

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

O(n^3)
n의 제곱 때는 면적이 되는데 n의 세제곱에는 큐빅이 됨!
그래프는 n의 제곱 때보다 처리시간이 더 급격히 늘어남

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

O(2^n)
피보나치 수열 같은 느낌
1, 1, 2, 3, 5, 8, 13... (앞의 숫자 두 개 더하는 게 다음 숫자)

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)
m을 n만큼 처리함

O(log n)
대표적인 것 이진검색
(반씩 덜어내며 키 값을 찾는 것)
O(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(sqrt(n))

정사각형에 n만큼 다 채워서 맨 위의 한 줄만 돌리는 알고리즘을 말한다

 

 

 

 

 

참고

https://www.youtube.com/watch?v=zgCnMvvw6Oo&list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk

https://www.youtube.com/watch?v=6Iq5iMCVsXA&t=313s