이제 Big-O 표기법에 대한 기본 개요를 살펴보았으므로 이해를 구축하는 가장 좋은 방법은 가장 일반적인 각 복잡성을 통해 학습하는 것이라고 생각합니다.

파트 2: O(n)

우리가 살펴볼 첫 번째 big-o 함수는 선형 시간이라고도 하는 O(n)입니다.

가상 케이터링 회사

케이터링 회사를 소유하고 있다고 가정해 보겠습니다. 귀하는 최근에 모든 기업 회의 및 행사에 음식을 제공하는 지역 비즈니스와 계약을 체결했습니다!

하지만, 당신은 단순한 케이터링 업체가 아닙니다. 당신도 코더! 그래서 우리가 무엇을 하기 전에 가능한 한 효율적으로 식사를 할 수 있도록 알고리즘을 계획할 것입니다.

유사 코드를 작성해 봅시다(루비에서 가장 좋아하는 이유)

# n = number_of_people

def cater_party (n)
   # whatever we're going to do
end

이 이벤트를 처리할 수 있는 몇 가지 방법이 있지만 참석한 모든 사람을 위해 식사를 만들기로 결정했다고 가정해 보겠습니다.

의사코드를 업데이트하자

# n = number_of_people

def cater_party (n)
   n.each do |person_at_party|
      # plate some chicken
      # plate some side dishes
      # etc
      return full_meal
   end
end

1명이 나오면 1접시
10명이 모이면 10접시를 만들어야 합니다.
10,000명이 모이면 10,000명의 식사를 따로 준비해야 합니다!

행사장에 오는 사람들이 늘어날수록 우리가 만들어야 할 접시도 일정하게 늘어나는 것을 볼 수 있습니다. 이 경우 1인 추가는 식사 1개를 더 의미합니다.

직관적으로 사람 수와 관련하여 작업 부하가 어떻게 증가하는지 확인하는 것은 매우 쉽습니다. 우리의 업무량은 모든 새로운 사람에 대해 일정한 양만큼 증가합니다.

이것은 O(n)으로 표현되는 관계입니다.

상수

케이터링 식사 예를 생각해 보면 우리가 빠뜨린 추가 작업이 많이 있었습니다. 모든 설정은 어떻습니까? 음료를 제공하는 것은 어떻습니까? 저녁 식사와 디저트 접시를 만들어야 한다면?

실제로 케이터링 의사 코드는 다음과 같을 수 있습니다.

# n = number_of_people

def cater_party (n)

   # cook all the food
   # drive to the venue
   # set up 

   n.each do |person_at_party|
      # plate some chicken
      # plate some side dishes
      # do it again for desert
      # get them a drink
      # etc
      return full_meal
   end
end

그런 것들을 고려해야 하지 않겠습니까?

먼저 우리는 big-o에 대해 이야기하고 있으며 big-o는 입력 크기가 증가함에 따라 복잡성이 증가하는 방식만을 설명한다는 점을 기억하십시오.

사람의 수가 우리가 해야 할 설정의 양에 영향을 줍니까? 설마.

그것은 우리 음료에 영향을 미칩니 까? 아니, 그냥 디스펜서를 꺼낼게.

인원수에 따라 1인당 2접시 하는건가요? 이것은 까다롭기 때문에 예라고 말하고 싶을 수도 있지만 실제로 생각해보십시오. 예, 각 사람을 위한 전체 과정을 만드는 것은 두 배로 어렵지만 여전히 한 사람당 작업 증가는 동일할 것으로 예상합니다. 저녁 식사와 디저트를 모두 하나의 "식사"로 생각한다면 다시 1:1 증가로 돌아갑니다.

이 모든 추가 사항은 상수입니다. 그들은 입력 크기에 대해 동일하게 유지되기 때문에 주어진 알고리즘에 대한 기본 big-o 복잡성을 결정할 때 대부분 무시할 수 있습니다.
물론 더 정확하게 하기 위해 추가할 수 있지만 "n"이 커질수록 상수의 효과가 줄어듭니다.

O(n)에 대한 추가 정보

처음에 O(n)을 선형 시간이라고도 합니다. 한 축에 항목 수(n)가 있고 다른 축에 작업 수(O)가 있는 그래프에 O(n)을 플로팅하면 아래와 같은 직선이 표시되기 때문입니다.

다음번

O(n)은 복잡성(주석 코딩뿐만 아니라 전반적으로)과 관련하여 기준선입니다. 아마도 가장 직관적이고 이해하기 가장 쉬운 big-o 기능 중 하나일 것입니다.

다음 시간에는 가장 덜 복잡한 알고리즘에 대한 표기법을 살펴보겠습니다.