[Java/알고리즘] 알고리즘과 시간 복잡도 / 로직 개선하기

* 알고리즘에서의 시간 복잡도 : 연산 횟수

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

* 시간 복잡도 유형
빅-오메가(Ω(n)) : 최선일 때의 연산 횟수 표기법(Best case)
빅-세타(Θ(n) : 보통일 때의 연산 횟수 표기법(Average case)
빅-오(O(n)) : 최악일 때의 연산 횟수 표기법(Worst case)

* 시간 복잡도 예제 코드

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

 

빅-오메가 표기법 시간 복잡도 : 1

빅-세타 표기법의 시간 복잡도 : N/2

빅-오 표기법의 시간 복잡도 : N

 

코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.

실제 테스트에서는 1개의 테스트 케이스가 아니라 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야 한다.

 

---

* 로직 개선하기

시간 복잡도 도출 기준은 다음과 같다.

1) 상수는 시간 복잡도 계산에서 제외한다.

2) 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

- 상수 제외 예시

for문을 한 번만 사용하여 연산 횟수가 N인 경우와 for문을 두 번 사용하여 연산 횟수가 2N인 경우

큰 차이인것 같지만 일반적으로 상수는 무시하여 시간 복잡도는 O(n)으로 같다.

 

- 중첩 반복문 예시

이중 for문 을 사용하여 연산 횟수가 N²인 경우

일반 for문이 여러개 더 있다고 해도 중첩된 반복문의 횟수를 기준으로 도출하므로 시간 복잡도는 N²으로 같다.