시간복잡도

배경

코딩 테스트 공부를 하다가 시간복잡도 개념을 확실히 하기 위해 정리하였습니다.

 

본론

시간복잡도란?

 - 시간 복잡도란 알고리즘의 연산횟수를 나타내는 척도입니다.

 - 시간 복잡도는 일반적으로 최악의 경우를 나타내는 빅오 표기법을 사용합니다.
 - 빅오 표기법은 연산횟수를 다항식으로 표현하여 최고차항의 계수를 제외시켜 나타내기 때문에 반복문의 반복 횟수를 계산하면 됩니다.

 

 

tip
 - 연산 횟수는 데이터입출력(copy,move),산술연산(add,multiply),제어연산(if,while,for)이 있습니다.
 - 연산 횟수 중에서 반복문(for,while)의 반복횟수를 계산하면 빅오표기법을 간단하게 계산할 수 있습니다. 아래 예시를 보면 알 수 있습니다.

int func (int n) {
  int sum = 0;     // 대입연산 1회
  int i = 0;       // 대입연산 1회

  for(i=0; i < n; i++) {  // 반복문 n+1회
    sum += i;             // 덧셈 연산 n회
  }
  for(i=0; i < n; i++) {  // 반복문 n+1회
    sum += i;             // 덧셈 연산 n회
  }
  return sum;       // 리턴 1회
}
4n+5
최고차항은 N이기 떄문에
시간 복잡도는 O(N) 입니다.


int func (int n) {
  int sum = 0;     // 대입연산 1회
  int i = 0;       // 대입연산 1회

  for(i=0; i < n; i++) {  // 반복문 n+1회
    sum += i;             // 덧셈 연산 n회
     for(i=0; i < n; i++) {  // 반복문 n+1회
        sum += i;            // 덧셈 연산 n회
        System.out.println(sum); // 출력연산 n회
     }
  }
  return sum;       // 리턴 1회
}
(n+1+n) * (n+1+n+n) + 3
= 6n²+.....
시간 복잡도는 O(n²) 입니다.

 

다음은 선택 정렬의 시간복잡도 계산 방법이다.

package com.study.basic;

public class SelectionSort {
    public static void main(String[] args) {

        int[] array = {1,10,5,8,7,6,4,3,2,9};

        /**
         * 선택 정렬
         *  - 오름차순으로 정렬한다고 했을 때, 가장 작은 값의 인덱스를 선택해서 맨 앞에서부터 교체하며 정렬하는 방법입니다.
         *  - 메모리를 적게 사용한다는 장점이 있지만 시간복잡도가 O(N²) 빅오의 N 제곱이기 때문에 비효율적인 정렬입니다.
         */
        /**
         * 계산 방법
         * 1. 개념적으로 계산
         *  인덱스 0~9 중 가장 작은 수  => 10개 n
         *  인덱스 1~9 중 가장 작은 수  => 9개  n-1
         *  ...
         *  인덱스 8~9 중 가장 작은 수  => 2개
         *  (위와 같이 앞에서부터 정렬했을 때 맨 마지막 인덱스에 대해서 정렬하지 않아도 맨 마지막 전 인덱스까지 정렬되면 전체가 정렬된다.)
         *
         *   ====> n n-1 ... 2개 이므로 1까지 포함한다고 생각하여 계산하면 n(n+1)/2
         *   1은 포함하지 않으니 최종적으로 n(n+1)/2 -1
         *   O(N²)
         *
         * 2. 코드를 보고 직접 계산
         * 첫번째 반목분 횟수 0~8 => 9개 즉, n-1
         * 두번째 반복문 횟수
         *  1~9 => 9개 즉, n-1
         *  2~9 => 8개 즉, n-2
         *  ...
         *  9~9 => 1개
         *
         *  ===> 첫번째 반복문 횟수와 두번째 반복문 횟수를 더하면
         *  (n-1) + (n-1)n/2 = n(n+1)/2 -1
         *  O(N²)
         *
         *
         */
        int i,j,min,index,temp, arrayLength;
        arrayLength = array.length;
        int count =0;
        for(i=0; i<arrayLength-1; i++) {
            index = i;
            count++;
            for(j=i+1; j<arrayLength; j++) {
                count++;
                if (array[index] > array[j]) {
                    index = j;
                }
            }

            temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }

        System.out.println("count = " + count); // 반복문에 의해 54번 연산한다.
        // 출력
        for (i=0; i<arrayLength; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

 

 

참고
https://yoongrammer.tistory.com/79
https://pizzasheepsdev.tistory.com/3