>>>>>>> 소스코드.git 이중 연결 리스트 이중 연결 리스트를 구현한 MyLinkedList 클래스는 단일 연결 리스트를 사용한다. 즉, 각 요소는 다음 요소에 대한 참조만 포함하고 MyLinkedList 객체 자체는 첫 번째 노드에 대한 참조만 가지고 있다. 하지만 여기에서 LinkedList 클래스에 대한 문서를 읽어보면 다음과 같은 내용이 나온다. List와 Deque 인터페이스를 구현하는 이중 연결 리스트 구현⋯⋯ 모든 연산은 이중 연결 리스트와 같이 동작합니다. 리스트의 인덱스를 활용하는 연산은 시작 또는 끝부터 리스트를 순회합니다. 이때 어느 것이든 특정 인덱스에서 가까운 것을 선택합니다. 이중 연결 리스트를 잘 모른다면 요약한 다음 내용을 확인하자. 각 노드는 다음 노드와 이전 노드에 ..
알고리즘 & 문제/알고리즘 분석
>>>>>>> 소스코드.git 시작에 요소를 추가하는 연산은 LinkedList 클래스가 ArrayList 클래스보다 빠르다. 하지만 요소를 끝에 더하는 것은 LinkedList가 더 느리다. 여기에서는 전체 리스트를 순회하여 끝에 요소를 추가하며 선형이다. 따라서 n번 추가하는 연산의 전체 시간은 이차가 되리라 기대한다. 하지만 그렇지 않다. 소스 코드를 보자. public static void profileLinkedListAddEnd() { Timeable timeable = new Timeable() { List list; public void setup(int n) { list = new LinkedList(); } public void timeMe(int n) { for (int i = 0; ..
>>>>>>> 소스코드.git 연결 리스트에서는 기존 요소를 시프트할 필요 없이 시작에 새로운 요소를 추가할 수 있다. 따라서 LinkedList 시작에 n번 추가하는 연산의 전체 시간은 선형이다. public static void profileLinkedListAddBeginning() { Timeable timeable = new Timeable() { List list; public void setup(int n) { list = new LinkedList(); } public void timeMe(int n) { for (int i = 0; i < n; i++) { list.add(0, "a string"); } } }; int startN = 128000; int endMillis = 2000;..
>>>>>>> 소스코드.git ArrayList의 시작에 새로운 요소를 추가하는 연산의 성능을 테스트한다. 앞의 분석(ArrayListAddEnd)에 근거하여 각 메서드는 선형이여야 한다. 이는 다른 요소들을 오른쪽으로 시프트하기 때문이다. 따라서 n번 추가 연산은 이차가 된다. public static void profileArrayListAddBeginning() { Timeable timeable = new Timeable() { List list; public void setup(int n) { list = new ArrayList(); } public void timeMe(int n) { for (int i = 0; i < n; i++) { list.add(0, "a string"); } } }..
결과 해석 ArrayList 클래스의 동작 방식을 이해했으니 이를 바탕으로 add 메서드가 끝에 한 개 요소를 추가할 때 상수 시간이 걸린다는 것을 예상할 수 있다. 따라서 n개 요소를 추가하는 전체 시간은 선형이다. 이 이론을 테스트하고자 문제 크기 대비 실행시간을 그래프로 그려보고 문제 크기가 측정에 적당할 만큼 충분히 클 때 직선을 이루는지 알아보자. 수학적으로는 이 직선의 함수를 다음과 같이 구할 수 있다. 실행시간 = a + bn 여기서 a는 Y 절편이고, b는 기울기이다. 한편 add 메서드가 선형이면 n번 추가하는 전체 시간은 이차가 된다. 문제 크기 대비 실행시간을 그래프로 그리면 포물선을 예상할 수 있다. 수식은 다음과 같다. 실행시간 = a + bn + cn² 완벽한 데이터가 있다면 직..
>>>>>>> 소스코드.git 그래프를 보기 위해 Profile 클래스가 있다. 이 클래스는 문제 크기의 범위를 인자로 받아 실행하는 코드를 포함하며 실행시간을 측정하고 결과를 그래프에 출력한다. Profile 클래스를 사용하면 ArrayList와 LinkedList 클래스에 있는 add 메서드의 성능을 분류할 수 있다. 다음 코드를 보자. (ProfileListAdd.java) public static void profileArrayListAddEnd() { Timeable timeable = new Timeable() { List list; public void setup(int n) { list = new ArrayList(); } public void timeMe(int n) { for (int ..
