O(n*logn)란?대수 O의 선형 시간 복잡도 이해

큰 O 기호보다 더 무서운 컴퓨터 과학 주제가 있습니까?이름을 놀라게 하지 마라, 큰 O 기호는 큰 문제가 아니다.이것은 이해하기 쉽다. 너는 수학 천재가 될 필요가 없이 이해할 수 있다.이 자습서에서는 JavaScript 예제에서 대수 선형 또는 의선형 시간의 복잡도에 대한 큰 O 기호의 기본 원리를 학습합니다.
이것은 큰 O 기호에 관한 시리즈 문장 중의 다섯 번째 편이다.순환에 남고 싶다면sign up for my weekly newsletter, The Solution.

빅오는 어떤 문제를 해결했나요?

큰 O 기호는 우리가 이 문제에 대답하는 데 도움을 준다. "그것이 확장됩니까?"

대O 기호는 다른 개발자(수학자와!)와 성능을 토론하는 공유 언어를 제공합니다.

빠른 연수
만약 네가 방금 우리에 가입했다면, 너는 그 문장부터 시작하고 싶을 것이다. What is Big O Notation?

무엇이 큰 O입니까?
대O표현법은 알고리즘의 성장률을 측정하는 시스템이다.대O 기호는 수학적으로 알고리즘이 시간과 공간에서의 복잡성을 묘사했다.우리는 초(또는 분!)로 알고리즘의 속도를 측정하지 않는다.반대로 우리는 완성에 필요한 조작수를 측정한다.
O는 순서의 줄임말이다.그래서 만약에 우리가 O(n^2)로 알고리즘을 토론한다면 우리는 그 단계나 성장률이 n^2 또는 2차 복잡도라고 말한다.

빅오는 어떻게 일하나요?
큰 O 기호는 최악의 상황을 평가한다.
왜?
우리가 모르니까. 우리가 모르는 거.
우리는 우리의 알고리즘 성능이 얼마나 나쁜지 알아야 다른 해결 방안을 평가할 수 있다.
최악의 경우도 상한선이라고 불린다.우리가 '상한' 을 말할 때, 우리는 알고리즘이 실행하는 최대 조작수를 가리킨다.
이 책상 기억나세요?
O
복잡성
성장률
O(1)
상수
스피드
O(대수 n)
대수적
O(n)
선형 시간
O(n*logn)
대수선성
O(n^2)
이차적
O(n^3)
입방체의
O(2^n)
지수형
O(n!)
계단의
완만했어
그것은 성장률에 따라 가장 빠른 주문서에서 가장 느린 주문서를 열거했다.
O(n logn)를 논의하기 전에 O(n), O(n^2)와 O(logn)를 살펴보자.

O(n)
선형 시간의 복잡성의 한 예는 간단한 검색인데, 그 중에서 수조의 모든 요소는 검색에 따라 검사된다.

const animals = [“ocelot”, “octopus”, “opossum”, “orangutan”, “orca”, “oriole”, “oryx”, “osprey”];

for (let i = 0; i < animals.length; i++) {
    if (animals[i] === userInput) {
        return `Found ${userInput} at ${i}`;
    };
};

더 깊이 들어가고 싶으면 Big O Linear Time Complexity를 보세요.

O(n^2)
O(n^2)의 대표적인 예는 Bubble Sort이다.

const bubbleSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (arr[j] > arr[j + 1]) {
                let tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    return arr;
};

왜 bubbleSort()O(n^2)의 순서입니까?
🔑 같은 입력의 중첩 순환을 반복합니다.
우리도 while 순환으로 쓸 수 있다.

