Big O 표기법

시간 복잡성 개요

Unsplash에 Jeff Fielitz의 사진

소프트웨어 엔지니어로서 우리 시대에는 문제 해결을위한 코드 작성이 포함됩니다. 주어진 문제를 해결하는 방법에는 여러 가지가 있지만 어떤 방법이 가장 좋은지 어떻게 알 수 있습니까? 컴퓨터가 솔루션을 실행하는 속도입니까? 사용 된 컴퓨터 메모리의 양입니까? 이러한 질문에 대한 답과 솔루션 비교 방법은 Big O 개념을 통해 이루어집니다. 이 블로그는 시간 복잡성의 범주에 속하는 속도의 첫 번째 질문에 초점을 맞출 것입니다.

Big O 표기법에 더 깊이 들어가기 전에 정리해야 할 한 가지는 알고리즘 개념입니다. 알고리즘은 "일반적으로 문제 클래스를 해결하거나 계산을 수행하기위한 잘 정의 된 컴퓨터 구현 가능한 명령의 유한 시퀀스"로 정의됩니다 ( Wikipedia ). 간단히 말해서 알고리즘은 문제에 대한 해결책이며 Big O 표기법을 사용하여 알고리즘을 비교하고 논의합니다.

Big O 표기법은 무엇입니까?

앞서 언급했듯이 Big O 개념은 소프트웨어 엔지니어에게 알고리즘과 알고리즘의 성능을 논의하는 방법을 제공합니다. 알고리즘이 얼마나 빠른지 알려면 코드를 실행하는 데 걸리는 시간 (초)이 아니라 컴퓨터가 실행해야하는 작업 수를 계산합니다. 또는 더 정확하게는 "… 입력이 증가함에 따라 알고리즘의 런타임이 증가하는 방식"(Steele)을 측정합니다.

Big O는 어떻게 생겼으며 어떻게 사용합니까?

Big O 개념에서는 각 개별 작업을 계산하는 대신 알고리즘의 전체적인 추세를 봅니다. 또한 위에서 언급했듯이 우리가 정말로 알고 싶은 것은 입력이 증가함에 따라 런타임이 어떻게 변하는 지입니다. 알고리즘은 일반적으로 가장 효율적인 것부터 가장 낮은 것까지 5 가지 Big O 시간 복잡성 중 하나에 속합니다.

  1. O (1)
  2. O (로그 n)
  3. O ( n )
  4. O (n * log n)
  5. O (n ^ 2)
  6. Colt Steele의 JavaScript 알고리즘 및 데이터 구조 마스터 클래스 Udemy 과정에서 Big O 표기법 시간 복잡성의 시각적 표현

function findLetter(string, letter) {
   let match = false
   for (let i = 0; i < string.length; i++) {
     if(string[i] === letter) {
       match = true
     }
   }
   return match
}

다음으로 다양한 유형의 Big O 표기법 복잡성을 살펴보고 각각에 대한 예제 알고리즘을 제공합니다. 제공된 예제 중 하나를 제외하고는 모두 Colt Steele의 JavaScript 알고리즘 및 데이터 구조 마스터 클래스 Udemy 과정에서 가져온 것입니다.

O (1)

알고리즘이 O (1) 시간 복잡도를 가질 때 알고리즘은 일정한 실행 시간을 갖는다 고합니다. 이는 입력의 크기에 관계없이 런타임이 일정하게 유지됨을 의미합니다. 이것은 가장 효율적인 알고리즘 유형입니다.

Function that calculates the sum of all numbers from 1 to the number n.
function addUpTo(n) {
   return n * (n + 1) / 2;
}

O (로그 n)

일정한 실행 시간이 알고리즘 시간 복잡성의 가장 효율적인 유형이지만 로그 시간이라고도하는 O (log n)는 가까운 초입니다. O (log n) 알고리즘의 주된 특징은“… 일부 동작을 수행 할 다음 요소의 선택은 여러 가능성 중 하나이며 하나만 선택하면된다”(Stack Overflow)라는 것입니다. O (log n)를 나타내는 일반적인 예는 이진 검색입니다. Flatiron School은 아래와 같이 이진 검색의 훌륭한 예를 제공합니다.

function findLetter(string, letter) {
    let startpoint = 0
    let endpoint = string.length - 1;
    let guessPosition = parseInt((endpoint - startpoint)/2)
while (startpoint != endpoint) {
      console.log(`start point is ${startpoint}, endpoint is     ${endpoint} and guessposition is ${guessPosition}`)
if (string[guessPosition] < letter) {
          console.log('too low')
            startpoint = guessPosition
            guessPosition = startpoint + Math.round((endpoint - startpoint)/2)
        } else if(string[guessPosition] > letter) {
          console.log('too high')
            endpoint = guessPosition
            guessPosition = startpoint + parseInt((endpoint - startpoint)/2)
        } else {
          console.log('just right')
            return true;
        }
    }
    if(string === letter){
      return true
    } else{
      console.log('sorry')
      return false;
    }
  }

let string1 = "aabeeeeeeffhhiiiimmooorsssssstttttttwww"
let letter1 = "t"
findLetter(string1,letter1)

Output:
start point is 0, endpoint is 38 and guessposition is 19
too low
start point is 19, endpoint is 38 and guessposition is 29
just right
true

Flatiron School의 바이너리 검색 차트

의 위에)

