비 CS의 각도에서 큰 O 기호를 보다

안녕하세요!

우리의 데이터 구조와 알고리즘 시리즈의 두 번째 문장에 오신 것을 환영합니다!지난번에 우리는 한 번 복습했다.이번에 우리는 큰 O 기호를 소개하고 시간과 공간의 복잡성을 깊이 있게 연구할 것이다.
우리는 훈련소를 졸업했기 때문에 Ruby on Rails, Java Script, React 등을 공부한 후에 우리는 많은 온라인 자원을 통해 빅오 기호를 배우는 데 많은 시간을 들여야 했다.우리는 이것이 당신의 장소가 되기를 희망합니다. 만약 당신이'간단한 영어'해석의 큰 O 기호를 찾고 있다면!

소개하다.

컴퓨터 과학에서 빅오 표현법은 알고리즘의 입력 크기가 커지면서 알고리즘의 운행 시간이나 공간 수요를 분류하는 데 사용된다.대학의 CS 학생에게 그들은 반드시 서로 다른 유형의 큰 기호(대O, 대θ, 대오메가)를 배워야 한다.
그러나 소프트웨어 공학 기술 면접을 위해 우리는 최선과 최악의 상황에만 관심을 갖는다.빅오가 CS 콘셉트에서 시간의 상한선을 묘사했지만, 업계에서는 빅오가 운용 시 가장 촘촘한 묘사를 제공하려고 애쓰고 있다.(게일 맥도널(Gayle McDowell)의 코딩 인터뷰를 해독하는 것은 이러한 개념의 아주 좋은 총결을 제공했다. 39페이지 읽기)

이 도표는 운행 시간과 공간이 어떻게 큰 O 기호의 입력에 따라 변화하는지 명확하게 보여 준다.O(1)와 O(log n)는 운행 시간과 공간의 복잡도가 가장 높았고, O(n!), O(n2)와 O(2n)는 운행 시간과 공간의 복잡도가 가장 낮았다.
본문에서, 우리는 제공된 예시와 각 부분의 끝에 있는 리코더 문제로 모든 기호를 분해할 것이다.

폭력과 최적화 해결 방안은 무슨 뜻입니까?

시작하기 전에 폭력과 최적화 해결 방안의 의미를 설명하고자 합니다. 본문 뒤에 보실 수 있는 키워드와 같습니다.
폭력 해결 방안이 무엇인지 이해하는 가장 간단한 방법은 당신이 가장 먼저 생각하는 모든 해결 방안이다.다른 한편, 최적화된 해결 방안에 대해 강력한 해결 방안을 얻은 후에 당신은 최적화된 해결 방안을 생각해서 코드를 간소화하거나 시간과 공간의 복잡성을 최대한 줄일 것입니다.
예를 들어 폭력 해결 방안의 시간 복잡도는 O(n2)이고 해결 방안을 최적화하면 시간 복잡도를 O(n)로 낮출 수 있다.
이 개념을 이해하는 것은 매우 중요하다. 왜냐하면 이것은 면접관과 토론할 문제이기 때문이다. 당신은 어떻게 당신의 해결 방안을 폭력에서 최적화된 해결 방안으로 바꿀 것인가.

복잡성 비교

성함
대O기호
고정 시간
O(1)
대수 시간
O(대수 n)
선형 시간
O(n)
선형 시간
로그
이차 시간
O(n2)
지수 시간
O(2n)
계단 곱하기 시간
O(n!)

고정 시간: O(1)

O(1)는 통상적으로'항정시간'이라고 불리며 복잡성이 가장 낮다.나는 그것을 입력이 아무리 크든 작든 함수 내부에서 같은 수량의 절차를 수행할 수 있다고 생각하는 것을 좋아한다.
예:

function sayHelloToFirstFriend(friends) {
   return `Hello ${friend[0]}`
}

sayHelloToFirstFriend([“spongebob”, “patrick”, “sandy”, “squidward”, “gary”])
// “Hello spongebob”

전형적인 용례
Inserting (push) or deleting (pop) from a Stack
Inserting or deleting a node in a Linked List
Insertion or deleting from a Queue
Searching, inserting, or deleting from a Hash Table

대수 시간: O(대수 n)

