자바로 배우는 핵심 자료구조와 알고리즘 : 2장 알고리즘 분석

그렇다면 언제 ArrayList와 LinkedList 중 어떤 것을 사용하는 것이 더 좋은 선택일까?

어떤 프로그램에 어떤 클래스를 사용하는 것이 더 좋을 지 결정할 때 두 경우의 효율성을 계산하기 위해서 두 가지 방법을 사용할 수 있다.

 

1. 프로파일링 (Profiling)

둘 다 시도해보고 각각 얼마나 걸리는 지 확인

 

단점 !

• 둘 다 구현해봐야한다.
• 결과가 사용하는 컴퓨터의 성능에 의존한다.
• 결과가 문제 크기나 입력으로 사용하는 데이터에 의존한다.

2. 알고리즘 분석 (Analysis of algoritms)

구현하지 않고 알고리즘을 비교하는 방법

 

• 첫번째 가정 - 하드웨어의 세부사항을 다루지 않기 위해 알고리즘을 이루는 기본 연산을 식별하여 알고리즘에 필요한 연산 수를 센다.
• 두번째 가정 - 입력 데이터에 의존하지 않도록 입력 데이터에 대한 평균 성능을 분석하거나 가능한한 가장 많은 데이터를 다루는 경우의 시나리오를 분석한다.
• 세번째 가정 - 작은 문제와 큰 문제에서의 알고리즘의 효율성이 달라진다. 보통 큰 문제에서 알고리즘의 차이가 극대화되기 때문에 큰 문제에 초점을 맞춰 분석한다.

간단한 알고리즘은 다음 몇 가지 범주로 나뉘게 된다.

• 상수 시간(constant time)
  실행 시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간을 따른다.
  ex) 브래킷 연산으로 배열 요소 중 하나에 접근
• 선형(linear)
  실행 시간이 입력의 크기에 비례하면 이를 선형이라고 한다.
  ex) 배열에 있는 요소를 모두 더한다면 1. n개의 요소에 접근 2. n-1번의 연산 => 2n - 1 의 연산 횟수를 갖고 결국 실행 시간은 n에 비례한다.
• 이차(quadratic)
  실행 시간이 n의 제곱에 비례하면 이를 이차라고 한다.
  ex) 배열에 있는 어떤 요소가 두번 이상 나타나는 지 알고싶다면 n개의 요소를 나머지 n-1개의 요소들과 모두 비교한다. 따라서 총 비교 횟수는 n * (n - 1) = n**2 - n 이 되어 n이 점점 커질수록 n**2에 비례하게 된다.

2.1. 선택 정렬

선택 정렬의 예시를 보자.

package com.heejin.data_structures;

public class SelectionSort {
  public static void swapElements(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
    
  }
  
  public static int indexLowest(int[] array, int start) {
    int LowIndex = start;
    for (int i = 0; i < array.length; i++) {
      if (array[i] < array[LowIndex]) {
        LowIndex = i;        
      }
    }
    return LowIndex;
  }
  
  public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
      int j = indexLowest(array, i);
      swapElements(array, i, j);
      
    }
  }
}

swapElements 메서드는 두번쨰 파라미터로 받은 인덱스의 요소와 세번째 파라미터로 받은 인덱스의 위치를 바꾼다. 인덱스의 값을 아는 상태에서 해당 인덱스에 위치하는 배열을 찾는 연산은 요소의 크기와 첫번째 위치만 알고 있다면 한번의 곱셈과 덧셈으로 충분하다. 따라서 이는 배열 크기와 전혀 상관이 없는 상수 시간 연산이다.

 

indexLowest 메서드는 start 인덱스에서 시작하여 끝 인덱스까지 가장 작은 요소를 찾는다. 반복문을 돌 때마다 두 요소에 접근 후(상수 시간 연산) 한 번의 비교 연산(상수 시간 연산)을 거친다. 두 과정 자체는 상수 시간 연산이기에 배열의 크기와는 상관없지만, 연산 횟수는 다르다. 총 비교 연산의 횟수는 n - start가 되어 이에 따라 메서드는 선형이 된다.

 

