처음에 thedukh에 썼습니다.

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
-Wikipedia

소개하다.

비록 당신이 직장 생활에서 큰 O를 영원히 사용하지 않더라도, 그것이 무엇인지 아는 것은 여전히 중요하다.이 개념을 파악하는 것은 매우 가치가 있다. 입력 크기의 변화에 따라 어떤 알고리즘을 어떻게 분류하는지 아는 것은 기술 면접, 인코딩 도전, 성능이 매우 중요한 대형 프로젝트에서 매우 유용하다.
보통 한 문제를 처리할 때 개발자는 하나의 원칙을 따르고 여러 버전에서 특정한 알고리즘의 실현을 찾는다.나 이거 필요해. 일해.
만약 첫 번째 해결 방안이 유효하다면.너무 신기해.우리 그걸로 하자.
만약 없다면, 도대체 무슨 일이 일어났는지, 어떤 것들이 작용할 때까지 바꾸고, 두 번째 해결 방안, 또는 세 번째... 또는 그 다음의 어떤 해결 방안을 선택하십시오.쓸모가 있기만 하면 무엇이든지 좋다.

"그것은 효과가 있다." 때로는 아직 좋지 않다.

하지만 우리가 더 깊이 들어가고 더 자세히 원한다면.만약 우리가 이러한 여러 가지 실현(효과적인 실현)을 비교하고 서로 다른 특징에 따라 그것들을 분류하고 싶다면 어떻게 해야 하는가.만약 우리가 해결 방안의 저효능을 찾아내거나 서로 다른 변체 간의 균형을 논의하고 싶다면 어떻게 해야 하는가.코드 방면에서, 우리는 어떻게 '더 나은' 을 정의합니까?우리는 더 좋은 해결 방안, 더 빠른 해결 방안을 고려하고 있습니까? 아니면 더 적은 자원을 사용하는 해결 방안을 고려하고 있습니까? 아니면 더 읽을 수 있는 해결 방안을 고려하고 있습니까?
대O 표현법은 알고리즘의 입력과 이 알고리즘을 실현하는 데 필요한 시간 간의 관계를 기술하는 방법이다.간단하게 말하면 입력의 크기에 따라 큰 O 기호는 알고리즘의 운행 속도를 알려준다.

정의

대O 표현법은 알고리즘의 성능이나 복잡성을 묘사한다.그것은 입력 계산 알고리즘 내부의 조작수를 바탕으로 이 점을 실현한다.여전히 사람을 곤혹스럽게 하는군, 그렇지?그래, 아래의 그림을 봐라.만약 우리가 특정한 입력 n을 가지고 있다면, 만약 우리가 이 입력의 크기를 늘린다면, 서로 다른 알고리즘의 운행 시간은 달라질 것이다.

다른 부호
만약 네가 이 글을 처음 읽었을 때보다 더 미치겠다면 아래의 예를 보아라.이 면접 문제를 해결합시다.

Write a function sumTo(n) that calculates the sum of numbers 1 + 2 + ... + n.

제일 먼저 생각나는 게 뭐예요?일반적인 해결 방안은 for 순환을 사용하는 것이다.우리는 1에서 n까지의 숫자를 교체한 후에 그것들을 더할 것이다.

