1. 어떤 알고리즘으로 풀어야 할까 ?

1. 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.

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

 

2. 실제 시간 복잡도를 정의하는 3가지 유형에는 빅-오메가 / 빅-세타 / 빅-오 가 있다.

    빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법

    빅-세타    : 보통일 때의 연산 횟수를 나타낸 표기법

    빅-오       : 최악일 때의 연산 횟수를 나타낸 표기법

 

3.  시간 복잡도를 나타내는 코드 유형의 예시

public class day1 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int findNumber = (int)(Math.random()*100);
		for(int i = 0 ; i < 100 ; i++) {
			
			if(i == findNumber) {
				System.out.println(i);
				break;
			}
		}
		
	}

}

 

위의 코드는 0~99 사이의 무작윗값을 찾아 출력하는 코드이다.

빅-오메가일 경우에는 최선의 경우를 나타내기 때문에-> 1 번

빅-세타 일 경우에는 보통의 경우를 나타내기 때문에 -> N / 2 번

빅-오 일 경우에는 최악의 경우를 나타내기 때문에   -> N번

 

 

4. 코딩테스트를 할 때는 어떤 시간 복잡도 유형을 사용해야 할까 ? -> 빅-오why?코딩테스트는 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단한다.즉, 최악일 때를 염두에 두어야한다.