수학을 두려워하지 마라!네가 대수를 보았을 때, 그것은 너에게 묻는다. "이 답을 얻기 위해서, 우리는 반드시 이 기수를 어떤 멱으로 높여야 합니까?"다시 말하면, 변수가 지수일 때, 우리는 대수로 그것을 구해야 한다.
컴퓨터 과학에 대해 말하자면, 이것은 "1로 돌아가기 위해서, 우리는 반드시 n을 반으로 몇 번을 나누어야 합니까?"라는 것을 의미한다.따라서 사용O(log n)의 해결 방안은 기본적으로 문제를 둘로 나누어 계속해야 할 절반을 정하고 이 부분을 둘로 나누어 필요한 것을 찾거나 집합을 배제할 때까지 같은 생각을 반복하는 것이다.따라서 이러한 솔루션의 성장은 고정 시간을 초과했지만 다른 시간의 복잡성에 비해 성장이 느리다.
전형적인 용례
Binary Search
Certain Divide and Conquer Algorithms based on Linear functionality
Calculating Fibonacci Numbers
주의: 주의, 모든 이 용례에 대해 입력은 정렬과 검색을 거친다.

선형 시간: O(n)

가장 흔히 볼 수 있는 것은 O(n) 또는'선형 시간'일 것이다.입력 크기가 커지면 작업을 수행하는 데 걸리는 시간도 늘어나기 때문이다.다시 말하면, 한 그룹에 10개의 항목이 있으면 for 순환은 10회, 10000개의 항목이 있으면 같은 for 순환도 10000회 실행된다.
예1:

const binarySearch = (list, target) => {
  let start = 0
  let end = list.length - 1

  while (start <= end) {
    const middle = Math.floor((start + end) / 2)
    const guess = list[middle]

    if (guess === target) {
      return middle
    }

    if (guess > item) {
      // search the right side of the list
      end = middle - 1
    } else {
      // search the left side of the list
      start = middle + 1
    }
  }
  return null // if target is not found
}

예2:

function sayHelloToFriends(friends) {
   for (let i = 0; i < friends.length; i++) {
      console.log(`Hello ${friends[i]}`)
   }
}

sayHelloToFriends([“spongebob”, “patrick”, “sandy”, “squidward”, “gary”])
// “Hello spongebob”
// “Hello patrick”
// “Hello sandy”
// “Hello squidward”
// “Hello gary”

전형적인 용례
통과Array 또는 Linked List
Linear Search
Deletion of a specific element in a Linked List (Not sorted)
Comparing two strings
Checking for Palindrome
Anytime using a `for` loop or iterating

선형 시간: O(n 대수 n)

O(log n) 전형적인 해결 방안을 토대로 추가'n'은 추가 정렬 시간 비용에서 나온다.따라서 많은 정렬 알고리즘의 복잡도는 O(n log n)이다.다른 한편 O(log n)보다 시간이 더 걸리는 것은 사실이지만 대수 증가가 매우 느리다는 것을 기억하는 것도 중요하다.따라서 경로는 선형 시간과 유사하다.n가 맡은 역할을 한층 더 설명하기 위해 합병 순서를 살펴보자.O(log n)와 마찬가지로 합병 정렬에서 먼저 수조를 둘로 나눈다.다음에 두 개의 반부분을 정렬한 다음에 두 개의 정렬된 반부분을 정렬된 전체로 합친다.그러나 두 쪽을 정렬하기 위해서, 모든 것을 정렬할 때까지 똑같은 생각을 반복해서, 두 쪽을 나누고, 정렬하고, 정렬한 두 쪽을 합쳐라.
예:

function merge(left, right) {
    let arr = []
    // Break out of loop if any one of the array gets empty
    while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }

    // Concatenating the leftover elements
    // (in case we didn't go through the entire left or right array)
    return [ ...arr, ...left, ...right ]
}

function mergeSort(array) {
  const half = array.length / 2

  // Base case or terminating case
  if(array.length < 2){
    return array 
  }

  const left = array.splice(0, half)
  return merge(mergeSort(left),mergeSort(array))
}

전형적인 용례
Merge Sort
Heap Sort
Quick Sort
Certain Divide and Conquer Algorithms based on optimizing O(n²) algorithms

2차 시간: O (n2)

