[TIL#3] Amortized Time?

Amortized Time 이란?

Amortized time 이란 시간 복잡도를 나타내는 방법 중 하나로 알고리즘이 딱 한번만 아주 나쁜 시간 복잡도를 가지지만 보통은 다른 시간 복잡도를 가질 때 쓰는 표현입니다. 좋은 예로는 ArrayList와 같이 동적으로 길이가 변하는 데이터구조가 될 수 있습니다.

ArrayList 와 Resizable Array

ArrayList<String> merge(String[] words, String[] more) {
	ArrayList<String> sentence = new ArrayList<String>();
    
    for(String w: words) sentnece.add(w);
    for(String w: more) sentence.add(w);
    return sentence;
}

Java 같은 언어에서는 기본적으로 array의 길이가 제한되어있습니다. array의 크기가 array를 만드는 순간 정해지는 것입니다. 만약 동적으로 길이를 조절할 수 있는 데이터 구조가 필요하다면ArrayList 를 사용하면 됩니다. ArrayList는 스스로 필요할 때마다 사이즈를 재조정하지만 여전히 O(1)의 시간밖에 걸리지 않습니다.

만약 N 크기의 array를 가지고 있다고 가정해봅시다. 그러면 얼마나 많은 요소들을 각각 용량이 증가할 때 복사해야할지 거꾸로 계산할 수 있습니다. 우리가 k 만큼 요소를 더할 때마다, array는 그 전의 반정도의 크기가 됩니다. 그러므로 우리는 k/2만큼을 복사를 해야 합니다.

    final capacity increase: n/2 elements to coply
    previous capacity increase : n/4 elements to copy
    previous capacity increase : n/4 elements to copy
    previous capacity increase : n/4 elements to copy
    ...
    second capacity increase : 2 elements to copy
    first capacity increase: 1 element to copy

그러므로 N만큼 요소를 더하기 위해 복사해야하는 총 수는 대략, N/2 + N/4...+2+1 입니다. 이는 대략 N보다 작습니다.

만약 이런 과정이 명확하다면, 약 1km 정도 떨어져 있는 가게를 생각해봅시다. 0.5 km를 걸어가고, 그 다음 0.25 km를 걸어가고, 그 다음은 0.125km.... 계속 반복했을 때, 절대 1km를 넘지는 않을 것입니다 (물론 수렴은 하지만)