const bubbleSort = arr => {

  let swapped = true;

  while (swapped) {
    swapped = false;

    for (let i = 0; i < arr.length; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
  }
  return arr;
}

어쨌든, 그것은 여전히 플러그인 교체를 사용하기 때문에, 그것은 O (n^2) 이다.
더 깊이 들어가고 싶으면 Big O Quadratic Time Complexity를 보세요.

O(대수 n)
2진 검색은 수 시간의 복잡도에 대한 대표적인 예이다.

const binarySearch = (arr, num) => {

   let startIndex = 0;
   let endIndex = (arr.length)-1;

   while (startIndex <= endIndex){

       let pivot = Math.floor((startIndex + endIndex)/2);

       if (arr[pivot] === num){
            return `Found ${num} at ${pivot}`;
       } else if (arr[pivot] < num){
           startIndex = pivot + 1;
       } else {
           endIndex = pivot - 1;
       }
   }
   return false;
}

🔑 매번 교체할 때마다, 우리의 함수는 입력을 분할하여, 幂 연산의 역연산을 집행한다.
더 깊이 들어가고 싶으면 Big O Logarithmic Time Complexity를 보세요.

O(n logn): 대수 선형 시간 복잡도
그럼 O (n logn)는 뭘까요?
그렇습니다.그것은 n으로, 하나의 선형 시간 복잡도를 곱하고, 대수 n을 곱하고, 하나의 대수 시간 복잡도를 곱한다.
☝️
"잠깐만요, 선생님."라고 네가 말하는 것을 들었다.
"당신은 우리가 비주도 조항을 포기한다고 말했는데, 이 n*logn 업무는 어떻게 된 것입니까?"
비록 우리가 빅O의 비주도 항목을 포기했지만 이것은 보통 두 가지 다른 복잡성을 추가할 때n^2 + n이다.여기서 우리는 곱셈을 사용한다.우리는 더 간소화할 수 없다n * log n. 그래서 우리는 이 두 가지 조건을 보류한다.
O(nlogn)는 우리에게 알고리즘의 성장률을 나타내는 방법을 제공했다. 이 알고리즘의 성능은 O(n^2)보다 우수하지만 O(n)보다 못하다.

계산 O(n logn):정렬 병합
예를 하나 봅시다.O(n logn)는 정렬 알고리즘에서 흔히 볼 수 있고 이상적이다.위에서 보듯이, 우리는 플러그인 교체 강제 정렬을 쉽게 사용할 수 있지만, 이러한 방법은 확장할 수 없다.
다음은 Merge Sort의 실현이다.

const nums = [128, 0, 64, 16, 4, 8, 2];

const merge = (left, right) => {

    let result = [];

    while(left.length || right.length) {

        if(left.length && right.length) {
            if(left[0] < right[0]) {
                result.push(left.shift())
            } else {
                result.push(right.shift())
            }
        } else if(left.length) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    return result;
};

const mergeSort = (arr) =>{
    if(arr.length <= 1) {
        return arr;
    }

    const pivot = arr.length / 2 ;
    const left = arr.slice(0, pivot);
    const right = arr.slice(pivot, arr.length);

  return merge(mergeSort(left), mergeSort(right));
};

우리는 이전에 이 문제를 본 적이 있습니까?
🤔
우리의 merge() 함수는 위의 기포 정렬에서 본 것과 유사합니다.그것은 두 개의 그룹을 받아들여 일련의 조건문을 통해 값을 그룹에서 옮긴 다음 그것들을 새로운 그룹 result 으로 밀어 넣는다.merge() 몇 번의 작업이 수행됩니까?
n
수조를 정렬하기 위해서, 우리는 모든 원소를 최소한 한 번 교체해야 하기 때문에, 우리는 이미 O (n) 에 도달했다.mergeSort()무슨 일이 일어났어요?
우리의 mergeSort() 함수는 위의 binarySearch()와 유사한 모델을 따른다.우리는 축을 만들고 입력을 두 개의 그룹으로 나누었다.
이것은 우리에게 무엇을 알려줍니까?
O(logn).
만약 우리가 두 함수를 합치면 mergeSort()의 순서는 O(n logn)이다.

대수선형 시간 복잡도
이 자습서에서는 JavaScript 예제를 통해 대수 선형 시간의 복잡도에 대한 기본 원리를 배웠습니다.
O(n 대수 n)의 배율이 조정됩니까?
그래.
우리가 더 잘할 수 있을까?
좋아요.
상황을 보고 결정하다.
수선형 시간의 복잡도는 많은 흔히 볼 수 있는 정렬 알고리즘의 순서이다.그러나 모든 정렬 알고리즘이 평등한 것은 아니다.우리는 이후의 문장에서 이것에 대해 탐구를 진행할 것이다.순환에 남고 싶다면sign up for my weekly newsletter, The Solution.