큰 O 기호와 종이컵 케이크

이 글은 나의 회의 강연Fun, Friendly Computer Science을 각색한 시리즈의 첫 번째 글이다.
나는 나쁜 요리사다.사실 이것은 사실이 아닐 수도 있다. 나는 단지 요리를 정말 좋아하지 않기 때문에 여태껏 어떤 정력도 들인 적이 없다.하지만 만약 네가 나 같지 않고 주방에 있는 것을 좋아한다면, 식단이 아닌 비율로 요리하는 데 익숙해질 것이다.
비율에 따라 요리하는 것은 식단을 기억하지 않고 조미료의 비율을 기억하는 것을 말한다.네가 필요로 하는 조미료의 양은 네가 만들고 싶은 음식의 양과 비례하여 변화한다.예를 들어 종이컵 케이크는 4:3:2:1의 비율을 따른다.계란 4개, 밀가루 3컵, 설탕 2컵, 버터 한 잔.
그러면 큰 O 기호와 종이컵 케이크는 어떤 관계가 있습니까?큰 O 기호는 함수나 알고리즘의 상대적인 복잡도를 측정한다.그것은 함수 입력의 크기에 따라 복잡성을 평가한다.
가장 흔히 볼 수 있는 복잡성은 운행 시간을 가리키지만 메모리 소모, 창고 깊이와 다른 자원을 측정하는 데도 쓰일 수 있다.우리는 운행 시간에 중점을 둘 것이다. 왜냐하면 인코딩 면접에서 이것은 그들이 일반적으로 묻는 문제이기 때문이다.우리가 토론한 것은 상대적인 복잡도이기 때문에 실제 입력 크기는 중요하지 않다. 왜냐하면 우리는 코드의 비례 복잡도를 측정하고 싶기 때문이다.우리의 예에서 이 점은 더욱 명확해질 것이다.
그 핵심은 큰 O 기호가 복잡한 수학적 표현이라는 것이다.이것은 이 측정의 함수 표현법이기 때문에 모든'O'는 도형에 표시할 수 있는데 이것은 더욱 시각적이거나 도형적인 사고를 가진 사람들에게 매우 도움이 된다.
만약 네가 시각 효과를 좋아하지 않는다면, 이 글도 코드 예시가 있을 것이다.이 글에서 샘플은 자바스크립트로 작성되어 here 를 찾을 수 있지만, 만약 이 두 언어 중 어느 것에 대해 더 익숙하다면, 나도 Ruby 과 Python 중의 샘플을 가지고 있다.

O（1）

당신이 만날 수 있는 첫 번째 "O"는 O(1)입니다.O(1)는 일정한 운행 시간입니다.입력 크기가 증가함에 따라 코드를 실행하는 시간은 변하지 않습니다.

예를 들어 종이컵 케이크를 만들고 있다면 버터와 설탕을 3분 동안 섞어야 한다.따라서 한 무더기든 두 무더기의 종이컵 케이크를 만들든 버터와 설탕을 섞는 데는 3분이 걸린다.

combineButterAndSugar(batches) {
  const steps = [];
  const butter = {
    ingredient: this.recipeRatios.butter,
    amount: batches * this.recipeRatios.butter.number
  };
  const sugar = {
    ingredient: this.recipeRatios.sugar,
    amount: batches * this.recipeRatios.sugar.number
  };
  steps.push(this.beatWithMixer([butter, sugar], 3));
  steps.push("Combined butter and sugar: O(1)");
  return steps.join("<br/>");
}

O（n）

다음은 O(n)입니다.함수의 운행 시간은 입력 크기와 정비례한다.입력 크기가 증가함에 따라 실행 시간이 선형적으로 증가한다는 것이다.

단일 for 순환이나while 순환은 함수가 O(n)인 좋은 지시기입니다.예를 들어 종이컵 케이크 반죽에 계란을 넣을 때, 우리는 한 번에 계란을 하나 추가한 후에 전동 믹서로 1분간 반죽을 섞어야 한다.따라서 만약에 우리가 종이컵 케이크 한 조각에 4개의 계란이 필요하다면, 그것은 보기에 1) 계란 하나를 추가하고, 1분을 섞고, 2) 계란 하나를 추가하고, 1분을 섞고, 3) 계란 하나를 추가하고, 1분을 섞고, 4) 계란 하나를 추가하고, 1분을 섞는다.이 운행 시간은 사실상 4n이지만 큰 O 기호에 대해서는 계수가 중요하지 않다는 것을 알 수 있습니다.마찬가지로 우리는 상대적인 복잡도와 복잡도를 측정하고 있다. 만약 n이 충분하게 구체적이라면 우리는 계수의 특이성을 증가시킬 필요가 없다.

addEggs(batches) {
  const steps = [];
  const oneEgg = { ingredient: this.recipeRatios.eggs, amount: 1 };
  const butterMixture = { ingredient: "butter mixture" };

  const amount = batches * this.recipeRatios.eggs.number;
  for (let egg = 0; egg < amount; egg++) {
    steps.push(this.beatWithMixer([oneEgg, butterMixture], 1));
  }
  steps.push("Added eggs: O(n)");
  return steps.join("<br/>");
}

