1. 자료구조와 알고리즘의 이해

이하은·2021년 6월 11일

빅-오 순차탐색 시간복잡도 공간복잡도 알고리즘 이진탐색 자료구조 자료구조 스터디

자료구조 스터디

목록 보기

1/2

자료구조란

데이터의 표현 및 "저장" 방법.

선형 자료구조 : 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식 ex) 리스트, 스택 큐

비선형 자료구조 : 데이터를 나란히 저장하지 않는 구조 ex) 트리, 그래프

자료구조와 알고리즘

자료구조 : 데이터의 표현 및 저장방법

알고리즘 : 데이터를 대상으로 하는 문제의 해결방법

⇒ 자료구조에 따라서 알고리즘은 달라진다. 알고리즘은 자료구조에 의존적이다.

알고리즘의 성능분석 방법

시간 복잡도 : 속도에 해당하는 알고리즘의 수행시간 분석결과

공간 복잡도 : 메모리 사용량에 대한 분석결과

대용량 시스템이 보편화되면서, 성능문제는 메모리 사용량보단 "속도"에 관심이 더 많음

속도(시간복잡도)를 평가하는 방법은 데이터의 수에 대한 연산횟수로 판단한다 🔴

좋은 알고리즘이란 데이터의 수가 많아짐에 따른 연산횟수의 증가폭이 적은 알고리즘이다.

하지만 언제나 같은 정답은 없고 상황에 맞게 종합적으로 사고하고 판단해야 한다.

~~(공간 복잡도는 연산횟수를 메모리 사용량으로 치환해서 읽으면 된다)~~

알고리즘과 시간복잡도 분석의 핵심요소

알고리즘의 시간복잡도를 계산하기 위해서는 어떠한 연산의 횟수를 기준으로 성능을 분석할 건지, 핵심이 되는 연산이 무엇인지 잘 판단해야한다.

ex) 탐색 알고리즘에서 연산횟수의 기준이 되는 핵심 연산은 == 동등비교연산이다.

모든 알고리즘에는 최선의 경우(best case ) 최악의 경우(worst case)가 존재한다.

알고리즘을 평가할 때에 최선의 경우는 의미가 없다. 최악의 경우가 알고리즘 성능을 판단하는데 있어서 중요하다.

평균적인 경우도 중요한 정보지만 '평균적인 경우' 자체를 설정하는게 어렵고 신뢰도가 떨어져서 일반적으로는 최악의 경우로 알고리즘을 평가한다.

빅-오 표기법

빅-오란 복잡도를 구하는 함수에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다.

데이터 수의 증가에 따른 연산횟수의 증가 패턴을 나타내는 표기법이다.

빅오 표기법의 특징

1. 상수항 무시

입력값 n이 충분히 크다고 가정하고, 상수항 같은 미미한 영향력은 무시한다.

O(2N) -> O(N)
O(N² + 2) -> O(N²)

2. 영향력 없는 항 무시

결과에 가장 지배적인 항을 제외한 나머지 항들은 무시한다.

O(N² + N) -> O(N²)

복잡도 함수가 다항식으로 표현될 경우, 최고차항의 차수가 빅오가 된다

아무리 다른 상수나 영향력이 작은 항들이 붙어서 데이터 수에 대한 연산횟수의 증가율에 영향을 끼치려고 해도, 데이터가 커지면 커질수록 빅오에 해당하는 항 하나의 증가율 패턴을 넘지 못한다. 빅오가 증가 패턴의 기준이 되는것이다.

때문에 빅오는 증가율의 상한선을 표현하는 표기법이다 라고도 할 수 있다.

대표적인 빅-오

O(1) 상수형 빅오

데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘.
O(log n) 로그형 빅오

데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘.
매우 바람직한 유형
O(n) 선형 빅오

데이터의 수와 연산횟수가 비례하는 알고리즘.
O(n log n) 선형로그형 빅오

데이터의 수가 두배로 늘때 연산횟수는 두배를 조금 넘게 증가하는 알고리즘. 선형 알고리즘에서 증가율 각도가 조금 높음
O(n²) O(n³) 제곱형 빅오

제곱, 세제곱에 해당하는 연산횟수를 요구하는 알고리즘. 이중, 삼중으로 중첩된 반복문내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 성능이 매우 안좋음. 중첩된 반복문의 사용은 알고리즘 디자인에서 별로 바람직 하지 못하다.
O(2ⁿ) 지수형 빅오

데이터 수가 증가함에 따라 연산횟수가 지수로 증가하는 알고리즘. 사용하기에 무리가 있을정도로 성능이 매우 안좋다.

탐색 알고리즘으로 알아보는 빅오 표기법

순차 탐색 알고리즘 : T(n) = n >> O(n)

이진 탐색 알고리즘 : T(n) = log₂n + 1 >> O(logn)

순차 탐색 알고리즘 구현

// js
function linearSearch (arr, target) {
    let count = 0;

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
        count += 1;
    }
    console.log(`linearSearch 비교연산 횟수: ${count}`)
    return -1;
}

linearSearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], -1);

// linearSearch 비교연산 횟수: 16

이진 탐색 알고리즘 구현

참고로 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다.

// js
function binarySearch (arr, target) {
    let first = 0;
    let last = arr.length - 1;
    let mid;
    let count = 0;

    while (first <= last) {
        mid = Math.floor((first + last) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] > target) {
            last = mid -1;
        } else {
            first = mid + 1;
        }
        count += 1;
    }

    console.log(`binarySearch 비교연산 횟수: ${count}`)
    return -1;
}

binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], -1);

// binarySearch 비교연산 횟수: 4