2차 시간 복잡도 함수의 성장률은 n2이다.무슨 뜻이에요?입력 크기가 2이면 함수는 4차례 동작을 수행합니다.입력 크기가 3이면 함수는 9번의 동작을 수행합니다.입력 크기가 1000이면 함수는 1000000(100만 개)의 동작을 수행합니다.
다시 말하면 O(n2)는 매우 느리게 실행될 것이다. 특히 입력 크기가 매우 크기 때문이다.
대부분의 경우, 우리는 알고리즘을 설명할 것이다. 대상에서 적어도 두 번은 교체해야 할 때, 그것은 두 번의 시간이 있다. 예를 들어 플러그인 for 순환이다.
중복 항목 찾기와 거품 정렬은 두 가지 2차 알고리즘의 예입니다.거품 정렬 (삽입 정렬 및 선택 정렬) 은 통합 정렬과 빠른 정렬의 원시 버전과 유사합니다.비록 속도는 매우 느리지만, 정렬 알고리즘을 배울 때, 그것은 시종 당신이 먼저 배우는 첫 번째 개념이다.그것은 다른 더 복잡한 정렬 알고리즘에 좋은 기초를 다졌다.
거품 정렬은 인접 원소의 순서가 틀리면 반복해서 교환하는 역할을 한다.만약 우리가 무질서한 숫자 그룹을 최소에서 최대로 정렬한다면.기포 정렬법은 숫자의 순서가 정확한지 하나하나 교환을 통해 검사한다.
거품 정렬의 예:

function bubbleSort(arr, n) {
  // double-loop of size n, so n^2
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap (arr, j, j+1);
      }
    }
  }
}

// swap helper method
function swap (arr, first, second) {
  let temp = arr[first];
  arr[first] = arr[second];
  arr[second] = temp;
}

중첩 순환에 대한 우리의 시간 복잡도는 O(n2)이다.
병합 정렬 (수조는 반으로 자르기) 에 비해 거품 정렬은 수조의 모든 원소를 하나하나 훑어보고, 모든 원소가 정확한 위치로 정렬될 때까지 훑어본다. (그리고 정렬을 했더라도 다시 한 번 훑어본다.)
전형적인 용례
Bubble Sort
Insertion Sort
Selection Sort
Find Duplicates (Brute Force)
Find All Possible Ordered Pairs in An Array

지수 시간: O(2n)

Base-2 지수 실행 시간은 입력 크기가 증가함에 따라 계산이 배가된다는 것을 의미한다.
22 => 4
23 => 8
24 => 16
...
2100 => 1,267,650,600,228,229,401,496,703,205,376
보시다시피 n 1만 증가하면 결과는 배로 늘어납니다.기본적으로 이 숫자는 처음부터 매우 낮았는데, 마지막에는 이 숫자가 매우 클 것이다.
대부분의 경우, 실행 시간이 느려지기 때문에 지수 시간을 사용하지 마십시오.이것이 최악이라고 말하는 것은 아니지만, 분명히 이것은 좋지 않다.
피보나치 예

function fib(n) {
  if (n <= 1) {
    return n
  }
  return fib(n - 1) + fib (n - 2)
}

전형적인 용례
Power Set: Finding all the subsets on a set
Fibonacci Number

단계 곱하기 시간: O (n!)

만약 당신이 계승이 어떻게 일을 하는지 알고 있다면 그것은 다음과 같다.
5! = 5 x 4 x 3 x 2 x 1 다시 말하면,
n!=nx(n-1)x(n-2)x(n-3)...x1
입력 크기가 증가함에 따라 운행 시간이 점점 커집니다!나는 개인적으로 곱셈 문제에 부딪히지 않았기 때문에 아래의 링크를 참고로 첨부할 것이다.
전형적인 용례
Permutations

결론

우리는 이 문장이 너로 하여금 큰 O 기호를 더욱 잘 이해하게 할 수 있기를 바란다.이 개념은 매우 중요하다. 왜냐하면 면접에서 해결 방안을 분석하는 큰 O 기호가 자주 필요하기 때문이다.또한 이 점을 이해하면 방법을 제시할 때 어떤 해결 방안의 운행이 더 좋거나 더 나쁜지 알 수 있습니다.만약 당신이 여전히 이해할 수 없다면, 우리는 아래에서 더 많은 자원을 제공하여 당신에게 참고를 제공할 것입니다.

리소스

Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities 👀(스택 오버플로우)

Big-O Cheat Sheet

What is Big O Notation Explained: Space and Time Complexity(FreeCodeCamp)

Big-O notation(위키백과)

8 time complexities that every programmer should know(비디오 및 예제 포함)

스탠퍼드 대학교