순수나라

이중 연결 리스트성능 프로파일 결과추정 기울기?문제 크기와 실행시간 사이 관계의 지수 앞자리를 의미예ArrayList의 끝에 요소를 더하는 add 메서드를 사용하였을 때 n번 추가 연산의 전체 시간은 n에 비례추정 기울기 : 1에 가까움n번 추가 연산은 O(n)ArrayList의 시작에 새로운 요소를 추가하는 연산의문제 크기 대비 실행시간 그래프 이 그래프에서 직선은 알고리즘이 선형임을 의미하지 않음실행시간이 어떤 지수 k에 대해 n^k에 비례한다면 결과 그래프는 기울기 k인 직선이 됨n번 추가하는 연산의 전체 시간이 n^2에 비례하므로 직선의 기울기는 2가 됨사실, 추정 기울기는 1.992인데, 데이터를 조작한 것처럼 너무나 정답에 가까움LinkedList 메서드 프로파일하기LinkedList 시작에 ..

LinkedList 클래스MyLinkedList 메서드 분류하기indexOf 메서드 구현public int indexOf(Object object) { Node node = head; for (int i = 0; i 보통 다음 Node가 null이 아닌지 확인해야 하지만, 이 경우에는 리스트 끝까지 가면 반복문이 종료되므로 안전size 변수는 리스트의 실제 노드 개수와 일치한다고 가정이 메서드의 증가 차수는?반복마다 상수 시간인 equals 메서드를 호출함이 메서드는 target이나 data의 크기에는 의존하지만, 리스트의 크기에는 의존하지 않음반복문의 다른 연산 또한 상수 시간반복은 n번 실행됨. 운이 없으면 전체 리스트를 순회할 수도 있기 때문=> 이 메서드의 실행시간은 리스트의 크기에 비..

ArrayList 클래스MyArrayList 메서드 분류하기get 메서드 구현public E get(int index) { if (index = size) { throw new IndexOutOfBoundsException(); } return array[index];}get 메서드에 있는 모든 것은 상수 시간 => get 메서드는 상수 시간set 메서드 구현public E set(int index, E element) { E old = get(index); array[index] = element; return old;}set 메서드는 인덱스가 유효하지 않으면 예외를 던지는 get 메서드를 호출get 메서드 호출을 포함한 set 메서드의 모든 것은 상수 시간 => set 메서드는 상수 ..

알고리즘 분석프로파일링이란?어떤 응용 프로그램에 어느 클래스가 더 좋을지 결정하는 한 가지 방법은 둘 다 시도해 보고 각각 얼마나 걸리는지 알아보는 것문제점알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야 함결과는 사용하는 컴퓨터의 성능에 의존함한 알고리즘이 어떤 컴퓨터에서는 더 좋을 수 있지만, 다른 알고리즘은 다른 컴퓨터에서 더 좋을 수도 있음결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 함알고리즘 분석을 사용하면 이런 문제점을 해결할 수 있음컴퓨터 하드웨어의 세부사항을 다루지 않기 위해 보통 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별. 각 알고리즘에 필요한 연산 수를 셈입력 데이터의 세부사항을 다루지 않으려면 가장 좋은 선택은 기대하는 입력 데이터에 대한 평균..

인터페이스리스트가 두 종류인 이유왜 자바는 List 인터페이스에 두 가지 구현을 제공?둘 중에 어느 것을 선택?어느 것이 더 좋을지는 수행하는 동작에 달려 있음자바 interface자바 interface는 메서드 집합을 의미ex) Comparable interfacepublic interface Comparable {public int compareTo(T o);}interface는 타입 파라미터인 T를 사용하여 Comparable이라는 제네릭 타입을 정의이 interface를 구현하려면 클래스는 다음과 같아야 함T 타입을 명시해야 함T 타입의 객체를 인자로 받고 int를 반환하는 compareTo() 메서드를 제공해야 함expublic int compareTo(Integer anotherInteger)..