O（n^2）

우리의 다음 "O"의 성능은 다소 떨어졌다.O(n^2)는 실행 시간과 입력 크기의 제곱이 비례하여 증가함을 나타낸다.

입력 크기의 제곱과 비례하여 증가하는 것은 흔치 않을 수도 있지만, 실제로는 매우 흔하다.플러그인 순환을 볼 때마다 O(n^2)나 동급 순환을 처리할 가능성이 높다.삽입 순환의 깊이가 증가함에 따라 지수도 증가한다.따라서 2층 깊이에 박힌 순환은 O(n^2), 3층 깊이는 O(n^3), 4층 깊이는 O(n^4)로 추정된다.

combineFlourMixtureAndMilkAndButterMixture(batches) {
  const steps = [];
  const butterMixture = { ingredient: "butter mixture" };
  const flourMixture = { ingredient: "flour mixture" };
  const milk = {
    ingredient: this.recipeRatios.milk,
    amount:
      (batches * this.recipeRatios.milk.number) / (batches * batches)
  };
  steps.push(this.beatWithMixer([butterMixture, flourMixture], 1));
  for (let batch = 0; batch < batches; batch++) {
    for (let portion = 0; portion < batches; portion++) {
      steps.push(this.beatWithMixer([butterMixture, milk], 1));
      steps.push(this.beatWithMixer([butterMixture, flourMixture], 1));
    }
  }
  steps.push("Slowly combined milk, flour mixture, and butter mixture: O(n^2)");
  return steps.join("<br/>");
}

O（2^n）

코드를 실행하는 시간이 입력의 크기에 따라 지수가 증가할 때, 보이는 것은 O(2^n)입니다.이것은 입력 크기의 작은 증가가 운행 시간의 큰 증가를 초래할 수 있음을 의미한다.

페보나치 수를 차례로 계산하는 것은 O(2^n) 알고리즘의 예이다.만약 우리가 피보나치를 위해 생일 파티를 열고 종이컵 케이크에 피보나치 숫자를 칠하고 싶다면, 우리가 점점 더 많은 종이컵 케이크를 칠함에 따라 우리는 지수급의 운행 시간을 보게 될 것이다.(곧 귀속을 소개할 테니 새로운 것이라면 걱정하지 마세요.)

fibonacciFrosting(batches) {
  const numberToFrost = this.calculateFibonacciNumber(batches);
  return `Iced the fibonacci number ${numberToFrost} to all of the cupcakes: O(2^n)`;
}

calculateFibonacciNumber(number) {
  if (number <= 1) {
    console.log("Fibonacci base case!");
    return number;
  }
  return this.calculateFibonacciNumber(number - 1) + this.calculateFibonacciNumber(number - 2);
}

O (대수 n)

마지막으로, 우리는 대수 운행 시간이 있다.나는 O(대수 n)가 O(2^n)의 역이라고 생각한다.지수 성장에서 입력 크기가 증가함에 따라 운행 시간의 증가는 점점 커지고 대수 성장에서 입력 크기가 증가함에 따라 운행 시간의 증가는 점점 작아진다. 큰 입력 크기에 가까운 고정된 운행 시간까지.

나는 이 방면의 코드 예시가 없다. 왜냐하면 나의 종이컵 케이크 비유는 좀 과장되었기 때문이다😬, 그러나 대수 운행 시간은 2진 검색과 같은 분할 알고리즘에서 흔히 볼 수 있다.만약 우리가 대수 운행 시간의 알고리즘을 이용하여 종이컵 케이크를 나누어 주고 싶다면, 우리는 종이컵 케이크를 반으로 썰어 가장 가까운 두 사람에게 건네주고, 수집한 종이컵 케이크를 반으로 썰어 가장 가까운 두 사람에게 건네주고, 모든 사람에게 종이컵 케이크가 하나 있을 때까지 이런 패턴을 계속할 수 있다.

큰 O 기호 사용

만약 당신이 그것을 배울 기회가 없다면, 그 의미의 상하문 단서를 맞추기 어려울 것이다.내가 코드를 작성한 10년 동안 대학 컴퓨터 과학 수업과 면접을 제외하고는 나는 지금까지 큰 O 기호를 사용한 적이 없다.따라서 면접에서 새로운 기회를 얻기 전에 당신의 기억을 갱신할 가치가 있을 수도 있습니다. 면접관이 다른 더 가치 있는 기술이 아니라 CS기초지식을 중시하지 않도록 하기 위해서입니다.
대형 O 기호는 당신의 동업자와 언어를 공유하여 상대적인 코드 성능을 토론하는 데도 사용할 수 있습니다.그러나 만약 당신이 다른'O'와 그것들의 뜻을 기억하지 못한다면 자신이 부족하다고 생각하지 마세요.공유 언어는 좋지만 중첩 순환을 가리키며 성능에 미치는 부정적인 영향에 대해 이야기할 수도 있습니다. 어떤 "O"인지 기억할 필요가 없습니다.🤗