코테 준비하기 - 1. 시간복잡도

시간복잡도 : 문제가 해결되는 연산 횟수

• 빅-오메가 : 최선일 때(best case)의 횟수. (젤 운좋을 때)
• 빅-세타 : 보통일 때(average case). (보통의 운수일 때)
• 빅-오 : 최악일 때(worst case). (....)

public class timeComplexity {
	public static void main(String[] args) {
    	// 1~100 사이 랜던값 선택
        int findNumber = (int)(Math.random() * 100);
        for(int i = 0; i <100; i++) }
        	if(i == findNumber) {
            	System.out.println(i);
                break;
            }
        }
    }
}

위 코드에서
운이 좋은 사람은 findNumber 가 0이 나와서 for문 한번만에 찾을 수 있을 것임

• 빅-오메가 시간복잡도 = 1

운이 보통인 사람은 중간 정도에서 멈출것임

• 빅-세타 시간복잡도 = N/2

운이 최악인 사람은 for문 다돌려서 마지막 번호에서 멈출것임

• 빅-오(O(n)) 시간복잡도 = N
  

코테에선 빅오 표기법을 기준으로 계산!