Data Structure/Think Data Structures 검색 결과

해당 글 3건

3. ArrayList 클래스

3.1 MyArrayList 메서드 분류하기 @Override public T get(int index) { if (index = size) { throw new IndexOutOfBoundsException(); } return array[index]; } get메서드에 있는 모든 것은 상수 시간이므로, get 메서드는 상수 시간이다. @Override public T set(int index, T element) { // TODO: FILL THIS IN! T old = get(index); array[index] = element; return old; } set 메서드는 배열의 범위를 검사하지 않고, 인덱스가 유효하지 않으면 에외를 던지는 get 메서드를 호출한다. get..
Data Structure/Think Data Structures 2024. 1. 17. 22:04

2. 알고리즘 분석

상수시간 O(1) 실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수시간을 따른다고 한다. n 개의 배열에서 [] 를 사용하여 요소 중 하나에 접근할 때 이 연산은 배열의 크기와 관계없는 같은 수의 동작을 반복한다. 선형 O(n) 실행시간이 입력의 크기에 비례하면 알고리즘은 선형이라고 한다. 배열에 있는 요소를 더한다면 n개 요소에 접근하여 n-1번 더하기 연산을 해야한다. 연산의 총 횟수는 2n-1이고 n에 비례한다. 이차 O(n²) 실행시간이 n^ 에 비례하면 알고리즘은 이차라고 한다. 리스트에 있는 어떤 요소가 두 번 이상 나타나는지를 알고 싶다고 가정했을때, 각 요소를 다른 모든 요소와 비교하는 알고리즘을 사용했을때 n^ 에 비례한다. ( n개의 요소가 있고 각각 n-1개의 다른 요소와 비교하..
Data Structure/Think Data Structures 2023. 12. 29. 00:22