selectionSort() 메서드는 인덱스마다 한번씩 indexLowest 메서드와 swapElements를 호출하여 가장 작은 것을 찾은 후 이를 가장 앞 인덱스와 위치를 바꿔주는 방식으로 배열을 정렬하고 있다. 따라서 indexLowest와 swapElements를 배열 크기만큼 반복한다. swapElements는 상수 시간 메서드이기 때문에 무시할 수 있다. 단 indexLowest는 첫번째는 n 번 두번째는 n - 1 번 세번째는 n - 2...1번, 0번하게 되므로 총 연산 횟수는 n(n + 1) / 2이다. 따라서 해당 메서드는 n**2에 비례하는 이차 메서드가 된다.

 

 

2.2. 빅오 표기법

이와 같은 상수시간 알고리즘, 선형 알고리즘, 그리고 이차 알고리즘은 빅오 표기법으로 표현이 가능하다.

• O(1) : 상수 시간 알고리즘의 집합
• O(n) : 선형 알고리즘의 집합
• O(n**2) : 이차 알고리즘의 집합

 

이 빅오 표기법으로 알고리즘이 어떻게 동작하는지에 관한 일반적인 법칙을 표현하는 간편한 방법을 제공한다.

상수시간 알고리즘 + 선형 시간 알고리즘 -> 선형시간 알고리즘

* ∈: ~의 요소

• f ∈ O(1) &  g  ∈ O(n) => f + g ∈ O(n)
• f ∈ O(n) &  g  ∈ O(n) => f + g ∈ O(n)
• f ∈ O(n) & k는 상수 => kf ∈ O(n)
• f ∈ O(n) => nf ∈ O(n**2)

일반적으로 n의 차수가 가장 큰 것에 따라 실행 시간의 종류가 결정된다.

n**2 + 100n + 10000 도 O(n**2)이다.

 

*증가 차수(order of growth) : 실행 시간이 같은 빅오 범주에 해당하는 알고리즘 집합
ex) 모든 선형 알고리즘은 실행 시간이 O(n)에 있으므로 같은 증가 차수에 속한다.

 

2.3. 실습 2

Algorithms/ThinkDataStructures/src/main/java com.allendowney.thinkdast.MyArrayList.java
Algorithms/ThinkDataStructures/src/main/java com.allendowney.thinkdast.MyArrayListTest.java

1. 클래스 정의와 인스턴스 변수, 생성자

public class MyArrayList<T> implements List<T> {
	int size;                    // keeps track of the number of elements
	private T[] array;           // stores the elements

	@SuppressWarnings("unchecked")
	public MyArrayList() {
		// You can't instantiate an array of T[], but you can instantiate an
		// array of Object and then typecast it.  Details at
		// http://www.ibm.com/developerworks/java/library/j-jtp01255/index.html
		array = (T[]) new Object[10];
		size = 0;
	}

size 변수는 MyArrayList 클래스의 요소 개수를 추적하고, array 변수는 실제로 그 요소들을 저장하는 배열을 의미한다. 생성자는 초기값이 null이고 10개 요소를 갖는 배열을 생성하며, size 변수는 0으로 설정한다. 대부분 시간 동안 배열의 크기는 size 변수보다 크기 때문에 배열에는 사용하지 않는 항목이 있다. 

 

타입 파라미터로 배열을 초기화할 수 없기 때문에 Object 배열로 초기화하고 형변환 해야한다. 

 

2. 리스트에 요소를 추가하는 add 메서드 (내가 한 것)

	@Override
	public boolean add(T element) {
		if (size == array.length) {
		  array = Arrays.copyOf(array, array.length + array.length / 2);
		}
		array[size] = element;
		size++;
		return true;
	}

size가 array.length와 같아지는 시점 (이상으로 해도 되지만 어차피 ArrayList에 항목을 하나씩만 넣을 수 있기 때문에 length보다 커지려면 무조건 먼저 같아지는 시점을 지난다) 에는 더 큰 배열을 만들어 원래 배열을 복사해야한다. 나는 Arrays.copyOf() 메서드를 사용했다. 

 

그리고 배열에 가장 마지막 항목인 array[size - 1]보다 하나 더 뒤의 항목 array[size]에 파라미터로 받은 객체를 저장한다. 그리고 size를 하나 더 늘려준다. 리턴값은 항상 true이다.

 

이 밑에 위치한 add(int index, T element) 는 size를 늘리기 위해 똑같은 코드를 중복 작성하지 않고, 이 메서드를 호출해서 여기서 사이즈를 늘릴 수 있도록 코드를 짰다.

 

true를 항상 반환하기 때문에 왜 불리언 형을 반환하는지는 분명하지 않다. 다만 자바 API에서 확인해보니 add의 리턴값은 Collection이라는 인터페이스의 리턴값을 그대로 따르는 것이고, 이 인터페이스에 리턴이 true인 이유는 다음과 같이 적혀있다.

Returns: true if this collection changed as a result of the call

이 말은 즉슨 요청한 대로 결과가 바뀌지 않는다면 false를 리턴한다는 것일 것이다. 다만 ArrayList는 그럴 일이 없기 때문에 항상 true를 리턴하는 것일 것이다. 

(더 알게 된 바는 Set과 같은 클래스에서는 이미 해당 객체가 있을 경우 중복 추가하지 않기 때문에 false를 리턴한다고 한다.)

 

이 메서드의 성능을 분석하는 방법도 분명하지 않다. 일반적으로는 상수 시간 O(1)이지만, 배열의 크기를 변경한다면 선형시간 O(n)이 된다. 

 

3. get 메서드

