시간복잡도

평소에 코딩 문제를 풀 때 문제를 푸는거에 의미를 둬서 시간 복잡도는 신경을 쓰지 못하였는데 한번 알아 보았다.

시간 복잡도

• 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 수행시간은 1억번의 연산은 1초의 시간으로 간주하여 예측합니다.
  ex) 시간 제한 2초 // 2억 연산 안에 답이 나와야 함

• 빅 오메가 Ω(N): 최선일 때의 연산 횟수를 나타난 표기법

• 빅 세타 Θ(N) : 보통일 때의 연산 횟수를 나타낸 표기법

• 빅 오O(N) : 최악일 때의 연산 횟수를 나타낸 표기법

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;
        }
   	 }
    }
}

n을 100으로 생각하고 n/2 , 50 번 정도 반복해서 찾으면 세타에 해당 된다.
가장 최악일 땐 99가 나오는 것이다 다 끝까지 반복문을 돌고 찾기 때문이다.

코딩 테스트에선 가장 최악의 케이스를 염두를 해야 하기에 빅 오 표기법을 기준으로 계산하는것이 좋다
다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로 시간 복잡도를 판단할 때에는 최악일 때를 염두해야 한다.

문제 : N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.
입력 : 1번째 줄의 수의 갯수 N(1<= N < = 1,000,000)
2번째 줄부터는 N개의 줄에 숫자가 주어진다. 이 수는 절댓값이 1,000,000 보다 작거나 같은 정수다.
시간 제한이 2초
연산 횟수 계산방법 : 알고리즘 시간 복잡도 크기 * 데이터 크기
문제에서 주어진 시간 제한이 2초이므로 여산 횟수 2억 번안에 원하는 답을 구해야 합니다.

시간 복합도 도출기준

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

public class 시간복잡도_판별원리{
  public static void main(String[] args) {
  	int N = 100000;
    int cnt = 0;
    for(int i = 0; i< N; i++) {
    	System.out.println("연산 횟수 : " + cnt++);
    }
  }
}

N번 100000번 돌기 때문에 해당 코드 시간복잡도는 O(N) 이 된다.

public class 시간복잡도_판별원리{
  public static void main(String[] args) {
  	int N = 100000;
    int cnt = 0;
    for(int i = 0; i< N; i++) {
    	System.out.println("연산 횟수 : " + cnt++);
    }
      for(int i = 0; i< N; i++) {
    	System.out.println("연산 횟수 : " + cnt++);
    }
      for(int i = 0; i< N; i++) {
    	System.out.println("연산 횟수 : " + cnt++);
    }
  }
}

30만번이 돌기 떄문에 3N이지만 상수는 제외 되기 떄문에 시간복잡도는 o(N) 으로 똑같다

public class 시간복잡도_판별원리{
  public static void main(String[] args) {
  	int N = 100000;
    int cnt = 0;
    for(int i = 0; i< N; i++) {
    	for(int j = 0; j<N; j++){
    	System.out.println("연산 횟수 : " + cnt++);
    }
    }
  }
}

해당 코드는 반복문이 중첩되기 때문에 O(n2) 복잡도를 갖는다. 추가로 일반 for문이 10개 있더라도 가장많이 중첩된 반복문을 기준으로 도출하므로 O(n2)복잡도를 갖는다.
맞는 알고리즘을 짰는데 시간 초과가 나타난다면 효율적으로 짜여져 있는데 확인이 필요하다

시간복잡도 따지는 법
1. 알맞은 알고리즘 쓰기
2. 비효율 적인 로직 찾아서 효율적으로 바꾸기