function sumTo(n) {
  let sum = 0;Using the for loop w
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

console.log(sumTo(5)) // 1 + 2 + 3 + 4 + 5 = 15

n (입력) 은 여기에서 매우 중요합니다. n을 추가할 때, for 순환으로 인해 자바스크립트는 동작을 하나 더 만들어야 합니다. (자바스크립트는 구화에 다른 숫자를 추가해야 합니다.)
따라서 만약에 우리가 3을 매개 변수로 보내면 for순환은 세 번 실행되고 세 번 덧셈을 할 것이다.만약 5가 매개 변수라면, 덧셈은 5번, 100이 매개 변수라면 100번, 1000... 을 얻으면 100번 호출됩니다.
이 해결 방안은 매개 변수 n에 달려 있고 조작의 수량은 n의 증가에 따라 증가한다.우리는 이 알고리즘의 운행 시간은 입력 O(n)와 직접적으로 관련이 있다고 말할 수 있다.
이제 같은 문제에 대한 또 다른 솔루션을 살펴보겠습니다.

function sumTo(n) {
  return n * (n + 1) / 2;
}

console.log(sumTo(5)); // 5 * (5 + 1) / 2 = 30 / 2 = 15

유한과 무한화, 그리고 왜 이 공식이 유효한지 알고 싶다면 이것link을 확인하세요. proof에 관한 내용을 읽을 수 있습니다.기본적으로 공식 n*(n+1)/2는 1과 n 사이의 모든 숫자의 합을 구한다. 여기에 연산이 얼마나 있습니까?우리는 곱셈이 있고, 그 다음은 덧셈이 있으며, 마지막은 나눗셈이 있기 때문에 우리가 어떤 수를 입력하든지 간에, 우리는 항상 3개의 연산이 있다. (3은 상수이며, 그것은 중요하지 않다고 여겨지기 때문에 우리는 그것을 1로 줄일 수 있다.)그래서 이 알고리즘은 일정한 속도로 운행한다.입력한 내용에 관계없이 이 기능을 실행하는 시간은 항상 O(1)로 유지됩니다.

큰 O의 예

O(1)

만약 결과가 입력 변수에 의존하지 않거나 입력이 실행해야 하는 조작수에 영향을 주지 않는다면 알고리즘은 O(1)에서 실행된다.O(1)는 일반적으로 다른 모든 기호보다 우수하다.너는 위에서 하나의 예를 보았는데, 다음은 몇 가지가 있다.

function sumNumbers(n1, n2) {
  console.log(n1 + n2)
}

function printMultiple(n) {
  for (let i = 0; i < 10; i++) {
    console.log(i * n)
  }
}

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

첫 번째 함수(sumNumbers)는 두 개의 값을 입력(n1과 n2)으로 하는데, 이것은 조작수(함수체에 하나의 조작-가산법만 있음)에 영향을 주지 않기 때문에 실행할 때 입력에 의존하지 않는다.그것은 항상 일정한 시간에 운행한다. O (1).
두 번째 함수 (print Multiple) 는 매우 재미있는 것 같습니다. 우리는 확실히 foor 순환이 있습니다. 순환이 더 높은 운행과 관련이 있는 것을 볼 수 있습니다.이런 상황에서 그렇지 않다. 순환이 10번만 실행되었기 때문에 n을 막론하고 10개의 배수만 출력할 수 있다(우리는 10개의 조작이 있다고 말할 수 있지만 우리는 큰 O 표현식을 간소화할 수 있기 때문에 최종 운행 시간은 다시 O(1)일 것이다.
세 번째 예도 정해진 시간 안에 운행하는 것이다.왜 액세스 그룹은 항상 상수입니까?배열의 구조 방식 때문에 배열의 요소는 연속된 메모리 시퀀스에 있기 때문에 배열의 모든 항목은 공식 - memory address+item size*index를 사용하여 한 번의 조작으로 쉽게 계산할 수 있습니다.

메모리의 그룹 시각화

O(n)

O(n)는 입력의 크기와 정비례하여 성능이 선형적으로 증가하는 알고리즘을 묘사했다.시간의 복잡도는 크기가 증가함에 따라 증가하고, 그것들은 같은 속도로 증가한다.다음은 몇 가지 예입니다.

function loggingNumbers(n) {
  for (let i = 1; i <= n; i++) {
    console.log(n)
  }
}

function loggingNumbers2(n) {
  for (let i = 0; i < n; i++) {
    console.log(n)
  }

  for (let i = 0; i < n; i++) {
    console.log(n)
  }
}

첫 번째 loggingNumbers 메서드는 for 루프가 이 매개변수에 종속되므로 루프가 반복되는 횟수를 제어합니다.만약 우리가 5를 보낸다면 우리는 1에서 5까지의 숫자를 출력할 것이다. 만약 우리가 1에서 10까지 보낸다면, 이와 같이 출력은 입력과 관련이 있기 때문에 이 방법은 선형적으로 증가하는 것을 의미한다. 즉, O (n) 이다.
두 번째 loggingNumbers2 방법은 매우 재미있다. 이것은 두 개의 for 순환이 있고 하나하나 운행한다. (그것들은 끼워 넣은 것이 아니다.)하나는 n으로 운행하고 다른 하나는 그렇기 때문에 최종 운행 시간은 O(2n)이다.아니면 이렇게?마찬가지로 우리는 표현식을 간소화하고 상수를 없애고 O(n)만 운행할 때 얻을 수 있다.

O(
n2{n^2}
n2
).

function multiplicationTable(n) {
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= n; j++) {
      console.log(i * j);
    }
  }
}

여기서 무슨 일이 있었죠?곱셈표 방법은 두 개의 for 순환이 있는데 모든 순환이 n번 교체된다. 이것은 우리가 모두 n*n번 교체를 얻었다는 것을 의미한다.런타임 시 O(
n2
{n^2}
n2
여기에 주의해야 할 것은 플러그인 순환의 운행은 플러그인 순환의 수량과 같다. 만약에 우리가 세 개의 순환이 있다면 운행할 때 O()가 된다.
n3
{n^3}
n3
등등.또한 위의 시각화 도형을 검사하고 실행할 때 두 번 또는 세 번 곡선이 나타나는 속도를 보면 입력이 증가함에 따라 실행할 때 더욱 빠른 속도로 증가하여 알고리즘의 효율이 높지 않다는 것을 의미한다.

대O 표현식 단순화

위에서 말한 바와 같이 loggingNumbers2 방법에서 우리는 해결 방안에서 2를 삭제했다.
왜?
우리 수학적으로 이 문제를 봅시다.만약 n이 무한대까지 증가한다면 상수 2는 알고리즘의 성장률을 바꾸지 않을 것이다. 선형 함수는 여전히 선형으로 증가한다.이것은 상수가 무관하거나 무의미하다는 것을 의미하지 않는다.이것은 단지 큰 O 기호가 상수에 관심이 없다는 것을 의미한다. 왜냐하면 큰 O는 수학 함수의 성장률만 묘사하고 실제 운행 시간이 아니기 때문이다.
여기서 가장 큰 두 가지 규칙은 상수는 중요하지 않다(O(2n)는 O(n), O(10)는 O(10*1))와 비교적 작은 항목은 중요하지 않다(O(n+10)는 O(n)로 변한다. 우리가 n을 무한대로 늘리면 10은 성장률에 큰 영향을 미치지 않는다는 것을 기억하세요.

결론

우리는 이미 큰 O 기호를 정의하여 가장 흔히 볼 수 있는 예를 보여 주었고 왜, 그리고 어떻게 간소화하는지 설명했다.다음 부분에서 대수가 운행할 때 선형 (O (n) 보다 효과적이지만 상수 (O (1) 보다 효율이 낮다는 것을 소개할 것이다.