1.핵심이론 , 시간복잡도

시간복잡도는 알고리즘 선택에 기준이 된다.

 

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

수행시간은 1억번 연산을 1초로 간주하고 예측한다.

 

시간복잡도의 유형 3가지

1.빅오메가 , 경우의 수가 최선일때의 연산횟수를 나타낸 표기법

2.빅 세타 , 경우의 수가 보통일때의 연산횟수를 나타낸 표기법

3.빅 오 , 경우의 수가 최악일때 연산횟수를 나타낸 표기법

 

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

public class example1{

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;

}

}

}

}

 

위 문제에서 각 시간복잡도는

1.빅 오메가 (최선) 은 값이 바로 0이나와서 1번만 연산을 하는 경우

2.빅 세타 (보통) 은 제시된 값 0~99의 평균값 만큼을 연산하는 경우

3.빅 오(최악) 은 연산이 마지막까지 진행된 경우

 

코딩 테스트 때에는 항상 빅 오(최악)의 염두하고 코드를 작성해야 한다.