시간복잡도

시간복잡도란?

시간복잡도주어진 문제를 해결하기 위한 연산 횟수

 

 

빅-오메가(Big-Ω) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법

빅-세타(Big-θ) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법

빅-오(Big-O) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

코딩 테스트에서는 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로  빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음

 

 

시간복잡도 도출 기준

① 상수는 시간복잡도 계산에서 제외

② 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨

 

 

 

아래 1, 2번 예제의 연산 횟수는 3배의 차이가 나지만, 일반적으로 두 코드 모두 시간 복잡도는 O(n)으로 같음

 

1. 연산 횟수가 N인 경우

- 시간복잡도는 O(n) → 100000

public class Main {
	public static void main(String[] args) {
		int N = 100000;
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			System.out.println("연산 횟수 :" +cnt++);
		}
	}
}

 

2.연산 횟수가 3N인 경우

- 시간복잡도는 3(n)  → 300000

public class Main {
	public static void main(String[] args) {
    	int N = 100000;
        int cnt = 0;
        for(int i = 0; i < N; i++) { //100000번
        	System.out.println("연산 횟수:" + cnt++);
        }
        for(int i = 0; i < N; i++) { //100000번
        	System.out.println("연산 횟수:" + cnt++);
        }
        for(int i = 0; i < N; i++) { //100000번
        	System.out.println("연산 횟수:" + cnt++);
        }
	}
}

 

 

 

시간복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이중 for문이 전체 코드의 시간복잡도 기준이 됨

가장 많이 중첩된 for문이 기준이 됨

 

1. 연산 횟수가 N*2인 경우

public class Main {
	public static void main(String[] args) {
    	int N = 100000;
        int cnt = 0;
        for(int i = 0; i< N; i++) {
        	for(int j = 0; j < N; j++) {
            	System.out.println("연산 횟수:" + cnt++);
            }
        }
    }
}