•
LinkedList와 ArrayList 중 무엇이 더 적합한지는 응용에 따라 다름
•
어떤 응용에 어느 클래스가 더 좋을지 결정하는 방법 중 하나는 둘 다 시도해 보고 각각 얼마나 걸리는지 알아보는 것 ⇒ 프로파일링(profiling) 접근법
•
하지만 여기는 몇 가지 문제점이 있음
1.
알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야함
2.
결과는 사용하는 컴퓨터의 성능에 의존함. 한 알고리즘이 어떤 컴퓨터에서는 더 좋을 수 있지만, 다른 알고리즘은 다른 컴퓨터에서 더 좋을 수도 있음
3.
결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도함
•
알고리즘 분석(analysis of algorithm)을 사용하여 이러한 문제를 해결할 수 있음
•
알고리즘 분석은 직접 구현하지 않고 알고리즘을 비교할 수 있지만, 몇 가지 가정을 전제로 해야함
1.
컴퓨터 하드웨어의 세부사항을 다루지 않기 위해 보통 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별합니다. 그리고 각 알고리즘에 필요한 연산 수를 셉니다.
2.
입력 데이터의 세부사항을 다루지 않으려면 가장 좋은 선택은 기대하는 입력 데이터에 대한 평균 성능을 분석하는 것입니다. 이것이 가능하지 않을 때는 일반적인 대안으로 최악의 시나리오를 분석하기도 합니다.
3.
한 알고리즘이 작은 문제에서는 최상의 성능을 보이지만 큰 문제에서는 다른 알고리즘이 더 좋을 수 있다는 가능성을 배제하면 안됩니다. 이때는 보통 큰 문제에 초점을 맞춥니다. 작은 문제에서는 알고리즘의 차이가 크지 않지만, 큰 문제에서는 그 차이가 훨씬 거대해질 수 있기 때문입니다.
대부분의 간단한 알고리즘은 아래의 범주로 나뉨
•
상수 시간
◦
실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간(constant time)을 따름
◦
Ex) 개의 배열에서 브래킷 연산([ ])을 사용하여 요소 중 하나에 접근할 때,
이 연산은 배열의 크기와 관계없이 같은 수의 동작을 수행함
•
선형
◦
실행시간이 입력의 크기()에 비례하면 알고리즘은 선형(linear)이라고 함
◦
Ex) 배열에 있는 요소를 더한다면 개 요소에 접근하여 번 더하기 연산을 해야함
연산(요소 접근과 더하기)의 총 회수는 이고 에 비례함
•
이차
◦
실행시간이 에 비례하면 알고리즘은 이차(quadratic)라고함
◦
Ex) 리스트에 있는 어떤 요소가 두 번 이상 나타나는지를 알고 싶다고 가정했을 때, 간단한 알고리즘은 각 요소를 다른 모든 요소와 비교하는 것
개의 요소가 있고 각각 개의 다른 요소와 비교하면 총 비교 횟수는 이 되어 이 커지면서 에 비례하게 됨
2.1 선택 정렬
아래의 SelectionSort는 선택 정렬(selection sort) 알고리즘을 구현한 클래스임
•
swapElements 메서드에 있는 모든 연산은 상수시간임
•
indexLowest 메서드는 만큼 비교하므로 선형임
•
selectionSort 메서드는 0에서 까지 반복하므로 번 반복함
◦
내부적으로 indexLowest를 호출하기 때문에 총 비교 횟수는 n +n-1 +n-2 +...+1 +0
◦
위 수열의 합은 이며 즉, 에 비례함
◦
selectionSort 메서드는 이차임