다음으로 가장 효율적인 시간 복잡도는 O (n)이며, 문자열에서 문자를 찾는 이전 예제에서 보았습니다 (아래 참조). O (n)을 사용하는 알고리즘의 런타임은 선형 런타임을 갖습니다. 이는 작업 수가 n에 비례하여 대략적으로 증가 함을 의미합니다. 이 알고리즘이 작동하는 방식과 런타임이 입력 수와 선형 방식으로 상호 연관되는 방식에 대한 이전 설명을 다시 참조하십시오.

function findLetter(string, letter) {
   let match = false
   for (let i = 0; i < string.length; i++) {
     if(string[i] === letter) {
       match = true
     }
   }
   return match
}

시간 복잡성이 O (n log n) 인 알고리즘은 지금까지 논의한 복잡성보다 덜 효율적이지만 큰 배열의 경우 O (n²)를 사용하는 알고리즘보다 훨씬 더 나은 런타임을 가질 수 있습니다. 시간 복잡도가 O (n log n) 인 알고리즘의 일반적인 예는 이름에서 알 수 있듯이 빠른 정렬 알고리즘입니다.

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  // We are assuming the pivot is always the first element
  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

  // Swap the pivot from the start the swapPoint
  swap(arr, start, swapIdx);
  return swapIdx;
}


function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){
        let pivotIndex = pivot(arr, left, right) //3
        //left
        quickSort(arr,left,pivotIndex-1);
        //right
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
} 
           
quickSort([100,-3,2,4,6,9,1,2,5,3,23])


// Shows how the algorithm works toward a solution

// [4,6,9,1,2,5,3]
// [3,2,1,4,6,9,5]
//        4
//  3,2,1    6,9,5
//      3      6
//  2,1      5  9
//    2
//  1

Output:
[  -3, 1, 2, 2,  3, 4, 5, 6, 9, 23, 100]

O (n²)

우리가 논의 할 마지막 알고리즘은 2 차 런타임이라고도하는 O (n²)입니다. O (n²)보다 느린 알고리즘이 있지만 2 차 시간 복잡도는 일반적으로 알고리즘에 대해 허용 할 수있는 최악의 복잡도입니다.

// function prints all the number pairs from 0 up to but not including n
function printAllPairs(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
}
printAllPairs(3)
Output:
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

시간을내어 Big O 개념과 다양한 시간 복잡성의 예에 대해 자세히 알아 보셔서 감사합니다. Big O 개념과 공간 복잡성에 대해 논의하는 다음 블로그를 찾아보세요.

자원

Steele, C. (nd). JavaScript 알고리즘 및 데이터 구조 마스터 클래스 . 온라인 코스.

Big O 근사. (nd). https://learn.co/lessons/big-o-approximation 에서 2020 년 10 월 10 일 검색

Feminella, J. (nd). O (log n)는 정확히 무엇을 의미합니까? https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly?page=1 에서 검색 함

연산. (2020 년 10 월 7 일). https://en.wikipedia.org/wiki/Algorithm 에서 2020 년 10 월 10 일 검색

Suggested posts

C # 문자열 대 문자열 — 단순한 스타일 이상?

C # 문자열 대 문자열 — 단순한 스타일 이상?

C #으로 작업 할 때 자주 묻는 질문은 문자열 또는 문자열을 사용할지 여부입니다. C #은 언어가 모든.

Go를 사용한 Raft 합의 알고리즘 구현

Go를 사용한 Raft 합의 알고리즘 구현

“분산 컴퓨팅 및 다중 에이전트 시스템의 근본적인 문제는 여러 결함이있는 프로세스가있을 때 전체 시스템 안정성을 달성하는 것입니다. 이를 위해서는 종종 합의에 도달하거나 계산 중에 필요한 일부 데이터 값에 동의하기위한 조정 프로세스가 필요합니다.

Related posts

"실용적인 프로그래머"의 5 가지 필수 사항

역대 베스트셀러 코딩 북의 요점

"실용적인 프로그래머"의 5 가지 필수 사항

Pragmatic Programmer는 1999 년에 처음 출판되었으며 이후 역대 최고의 프로그래밍 책으로 선정되었습니다. 저자 Andy Hunt와 David Thomas는 Agile Manifesto의 원저자 중 하나였으며 몇 가지 심각한 자격을 가지고 있습니다.

대규모 GraphQL 쿼리 공격으로부터 보호

공격자가 공개적으로 사용 가능한 GraphQL 인터페이스를 사용하여 사이트를 스크랩하거나 서비스 거부 공격을 실행하는 방법에 대해 알아보십시오. 이들은 4 가지 방법 중 하나로이를 수행 할 수 있습니다. 단일 대형 쿼리를 신중하게 구성하여 실행하고, 관련 데이터를 가져올 수있는 병렬 쿼리를 많이 작성하고, 일괄 요청을 사용하여 많은 쿼리를 연속적으로 실행하고, 마지막으로 많은 요청을 보냅니다.

기술 인터뷰의 사회적 구성 요소

코딩 문제는 스트레스가 많지만 스트레스에 대한 당신의 반응은 당신의 기술적 능력보다 더 크게 말합니다.

기술 인터뷰의 사회적 구성 요소

기술 업계의 직책을 위해 인터뷰 할 때 일반적으로 제안을 고려하기 전에 최소한 3 차례의 인터뷰를 거치게됩니다. 라운드는 일반적으로 다음과 같습니다. 그렇게 생각하면 잘못된 것입니다.

훌륭한 개발자의 3 가지 행동 특성

훌륭한 개발자의 3 가지 행동 특성

훌륭한 개발자를 만드는 비 기술적 인 것들 나는이 기사를 작성하는 것을 한동안 미루고 있습니다. 나는 그것을 작성할 자격이 있다고 생각하지 못했습니다. 오늘은 쓸 때라고 생각했습니다.