알고리즘의 시간 복잡도와 공간 복잡도의 개념, 빅오 표기법

알고리즘의 성능을 이야기할 때에는 시간 복잡도와 공간 복잡도에 대해 이야기한다.

시간 복잡도는 문제를 해결하는 데 걸리는 시간이고 공간 복잡도는 메모리 공간을 얼마나 사용하는지 나타낸다.

입력 크기에 따라서 어떻게 되는지는 빅오 표기법을 통해 표시한다.

Wikipedia Big O notation Graph

특정 데이터를 찾을 때에는 왼쪽에서 시작하여 오른쪽으로 끝이 나는 방법 같이 선형적으로 찾게 된다. 운에 귀결되는 탐색이다.

이러한 방식으로 모든 값을 확인하는 것은 O(n) 시간 복잡도를 뜻한다.

하지만 알고리즘으로 정렬이 되어있다면 특정 데이터를 빠르게 찾을 수 있게 된다.

자주 사용되는 정렬 알고리즘의 동작 원리와 시간 복잡도

Sorting Algorithms	Time Complexity	Space Complexity
Best Case	Average Case	Worst Case
Selection Sort	O(1)	O(n^2)	O(n^2)	O(n^2)
Insertion Sort	O(1)	O(n)	O(n^2)	O(n^2)
Bubble Sort	O(1)	O(n)	O(n^2)	O(n^2)
Quick Sort	O(log n)	O(log n)	O(n log n)	O(n^2)
Merge Sort	O(n)	O(n log n)	O(n log n)	O(n log n)
Heap Sort	O(1)	O(n log n)	O(n log n)	O(n log n)

예외 사항을 포함하지 않은 코드는 아래와 같다.

선택 정렬(Selection Sort)

func selectionSort(_ arr: inout [Int]) {
    for i in 0..<arr.count - 1 {
        var least = i

        // i번째 이후 원소들 중 최소 값을 가진 index를 least로 지정
        for j in i+1..<arr.count where arr[j] < arr[least] {
            least = j
        }

        // least가 달라졌다면 위치를 변경
        if i != least {
            arr.swapAt(i, least)
        }
    }
}

삽입 정렬(Insertion Sort)

func insertionSort(_ arr: inout [Int]) {
    for i in 1..<arr.count {
        let current = arr[i]
        var j = i - 1

        // 현재과 j번째 값을 비교
        // 현재보다 큰 값들은 한 칸씩 뒤로 이동
        while j >= 0, arr[j] > current {
            arr[j + 1] = arr[j]
            j -= 1
        }

        // 현재를 정렬되는 위치에 삽입
        arr[j + 1] = current
    }
}

버블 정렬(Bubble Sort)

func bubbleSort(_ arr: inout [Int]) {
    for i in stride(from: arr.count - 1, through: 0, by: -1) {
        // 근접한 원소들을 비교하면서 변경
        // 가장 큰 값을 차례대로 채운다.
        for j in 0..<i where arr[j] > arr[j + 1] {
            arr.swapAt(j, j + 1)
        }
    }
}

퀵 정렬(Quick Sort)

func quickSort(_ arr: inout [Int], _ low: Int, _ high: Int) {
    guard low < high else { return }

    // pivot을 기준
    // pivot보다 작은 수가 담긴 배열, 큰 수가 담긴 배열을 재귀
    let p = partition(&arr, low, high)

    quickSort(&arr, low, p - 1)
    quickSort(&arr, p + 1, high)
}

func partition(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int {
    // 배열의 마지막 원소를 기준
    let pivot = arr[high]
    var i = low

    // j번째 원소가 pivot보다 작으면 i번째 원소와 교체
    // 교체를 했다면 i번째는 유지해야 하니깐 1 증가하면 다음 교체해야 할 원소를 유지
    for j in low..<high where arr[j] <= pivot {
        arr.swapAt(i, j)
        i += 1
    }

    // pivot이었던 high의 원소를 기준점으로 되는 i번째로 교체
    arr.swapAt(i, high)
    return i
}

병합 정렬(Merge Sort)

func mergeSort(_ array: inout [Int]) {
    // 배열이 하나 이하의 요소를 가지면 이미 정렬된 것으로 간주
    guard array.count > 1 else { return }

    // 배열을 반으로 나누기
    let middleIndex = array.count / 2
    var leftArray = Array(array[..<middleIndex])
    var rightArray = Array(array[middleIndex...])

    // 두 배열을 재귀적으로 정렬
    mergeSort(&leftArray)
    mergeSort(&rightArray)

    // 두 배열을 병합
    array = merge(leftArray, rightArray)
}

func merge(_ lhs: [Int], _ rhs: [Int]) -> [Int] {
    var leftIndex = 0, rightIndex = 0, mergedArray = [Int]()

    // 두 배열을 비교하면서 정렬된 배열을 만듦
    while leftIndex < lhs.count && rightIndex < rhs.count {
        if lhs[leftIndex] < rhs[rightIndex] {
            mergedArray.append(lhs[leftIndex])
            leftIndex += 1
        } else {
            mergedArray.append(rhs[rightIndex])
            rightIndex += 1
        }
    }

    // 남은 요소들을 추가
    mergedArray.append(contentsOf: lhs[leftIndex...])
    mergedArray.append(contentsOf: rhs[rightIndex...])

    return mergedArray
}

 

이진 탐색의 원리와 시간 복잡도

이진 탐색은 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다.

책의 특정 페이지를 과격하게 찾아보면 특정 페이지를 찾기 위해 책의 절반을 펼쳐서 페이지를 확인한다.

펼친 페이지가 특정 페이지보다 크다면 큰 페이지들의 부분을 찢어버린다. 그리고 다시 남은 책을 가지고 탐색을 반복한다.

탐색의 범위를 계속 절반으로 나누기 때문에 시간 복잡도가 O(log n)이지만, 배열이 정렬되지 않으면 사용할 수 없다.

선형 탐색을 하게되면 O(n)의 시간 복잡도이기에 이진 탐색은 훨씬 효율적이다.

 

다이나믹 프로그래밍(Dynamic Programming)

큰 문제를 작은 문제로 나누고 해결된 작은 문제를 저장하는 방식이다.

답을 재활용하는 것으로 대표적인 문제는 피보나치 수열로 이미 진행했던 연산을 재활용하여 해결한다.

• 상향식 접근법: 재귀로 문제를 해결하면서 동일한 문제를 이전에 계산관 결과를 재활용하는 것으로 메모이제이션 기법을 사용
• 하향식 접근법: 작은 문제부터 시작하여 큰 문제까지 순차적으로 해결하는 방식

---

모든 사진에 대한 출처는 Wikipedia 입니다.