어쨌든 "Big-O 표기법"은 무엇을 의미합니까?

프로그래머라면 "Big-O 표기법"이라는 용어를 우연히 발견했을 것입니다. 그러나 이것이 실제로 무엇을 의미합니까?

Big-O 표기법은 프로그램 또는 데이터 구조의 계산 복잡성을 지정하는 데 사용됩니다. 이것은 기본적으로 다음을 의미합니다. 특정 작업을 수행하는 데 몇 단계가 필요합니까? 이 컨텍스트에서 "단계"는 프로그램의 CPU 주기 또는 라인을 의미하는 것이 아니라 크기에 상관없이 고정된 길이의 임의의 단계를 의미합니다.

예를 들어 시작하겠습니다. 요소가 배열에 있는지 확인합니다. JavaScript에서는 다음과 같이 구현합니다.

function findInArray(array, element) {
    for(let i = 0; i < array.length; i++) {
        if(array[i] === element) {
            return true;
        }
    }
    return false;
}

아주 쉽게 볼 수 있습니다. 루프 내부의 모든 작업에는 일정한 시간이 걸립니다. 인덱스와 비교를 사용하여 배열의 요소에 액세스합니다. 이것을 1 "단계"로 정의합시다. 그러나 for 루프 때문에 이 작업을 n 번 수행합니다. Big-O에서: O(n) .

Big-O 표기법에 설명된 다른 표준 예는 정렬 알고리즘입니다. 가장 간단한 정렬 알고리즘인 버블 정렬을 예로 들어 보겠습니다. 구현은 다음과 같을 수 있습니다.

function bubblesort(array) {
    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length - 1; j++) {
            if(array[j] > array[j + 1]) {
                let tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}

배열의 모든 요소에 대해 전체 배열을 실행하고 필요한 경우 교체합니다. 이전과 마찬가지로 루프의 모든 것은 일정합니다. 그런 다음 이것을 n번 반복하는 루프가 있습니다. 그러나 첫 번째 루프n번을 실행하는 두 번째 루프가 추가로 있습니다. 그래서 우리는 n 단계를 n 번 실행합니다. Big-O 표기법: O(n*n) = O(n²)
그러나 대답이 그렇게 간단하지 않은 다른 경우도 있습니다. 다음 코드 조각을 예로 들어 보겠습니다.

function mapAndFilter(x) {
    return x
        .map(n => n * 2)
        .filter(n => n > 0);
}

이 함수의 복잡성은 무엇입니까? 인가

O(1) ?

O(n) ?

O(n²) ?

뭔가 다른가요?

정답은 O(n) 입니다. 왜요? 코드 자체는 일정하지만(직접 루프 없음) 다른 기능을 실행하는 데도 시간이 걸립니다. map의 경우 브라우저는 모든 요소를 ​​실행하고 해당 요소에 대한 함수를 호출합니다. 함께 우리의 함수는 O(n) 를 가질 것이지만 Big-O 표기법은 상수 요인을 고려하지 않으므로 filter 가 지워져서 findInArray 가 됩니다.

자신의 코드뿐만 아니라 라이브러리나 브라우저를 통해 가져온 코드도 항상 확인해야 하는 좋은 예라고 생각합니다. 데이터 구조에서 작동하는 모든 알고리즘에는 계산 복잡성이 있습니다. 알고 있다면 가능한 한 최소한의 복잡성을 갖도록 코드를 작성할 수 있습니다. 또한 "내 데이터 구조에서 수행해야 하는 작업은 무엇이며 이러한 작업에 대해 덜 복잡한 다른 데이터 구조가 있습니까?"라고 자문해 볼 수도 있습니다.

이것은 일반적인 데이터 구조와 내부적으로 어떻게 작동하는지에 대한 시리즈의 첫 번째 기사입니다. 이러한 종류의 기사에 관심이 있다면 나를 팔로우하고 관심 있는 데이터 구조를 작성하십시오.