시간 복잡도

---

시간복잡도란?

알고리즘에서 시간 복잡도는 문제를 해결하기 위한 연산 횟수, 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.

시간 복잡도 표기 유형

• 빅 오메가 > 최선일 때의 연산 횟수를 나타낸 표기법
• 빅 세타 > 보통일 때 연산 횟수를 나타낸 표기법
• 빅 오 > 최악일 때의 연산 횟수를 나타낸 표기법

빅 오 표기법의 성능을 비교하면 아래와 같다.

faster O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) slower

코딩테스트와 같은 알고리즘 문제를 풀이할 때는 시간 복잡도를 염두하여 풀이해야 한다.

시간 복잡도 연산 횟수 계산 방법

알고리즘 시간 복잡도 * 데이터의 크기 = 연산 횟수
Ex) 버블 정렬 알고리즘의 시간 복잡도는 O(n^2)이므로  정렬해야 하는 데이터의 크기가 1000000이라면
1000000 * 1000000 = 1000000000000

빅오 표기법의 특징

1. 상수항은 무시한다.
O(2n) -> O(n)으로 표기한다.

    public static void main(String[] args) {
    	int num = 100000;
        // 아래와 같이 중첩되지 않는 for문이 2개 있더라도 시간 복잡도는 O(2n)이 아닌 O(n)이다.
        for(int i = 0; i < num; i++) {
        	System.out.println("Count : " + i);
        }
        for(int i = 0; i < num; i++) {
        	System.out.println("Count : " + i);
        }
    }

2. 가장 시간 복잡도에 영향력이 큰 곳을 기준으로 도출한다.
O(n^2 + 2n + 1) -> O(n^2)으로 표기한다.

    public static void main(String[] args) {
    	int num = 100000;
        // 아래와 같이 중첩 for문이 시간 복잡도에 가장 영향력이 크기 때문에 시간 복잡도는 O(n^2)이다.
        for(int i = 0; i < num; i++) {
        	for(int j = 0; j < num; j++) {
            	System.out.println("Count : " + i);
            }
        }
        for(int i = 0; i < num; i++) {
        	System.out.println("Count : " + i);
        }
    }

---

What I learned?

시간 복잡도를 알 수 있다면,

1. 알고리즘 문제의 알맞은 알고리즘 선택의 기준이 된다.
   -> 예를 들어 숫자 정렬 문제의 경우 버블 정렬 알고리즘(n^2)을 사용하여 문제 해결에 실패한다면, 더 시간 복잡도가 낮은 병합 정렬 알고리즘(n log n)을 사용하여 문제를 해결할 수 있다.
2. 작성한 코드에서 시간 복잡도가 높은(비효율적인) 로직을 찾아 개선시킬 수 있다.

정보처리산업기사를 준비할 때 공부했었던 내용이지만 그 당시에는 내용을 암기하기에 급급해 제대로 머리에 흡수시키지 못했던 내용을 다시 한 번 공부해보게 되었다.

현재 코딩테스트 문제들을 하루에 몇 개씩이라도 풀어보고 있는데, 아직은 쉬운 단계,그러니까 데이터의 양이 크지 않고, 테스트 셋이 별로 없는 문제들이라 위 내용과 같이 시간 복잡도를 고려하며 풀어본 적이 없다.

앞으로 더 난이도가 있는 문제들을 풀어내기 위해 시간 복잡도를 고려하여 문제를 푸는 습관을 들여보려고 한다.