https://www.youtube.com/watch?v=XncTU-4i1KI&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT

📌 시간복잡도란?

• 주어진 문제를 해결하기 위한 연산의 횟수
  대개 1억 번의 연산 = 1초로 간주
• 시간복잡도는 알고리즘 선택의 기준이 된다.

◾ 시간 복잡도의 유형

• 빅-오메가 : 최선일 때 연산 횟수
• 빅-세타 : 보통일 때 연산 횟수
• 빅-오 : 최악일 때 연산 횟수

예시 ) 1~100사이에 랜덤값을 선택하는 경우

	...
    
int findNum = (int) (Math.random() * 100);
for (int i=0; i<100; i++ {
	if(i==findNum){
    
     ...
     

    빅 오메가 : `i=0`인 경우 
    빅 세타 : `i=50`인 경우 (N/2)
    빅 오 : `i=99`인 경우

• 코딩테스트에서 우리가 염두해야 하는 것은 빅-오 이다.

◾ 코딩 테스트에서 어떤 시간복잡도 유형을 사용해야할까?

• 빅-오를 기준으로 수행시간을 계산하는 것이 좋다.
  왜냐하면 다양한 테스트 케이스를 수행 해 모든 케이스를 통과해야만 합격으로 판단하기 때문이다.

사진 출처 : https://github.com/zeroam/studynote/blob/master/content/%5B%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%5D%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84.md

📌 시간복잡도 활용하기

• 시간복잡도를 따질 때에는 항상 데이터의 갯수를 확인한다.

ex) 데이터의 갯수가 1,000,000개 이고 제한 시간이 2초인경우 2억번 이하의 연산 횟수로 문제를 해결해야 함.

◾ 연산 횟수 계산 방법

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

• 버블 정렬의 경우
  (1,000,000)² = 1,000,000,000,000 > 2,0000,000 → 부적합 (시간초과)

• 병합 정렬의 경우
  1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 → 적합

◾ 시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가상 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

연산횟수가 1N인 경우 연산 횟수는 O(n)개 (for문 1개)
연산횟수가 3N인 경우 연산 횟수는 O(n)개 (for문 3개)
연산 횟수가 N²인 경우 연산 횟수는 O(n²)개 (중첩 for문 1개)
→ 만약 중첩 for문 1개, 일반 for문 3개가 함께 있더라도 중첩 for문 1개를 기준으로 시간 복잡도 도출

📌 정리

시간 복잡도를 위해서 해야하는 작업

1. 알맞은 알고리즘 사용하기
2. 비효율적인 로직을 찾아 수정하기