	@Override
	public T get(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		}
		return array[index];
	}

인덱스가 범위를 벗어나면 예외를 던지고 아니면 배열의 요소를 읽고 그것을 반환한다. 인덱스 유효 검증 과정에서 array.length가 아니라 size보다 작은지를 검사하기 때문에 사용되지 않는 배열 항목에는 접근이 안된다.

 

4. indexOf 메서드 (내가 한 것)

	@Override
	public int indexOf(Object target) {
	  for (int i = 0; i < size; i++) {
	    if (equals(target, array[i])) {
	      return i;
	    }
	  }
		return -1;
	}

반복문을 돌려가면서 파라미터 객체와 equals메서드가 true가 되는 배열 항목의 인덱스를 리턴하는 과정이다. 그런데 중요한 점은 Object 클래스에 있는 equals 메서드를 그대로 사용한다면 equals를 호출하는 객체가 null일 경우 NullPointerException 에러가 떠버린다. 따라서 배열에 있는 항목이든, 혹은 파라미터든 null이 있더라도 에러가 뜨지 않도록 equals 메서드를 오버로딩한다. 이 메서드는 이 자바 파일에 미리 제공되어있다. 이 메서드를 그대로 사용하면 된다. 만약 배열에 아무것도 target과 같은 것이 없다면 -1을 리턴한다.

    private boolean equals(Object target, Object element) {
		if (target == null) {
			return element == null;
		} else {
			return target.equals(element);
		}
	}

이 메서드는 앞에 위치한 파라미터가 null일 경우, 앞 파라미터로 Object의 equals 메서드를 호출하는 대신, 직접 두번째 파라미터와 null을 == 연산자를 통해 비교한다. 그 외의 경우에는 Object의 equals 메서드를 사용해주면 된다.

 

5. remove 메서드 (내가 한 것)

	@Override
	public T remove(int index) {
	  get(index);
	  T old = get(index);
	  for (int i = index + 1; i < size; i++) {
	    array[i - 1] = array[i];
	  }
      array[size - 1] = null;
	  size--;
	  return old;
	}

파라미터로 받은 index에 해당하는 항목을 삭제하는 메서드이다. 본격적으로 항목을 지우기 전에 인덱스 유효 검증을 해야하는 데, get() 메서드에 유효성 검증 코드가 있고, 이것은 배열에 변화를 주지 않기 때문에 이 메서드를 호출함으로써 유효 검증을 거칠 것이다. 그리고 그 이후에는 원래 인덱스에 저장된 객체를 따로 임시 변수에 저장한다. 이후에는 지우고자하는 인덱스 바로 뒤에것부터 시작하여 가장 마지막 인덱스까지 차례로 하나씩 앞으로 옮기는 과정을 거친다. 

 

그렇게 배열을 바꾸고 나면 이제는 쓰이지 않을 가장 마지막 항목을 null로 바꿔주고 size를 하나 줄인다. 그러고 나서 원래 객체를 저장했던 임시변수 old를 리턴한다.

 

6. set 메서드 (내가 한 것)

	@Override
	public T set(int index, T element) {
	  get(index);
	  T old = array[index];
	  array[index] = element;
		return old;
	}

인덱스의 유효성 검증을 get 메서드를 호출하여 거친 후, 원래 인덱스에 저장된 객체를 임시변수에 저장한다. 그리고 그 인덱스에 파라미터 객체를 저장하고 원래 객체가 저장된 임시변수 old를 리턴한다.