[Do It!]알고리즘 코딩테스트 with JAVA - 시간복잡도

시간복잡도란?

시간복잡도란 알고리즘 선택의 기준이 되는 연산 수행 시간입니다.
주어진 문제를 해결하기 위한 연산횟수로 보통 1억번 연산에 1초의 시간이 소요됩니다.
따라 시간 제한이 2초인 문제가 있다면 2억 연산 안에 답이 나와야 한다는 뜻 입니다.
이 시간은 그럼 어떻게 표기할 수 있을까요?

시간 복잡도 표기 방법

int findNum = (int)(Math.random()*100);
for(int i=0;i<100;i++){
	if(i == findNum){
		System.out.println(i);
		break;	
	}
}

findNum 이 0 , 50, 99 인 상황을 가정해보겠습니다.

• 0 일 때 : 반복문이 i=0일 때 끝나므로 => O(1)
• 50 일 때 : 반복문이 0,1,2, ... 50 까지 가므로 => O(50) => O(2/N)
• 99 일 때 : 반복문이 0,1,2,3, ... 99 까지 가므로 -> O(100) => O(N)
  ( N이 100인 이유는 반복문 0~99 의 연산횟수 )

• 여기서, findNum이 0일 때는 최선의 상황이라고 할 수 있습니다.
  • 빅 오메가 : 최선일 때 (base case)의 연산 횟수를 나타낸 표기법 : O(1)

• 50일 때는 보통의 상황이라고 할 수 있습니다.
  • 빅 세타 : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법 : 50일 때, O(2/N)

• 99일 때는 최악의 상황이라고 할 수 있습니다.
  • 빅 오 : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법 : 99일 때, O(N)

위의 표기법 중 코딩테스트에 적용할 표기법은 ? 빅 오 입니다.
모든 TestCase에 통과하기 위해서는 최악의 상황까지 생각한 수행 시간을 계산하여 적용
하여야 하기 때문입니다

시간 복잡도 계산 규칙

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

for(int i=0;i<200;i++){
	println(i);
}
for(int j=0;j<100;j++){
	println(j);
}

• O(2N)이지만 상수항은 무시하므로 O(N)
  == O (i + j) 이지만 O(i)

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

for(int i=0;i<100;i++){
	for(int j=0;j<100;j++){
		println(i+j);
	}
}

for(int k=0;k<1000;k++){
	println(k);
}

• O(N^2 + N) 이지만 영향력이 낮은 항은 무시하므로 O(N^2)
  == O( ( i x j ) + K) 이지만 O(i x j) 로 표기

• i 와 j 의 범위가 같은 경우만 있는 것이 아니므로, O(N^2) 이 아닌 O(i * j) 로 표기
  

시간 복잡도의 필요성

1. 알맞은 알고리즘 선택 기준
2. 비효율적인 로직 찾아 효율적으로 수정