자바 알고리즘 공부 2일차(1)

📖chap2.알고리즘 분석

  오늘은 알고리즘 분석에 대해서 정리해보고자 합니다. 지금까지는 기록용으로 간단하게 정리하는 것이 목표였지만 앞으로 누군가에게 지식을 전달한다는 마음으로 친절한 말투와 설명조로 공부한 내용을 설명드릴 예정입니다!

 앞에서 List 인터페이스 구현 클래스인 ArrayList와 LinkedList는 응용프로그램에 따라 더 유용하게 사용할 수 있다고 말씀드렸습니다. 대충 두개다 실행해 보고 시간을 측정해서 어느 클래스가 더 좋은지 판별할 수도 있지만 (이러한 접근법을 Profiling이라 함) 여러 문제점이 있습니다. 일단 모두 구현해봐야하고 컴퓨터 성능에 따라 달라질 수 있기도 하고 문제크기나 입력하는 데이터에 의존해하는 경우가 발생하죠. 이러한 문제점을 활용하는 것이 바로 알고리즘 분석(analysis of algorithm)입니다. 구현하지 않아도 비교합니다.
알고리즘 분석은 몇가지 가정을 해야합니다. 간단한 알고리즘의 분석을 위한 3가지 가정입니다.
1. 컴퓨터 하드웨어의 세부사항을 다루지 않기 위해 보통 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별합니다. 그리고 각 알고리즘에 필요한 연산 수를 셉니다.
2. 입력 데이터의 세부사항을 다루지 않으려면 가장 좋은 선택으로 기대하는 입력 데이터에 평균 성능을 분석합니다. 하지만 가능하지 않을 경우에는 최악의 시나리오를 분석하기도 합니다.
3. 한 알고리즘이 작은 문제에서 좋은 성능을 보여도 큰 문제에서는 다른 알고리즘이 더 좋을 수 있다는 가능성을 배제하면 안됩니다.
이러한 가정이 들어간 분석은 간단한 알고리즘에 적합한데 간단한 알고리즘은 상수시간, 선형, 이차 이런 범주로 나눌 수 있습니다. 이 책에서는 간단한 알고리즘 예시로 선택정렬(selection sort)구현을 보여줬습니다.

import java.util.Arrays;

public class SelectionSort {
    /**
     * i와 j 위치변경
     * @param array
     * @param i
     * @param j
     */
  public static void swapElement(int[] array, int i, int j){
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
  }

    /**
     * 최솟값찾고 배열의 마지막위치로 이동
     * @param array
     * @param start
     */
  public static int indexLowest(int[] array, int start){
      int lowIndex = start;
      for(int i = start; i < array.length; i++){
          if(array[i] < array[lowIndex]){
              lowIndex = i;
          }
      }
      return lowIndex;
  }

    /**
     * 선택정렬로 요소 정렬
     * @param array
     */
  public static String selectionSort(int[] array){

      for (int i = 0; i < array.length; i++){
          int j = indexLowest(array, i);
          swapElement(array, i ,j);
      }

      return Arrays.toString(array);
  }

    public static void main(String[] args) {
      int[] sort = {5,3,6,4,8,7,1,32,23,5,12,5,14,13};


        System.out.println(selectionSort(sort));
    }
}

일단 첫번째 메서드인 swapElement에서는 배열에 있는 두 요소(i, j)의 값을 바꾸어 줍니다. 바꾸어 줄때 요소를 읽고 쓰는 것은 요소의 크기와 첫 번째 위치를 알고 있으면 한번의 연산으로 위치를 알 수 있기 때문에 상수 시간 연산의 예시이고 두번째 메서드인 indexLowest는 비교 횟수가 n-start가 되기 때문에 선형이 됩니다. 세번째 메서드인 selectionSort는 indexLowest를 n번 반복 실행하므로 수열의 합은 n(n+1)/2 가 되어서 n^2 에 비례하게 되서 이차가 됩니다. 따지고 보면 선택정렬은 이중 for문의 형태를 띄고 있는데 for문 하나가 선형이니 이중은 이차가 된다고 생각하면 좀 더 쉬울 것 같습니다.

나머지 내용은 (2)에서 찾아뵙도록 하죠.