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

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

<aside> 💡

시간 제한이 2초라는 말 = 2억 번의 연산 안에 답이 나와야 함

</aside>

빅 오메가 = 최선일 때 best case 연산 횟수

빅 세타 = 보통일 때 average case 연산 횟수

빅 오 = 최악일 때 worst case 연산 횟수

public class timeComplexityExample {
	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;
				}
		}
	}
}

코딩 테스트에서는 빅 오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다. worst case. 최악의 경우를 항상 염두에 둘 것.

<aside> 💡

log 100은 2^7=128이므로 7번의 연산 안에 찾을 수 있다는 것을 의미

</aside>

연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기

ex… 문제에서 시간 제한을 2초로 줌 → 버블 정렬의 시간 복잡도는 N^2인데 N=백만이면 2초 안에 계산 불가 → 부적합 알고리즘으로 판단

시간 복잡도 가장 많이 중첩된 반복문을 기준으로 도출함 !!

이중 for문은 일반 for문보다 시간 복잡도가 더 큼.. 그래서 일반 for문이 몇개가 있더라도 이중 for문이 있으면 이중 for문의 시간 복잡도인 N^2이 되는 것.

• 알맞은 알고리즘 선택 기준
• 비효율적인 로직 찾아서 효율적으로 바꿀 것 *****