시간복잡도 이론

시간복잡도란?

 

알고리즘 선택의 기준

주어진 문제를 해결하기 위한 '연산 횟수'

일반적으로 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측

ex) 시간제한 2초라고 가정한다면 2억 번의 연산 안에 도출

 

시간 복잡도 유형

• 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타(Θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

---

public class timeComplexityEx01 {
	public static void main(String[] args) {
    	int findNumber = (int)(Math.random() * 100);
        for(int i = 0; i < 100; i++) {
        	if(i == findNumber) {
            	System.out.println(i);
                break;
            }
        }
    }
}

 

▲0~99 사이의 무작위 값을 찾아 출력하는 코드에 대한 각 시간복잡도의 연산횟수 ▼

• 빅-오메가(Ω(n)) : 1번
  • 위 for loop문에서 가장 최선인 경우는 random으로 돌린 정수 findNumber가 바로 0이 나오는 경우이다.
    즉, 1번만에 바로 찾아진다.
• 빅-세타(Θ (n)) : N/2 번
  • 랜덤값은 32, 56, 82 등이 나올수 있고 랜덤에 대한 평균값은 0~99 사이이므로 대략 50정도라고 가정할 수 있다.
    따라서 세타의 경우 N을 2로 나눈 정도가 된다.
• 빅-오(O (n)) : N번
  • 최악의 경우는 99가 나올때 이다.
    0부터 99까지 연산을 진행하고 마지막에 최종적으로 도출하게 된다.
    가장 시간이 오래 걸린다.

---

 

코딩테스트를 풀 때는 빅-오를 기준으로 푼다.

즉, 최악의 경우를 염두해 둬야 한다.

 

[빅 - 오 표기법 기준의 수행시간]

• O(1) 　　: 1회만에 도출
• O(logn)　: 바이너리서치 logn은 대략 6번만에 도출된다
  • ex) 밑이 2인 log의 log100 : 100은 2⁶ ~ 2⁷ 사이에 존재하므로 약 6이 된다.
• O(n) 　　: n이 100이면 100번의 연산으로 도출
• O(nlogn) : (병합정렬) 100log100 = 600
• O(n²)　　: (버블정렬) 100의 제곱 10,000
• O(2ⁿ)　　: 1,267,650,600,228,229,401,496,703,205,376
• O(n!)　　: 최악의 경우 100! 만에 도출
  • ex) 100일경우 100!의 경우의수를 갖는다. 

+) 시간복잡도에서 log의 밑은 2가 된다.

---

시간복잡도 활용

연습문제 - 백준 온라인 저지 2750번 (시간제한 2초)

 

N개의 수가 주어졌을 때 이를 오름차순 정렬하라.

 

[입력]

1번째 줄에 수의 개수 N은 1 <= N <= 1,000,000의 범위를 갖는다.

2번째 줄 부터는 N개의 줄에 숫자가 주어진다.

절대값이 1,000,000보다 작거나 같은 정수이며 중복되지 않는다.

 

 

[풀이 팁]

제한시간이 2초라면 2억번 이하의 연산횟수로 문제를 해결해야 한다.

문제에 주어진 시간 제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야할지 판단해야 한다.

 

연산 횟수 계산 방법

• 연산 횟수 = 알고리즘 시간 복잡도 X 데이터 크기
  • ex) 버블정렬(n²) : 100만의 제곱은 1000억이므로 2초 즉, 2억번의 연산 횟수에 부적합하다.
  • ex) 병합정렬(nlogn) : 100만log100만 약 2천만이므로 2억번의 연산 횟수에 충분하다.

 

위와 같이 시간복잡도를 통해 작성한 코드의 비효율적 logic에 대해 개선이 가능해진다.

시간 복잡도 도출 기준은 다음과 같다 (n은 100000으로 가정)

 

1. 상수는 시간 복잡도 게산에서 제외
   • 연산횟수 N) i < n loop 연산 횟수는 100000
   • 연산횟수 3N) 3개의  i < n  loop 연산 횟수는 300000
   • N 과 3N에서 상수3을 무시한다면 두 연산횟수는 N == N으로 동일해진다.
2. 반복문이 여러개일 경우 가장 많이 중첩된 반복문의 시간 복잡도가 기준이 된다.
   • 중첩 반복문의 경우 N * N => N제곱
     (만약 N * 3N인 경우에도 1번과 마찬가지로 상수를 생략하여 N제곱?)
   • [2중첩] [3중첩] [1중첩*10개]로 구성되어있다면 가장 높은 중첩문인 3중첩을 기준으로 시간복잡도를 계산(N³)

 

문제를 풀다가 '시간초과가 발생할 경우' 위에 정리한 원리를 바탕으로 문제의 원인 코드를 도출하고

해당 코드를 연산에 더욱 효율적인 구조로 수정함으로써 해결해야한다.

 

보통은 알고도 간과하는 경우가 많다.

(내가 짠 코드가 잘못인데, 알고리즘 잘못으로 오해하는 경우...)