프로파일 - ArrayListAddEnd 2

결과 해석

ArrayList 클래스의 동작 방식을 이해했으니 이를 바탕으로 add 메서드가 끝에 한 개 요소를 추가할 때 상수 시간이 걸린다는 것을 예상할 수 있다. 따라서 n개 요소를 추가하는 전체 시간은 선형이다.

 

이 이론을 테스트하고자 문제 크기 대비 실행시간을 그래프로 그려보고 문제 크기가 측정에 적당할 만큼 충분히 클 때 직선을 이루는지 알아보자. 수학적으로는 이 직선의 함수를 다음과 같이 구할 수 있다.

 

실행시간 = a + bn

 

여기서 a는 Y 절편이고, b는 기울기이다.

 

한편 add 메서드가 선형이면 n번 추가하는 전체 시간은 이차가 된다. 문제 크기 대비 실행시간을 그래프로 그리면 포물선을 예상할 수 있다. 수식은 다음과 같다.

 

실행시간 = a + bn + cn²

 

완벽한 데이터가 있다면 직선과 포물선의 차이를 분명하게 보여주지만, 측정에 잡음이 많으면 구별하기 어려울 수 있다. 잡음이 많은 측정을 해석하는 좋은 방법은 log - log 스케일(log-log scale)로 실행시간 대비 문제 크기의 그래프를 그리는 것이다.

 

왜 그럴까? 실행시간이 nᴷ에 비례하지만, 지수 k가 무엇인지 모른다고 가정해 보자. 그러면 이 관계는 다음과 같이 적을 수 있다.

 

실행시간 = a + bn + … + cnᴷ

 

큰 수인 n에 대해 가장 큰 지수의 항이 가장 중요하므로 다음과 같이 나타낼 수 있다.

 

실행시간  ≈ cnᴷ

 

여기서 ≈은 '근사적으로 같음'을 의미한다. 자, 이 방정식의 양측에 로그 함수를 적용한다.

 

log(실행시간) ≈ log(c) + klog(n)

 

이 식은 log-log 스케일로 n에 대해 실행시간의 그래프를 그리면 절편 log(c)와 기울기 k를 갖는 직선을 볼 수 있음을 의미한다. 절편은 신경쓰지 않아도 되지만, 기울기는 증가 차수를 의미한다. 즉, k가 1이면 알고리즘은 선형이고, k가 2면 이차가 된다.

 

위의 그림을 보면 기울기를 눈으로 가늠할 수 있었다. 하지만 plotResults 메서드를 실행하면 데이터에 적합한 최소제곱(least squares)을 계산하고 추정 기울기(estimated slop)를 출력한다.

 

기울기 = 0.8170538245051164

 

앞의 값은 1에 가까운데, 이는 n번 추가하는 총 시간이 선형임을 의미한다. 따라서 한 번 추가하는 시간은 예상대로 상수 시간이 된다.

한 가지 중요한 점은 이와 같은 그래프에서 직선을 본다고 해서 알고리즘이 선형이라는 의미는 아니라는 점이다. 실행시간이 nᴷ에 비례한다면 기울기 k의 직선을 보게 된다. 기울기가 1에 가까우면 알고리즘은 선형이고, 2에 가까우면 이차로 봐야한다.