Do-It Algo -시간복잡도 1

본 Do-It 시리즈 포스팅은, Do-it! 알고리즘 코딩 테스트 java편을 기반으로 작성됩니다. 

1.Intro

  백앤드에서 핵심적인 MVC 나 구조적 패턴에 대한 학습은 얼추 하였으니, 이제 Algorithem 공부를 병행 해볼까 한다. 

 알고리즘에 대해서는 따로 배운적도, 공부한 적도 없기에 처음부터 공부를 시작해볼까 한다. 

 

1.시간 복잡도 

 - 알고리즘 문제를 볼 때마다 항상 이게 뭔데,,, 그래서,, 라는 느낌을 준 시간 복잡도. 오늘 개념을 잡고 간다. 

 

 1. 시간 복잡도란? 

    주어진 문제를 해결하기 위한 연산 횟수
                              = 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측
    시간 복잡도에 대한 정의 3가지 
    1). 빅-오메가( Ω(n) ) : Best Case 연산횟수 표기법
     2). 빅-세타( Θ(n)) : Average Case 연산 횟수 표기법 [보통 정도]
      3). 빅-오 ( O(n) ) : Worst Case 연산 횟수 표기 

	public static void main(String[] args) {
		//ex1. 0~99 사이의 무작위 값 출력 코드 
		int targetNum = (int)(Math.random() * 100) ;
		System.out.println(targetNum);
		for(int i =0; i<100; i++) {
			if(i == targetNum) {
				System.out.println(i);
				break;
			}
		}

   해당 코드의 시간 복잡도를 정의에 따라 표기하면 
  1. Ω(n) = 1
  2. Θ(n) = N/2
  3. O(n) = N 번이다. 
    
   음,, 아직은 잘 감이 잡히지 않는다. 직관적으로 생각해보자면
   빅-오메가 = targetNum이 0일 경우에는 1번의 수행만이 필요하다
   빅-세타 = targetNum의 범위가 1~100까지이니, 이를 Average화 하면 50이니까,,,?
   빅-오 = targetNum이 100이면, 총 100번의 연산을 해야하기 때문이라고 생각한다.
 

 

아래는 간단한 시간 복잡도 활용에 대한 예제 및 설명이다.

 

	public static void main(String[] args) {
		/** @Intro : 수 정렬하기 
		 *  Bubble Sort = O(n **2)
		 *  병합 정렬 = O(nlog n) 
		 * Ex 0. 수 정렬하기 
		 N개의 수가 주어졌을 때 이를 오름 차순 하는 정렬 프로그램 작성 
		 버블 정렬은 할 수 있겠지만,, 일단,, 천천히 개념부터 알아보자
		 
		 1. 시간 제한 2초 = 2억번 이하의 연산 횟수로 문제 해결해야 한다. 
		    =시간 복잡도의 경우, 항상 최악일 경우를 산정 => 데이터가 가장 클 때를 기준으로 작성 
		 @Tip = 연산 횟수 계산법 [ 연산횟수 = 알고리즘 시간 복잡도 * 데이터 크기]   
		 
		 2. 알고리즘 적합성 평가 
		   버블 정렬 = (1,000,000) **2 = 1,000,000,000,0000 > 2억 => 부적합 알고리즘 
		   병합 정렬 = 1,000,000 log (1,000,000) = 약 2천 < 2억 => 적합 알고리즘 
		   
		   즉 이 문제는 병합 정렬로 해결해야 한다.
		 @TIp = 데이터의 최대크기(N)를 단서로 사용하여, 사용할 알고리즘 유추  
		 * */
		/** 시간 복잡도 도출 기준 
		 *  1.상수는 시간 복잡도 계산에서 제외 
		 *  2.가장 많이 중첩된 반목문의 수행 횟수가 시간 복잡도의 기준 
		 * */
		//연산 횟수가 N인 경우
		N();
		//연산 횟수가 3N인 경우 
		ThreeN();
		
		/** 두 예제 코드의 연산 횟수는 3배가 차이남, 
		 *  But, 일반적인 코테의 경우 상수 무시 => 두 코드의 시간 복잡도는 O(n)으로 동일
		 * */

		//연산횟수 n **2 
		Npow2();
		/** 시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출 
		 * Npow2 에서는 이중 for문이 전체 코드의 시간 복잡도 기준 (해당 메소드에 더 많은 일반 포문이 있어도 시간 복잡도는 N **2로 동일)
		 *  
		 *  =>작성한 코드의 시간 복잡도 도출로 실제 코테에서 시간 초과 발생시 원인 발견 가능  
		 * */
	
	
	}
	public static void N() {
		int N = 100000;
		int cnt = 0;
		for (int i =0; i<N; i++) {
			System.out.println("연산횟수 :" + cnt++);
		}
	}
	public static void ThreeN() {
		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++);
		}
	}
	
	public static void Npow2() {
		int N = 100000;
		int cnt = 0;
		for (int i =0; i<N; i++) {
			for (int j=0; j<N; j++) {
				System.out.println("연산횟수 :" + cnt++);
			}
		}
	}