[자바로 배우는 핵심 자료구조와 알고리즘] 2장. 알고리즘 분석

2023.03.12 - [Study/Think Data Structures] - [자바로 배우는 핵심 자료구조와 알고리즘] 1장. 인터페이스

[자바로 배우는 핵심 자료구조와 알고리즘] 1장. 인터페이스

 

✏️본 게시글은 자바로 배우는 핵심 자료구조와 알고리즘을 학습한 내용을 개인적으로 학습하기 위해 정리한 글입니다.

 

프로파일링 접근법을 통해 어떤 응용 프로그램에서 어느 클래스가 더 좋을지 둘 다 시도해 보고 각각 얼마나 걸리는지 비교하면 됩니다.

대신 몇 가지 문제점이 있습니다.

1. 알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야 합니다.
2. 결과는 사용하는 컴퓨터의 성능에 의존합니다.
3. 결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 합니다.

알고리즘 분석을 사용하여 이러한 문제점을 해결할 수 있습니다. 알고리즘 분석은 그것을 구현하지 않고도 알고리즘을 비교할 수 있게 합니다.

하지만 몇 가지 가정을 해야만 합니다.

1. 보통 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별합니다. 그리고 각 알고리즘에 필요한 연산 수를 셉니다.
2. 가장 좋은 선택은 기대하는 입력 데이터에 대한 평균 성능을 분석하는 것입니다. 가능하지 않을 때는 대안으로 최악의 시나리오를 분석하기도 합니다.
3. 한 알고리즘이 작은 문제에서는 최상의 성능을 보이지만 큰 문제에서는 다른 알고리즘이 더 좋을 수 있다는 가능성을 배제하면 안 됩니다.

이러한 종류의 분석은 간단한 알고리즘 분류에 적합합니다.

예를 들어, 알고리즘 A의 실행시간이 입력 n의 크기에 비례하고 알고리즘 B는 n²에 비례하는 경향이 있다면 적어도 n의 값이 클 때는 A가 B보다 빠르다고 기대합니다.

대부분 간단한 알고리즘은 다음 몇 가지 범주로 나뉩니다.

• 상수시간 : 실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수시간을 따릅니다.
• 선형 : 실행시간이 입력의 크기에 비례하면 알고리즘은 선형이라고 합니다.
• 이차 : 실행시간이 n²에 비례하면 알고리즘은 이차라고 합니다.

2.1 선택 정렬

예를 들어, 다음은 선택 정렬이라는 간단한 알고리즘의 구현입니다.

첫 번째 메서드 swapElements는 배열에 있는 두 요소의 값을 바꿉니다. 요소를 읽고 쓰는 것은 상수 시간 연산입니다.

두 번째 메서드 indexLowest는 주어진 위치인 start에서 시작하여 배열에 있는 가장 작은 요소의 인덱스를 찾습니다.

간단하게 비교 횟수를 세면 다음과 같습니다.

1. start 인자가 0이면 indexLowest 메서드는 전체 배열을 검색하고 전체 비교 횟수는 배열의 길이인 n이 됩니다.
2. start 인자가 1이면 비교 횟수는 n - 1이 됩니다.
3. 일반적으로 비교 횟수는 n - start가 되어 indexLowest 메서드는 선형이 됩니다.

세 번째 메서드 selectionSort는 배열을 정렬합니다. 0에서 n - 1까지 반복하므로 n번 반복 실행됩니다.

매번 indexLowest 메서드를 호출한 후 상수 시간 연산인 swapElements 메서드를 실행합니다.

indexLowest 메서드가 처음 호출되면 n번 비교 연산을 합니다. 두 번째는 n-1번 비교 연산을 합니다.

이렇게 하면 총 비교 횟수는 n + n - 1 + n - 2 + ⋯ + 1 + 0입니다.

이 수열의 합은 n(n + 1)/2이고 n²에 비례합니다. 이것은 selectionSort 메서드가 이차라는 것을 의미합니다.

다른 방법으로 같은 결과를 얻으려면 indexLowest 메서드를 중첩된 반복문으로 생각할 수 있습니다.

indexLowest 메서드를 호출할 때마다 연산 횟수는 n에 비례합니다. 이를 n번 호출하므로 결과적으로 총 연산 횟수는 n²에 비례하게 됩니다.

2.2 빅오 표기법

모든 상수 시간 알고리즘은 O(1)이라는 집합에 속합니다. 따라서 어떤 알고리즘이 상수 시간임을 다르게 말하고 싶다면 그것이 O(1)에 있다고 말하면 됩니다.

마찬가지로 모든 선형 알고리즘은 O(n)에 속하며 모든 이차 알고리즘은 O(n²)에 속합니다.

이렇게 알고리즘은 분류하는 방식을 빅오 표기법이라고 합니다.

일반적으로 n의 가장 큰 지수만 신경 쓰면 돼서 총 연산 횟수가 2n + 1이라면 실행시간은 O(n)이 됩니다.

마찬가지로 n² + 100n + 1000도 O(n²)이 됩니다.

증가 차수는 같은 개념의 다른 이름입니다. 증가 차수는 실행 시간이 같은 빅오 범주에 해당하는 알고리즘 집합입니다.
예를 들어, 모든 선형 알고리즘은 실행시간이 O(n)에 있으므로 같은 증가 차수에 속합니다.
이 문맥에서 차수는 집단의 의미로, 원탁의 기사단처럼 기사들의 집단을 가리키지 그들의 순서를 말하는 것이 아닙니다.
따라서 선형 알고리즘 차수는 용감하고 예의 바르고 특히 효율적인 알고리즘 집합으로 생각하면 됩니다.