더 복잡해짐

지금까지 우리는 O(1) 일명 상수 시간과 O(n) 일명 선형 시간을 다루었습니다.

상수 시간이 가장 효율적이지만 선형 시간도 알고리즘 복잡성 측면에서 나쁘지 않습니다. 그러나 O(n²)는 꽤 나쁩니다. 케이터링 회사로 돌아가서 작업이 얼마나 빨리 통제 불능 상태가 되는지 확인하겠습니다...

우리 케이터링 회사는 곤경에 처했습니다

우리가 함께 일해 온 회사는 우리의 첫 번째 행사에 만족했지만 마지막 케이터링 작업에 대해 수많은 불만을 받았습니다. 분명히 손님은 우리의 독창적인 Constant Time Soup이 게으르다고 생각하고 더 많은 음식 옵션을 원했습니다.

선형 시간보다 더 나은 경험을 제공하기 위해 둘 사이의 절충점을 찾으려고 노력할 수 있습니다...

또는 우리는 극도로 앙심을 품고 터무니없이 고안된 복수 계획을 부화시킬 수 있습니다!

"케이터링 회사" 회사

그 손님이 케이터링 회사를 운영하는 것이 얼마나 힘든지 안다면 우리가 Constant Time Soup을 사용하고 싶어하는 이유를 이해할 것입니다. 그들이 그 모든 식사를 만들어야 한다면 그들은 우리의 독창성을 인정할 것입니다.

그래서 우리는 사람들에게 각각의 방식으로 행사를 하는 것의 차이점을 가르치는 새로운 회사를 운영할 것입니다! 그게 그들에게 가르쳐 줄거야!

이전과 마찬가지로 이를 매핑하기 위한 유사 코드를 만들어 봅시다.

# n = number of people aka haters

def teach_those_haters_a_lesson (n)

   # we have to teach each hater 
   n.each do |hater|  # O(n)

     # First we have to get each hater to cater a party
     # for all the other haters, using the individual meal method

     idnv_meal_cater_party(all_the_other_haters) # O(n)

     # After that, we let them do the soup way
     # so they can see why it's better!

     soup_cater_party (all_the_other_haters) # O(1)

   end
end

그 계획이 지나치게 비실용적이고 지나치게 복잡한 계획처럼 들린다면 당신이 절대적으로 옳습니다. 개별 식사로 파티를 준비해야 할 뿐만 아니라 모든 손님을 위해 그렇게 해야 합니다! 모든 손님을 위한 전체 별도의 파티!

그래, 수프 파티도 해야 하고 기술적으로 복수 피해자가 우리와 함께 요리하는 동안 식사를 준비할 필요는 없지만, 우리가 할 추가 작업에 비하면 사소한 일입니다. Big O 표기법에서 상수는 어떻게 됩니까?

그것을 생각하는 가장 간단한 방법은 모든 손님을 위해 [거의] 모든 손님을 위한 식사를 준비해야 한다는 것입니다. 즉, O(n) 복잡도 알고리즘(식사 만들기)을 O(n)번 수행합니다. O(n) X O(n)이므로 O(n²)를 얻습니다.

O(n²) 식별

O(n²) 시간 복잡도를 파악하는 쉬운 방법은 중첩 루프입니다. 특히 데이터 세트가 다른 반복 내에서 반복되는 경우입니다.

즉, 중첩된 반복이 모두 O(n²) 시간인 것은 아닙니다. 중첩 루프는 원래 입력 크기와 연관될 필요가 없습니다. 예를 들어 문자열 배열의 각 문자를 고려하는 경우 한 경우에는 배열의 크기(문자열 수)를 보고 다른 경우에는 각 문자열의 길이(아무거나)를 봅니다.

이 두 입력이 반드시 같을 필요는 없기 때문에 별도의 변수가 필요하며 big-O 함수는 O(nk)가 됩니다. 여기서 k는 다른 입력의 크기를 나타냅니다. 개별 문자열의 최대 길이)

k가 상수(또는 최대값이 상수)이면 중첩 루프는 기술적으로 선형 시간 O(n)으로 단순화됩니다. 그러나 입력 크기가 작을수록 더 많은 효과가 나타납니다. n이 무한대에 도달하면 k가 무시할 수 있게 될 수 있기 때문에 실제로 입력하는 크기에서 여전히 큰 차이를 만들 수 있습니다.

다음번

우리는 일반적인 복잡성에 대해 거의 완료했습니다. 다음 시간에는 대수 시간 O(log n)을 살펴보겠습니다. 이는 사촌 O(n log n)입니다.

다음까지...