2.3. Big-O Notation

이 문서는 영문으로된 내용을 구글 번역기를 활용하여 번역한 내용입니다. 
개인적인 공부 및 추후 다시 볼 수 있도록 하기 위해 개인 블로그에 번역 내용을 옮겨 놓았습니다.
원문과 내용이 다를시 책임지지 않으며, 저작권 문제가 발생시 언제든 삭제 될 수 있습니다. 

Problem Solving with Algorithms and Data Structures using Python by Bradley N. Miller, David L. Ranum is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. 

특정 프로그램이나 컴퓨터와 독립적으로 실행 시간 측면에서 알고리즘의 효율성을 특성화하려고 할 때 알고리즘에 필요한 작업 또는 단계의 수를 정하는 것이 중요합니다. 이 단계들 각각이 계산의 기본 단위로 고려되면, 알고리즘의 실행 시간은 문제를 해결하는 데 필요한 단계의 수로 표현 될 수 있습니다. 적절한 계산 단위를 결정하는 것은 복잡한 문제가 될 수 있으며 알고리즘 구현 방법에 따라 달라집니다.

앞에서 설명한 합계 알고리즘을 비교하기 위한 좋은 기본 계산 단위는 합계를 계산하기 위해 수행 된 대입문의 수를 계산하는 것일 수 있습니다. sumOfN 함수에서 할당문 수는 1 (theSum = 0)과 n (TheSum = theSum + i를 수행 한 횟수)의 값을 더한 값입니다. T(n) = 1 + n 인 함수로 이것을 나타낼 수 있습니다. 매개 변수는 흔히 "문제의 크기"라고 불리며 "T(n)은 크기 n의 문제를 해결하는 데 걸리는 시간, 즉 1 + n 단계"라고 읽을 수 있습니다.

위에 주어진 합계 함수에서 합계의 용어 수를 사용하여 문제의 크기를 나타냅니다. 우리는 첫 번째 100,000 개의 정수의 합이 처음 1,000 개를 합한 것보다 합계 문제의 더 큰 경우라고 말할 수 있습니다. 이 때문에 큰 사건을 해결하는 데 필요한 시간이 소규모 사건보다 더 커지는 것은 합리적으로 보일 수 있습니다. 우리의 목표는 문제의 크기에 따라 알고리즘의 실행 시간이 어떻게 변하는지를 보여주는 것입니다.

컴퓨터 과학자들은이 분석 기술을 한 걸음 더 앞당길 것을 선호합니다. 정확한 연산 횟수는 T(n) 함수의 가장 중요한 부분을 결정하는 것만 큼 중요하지 않습니다. 즉, 문제가 커지면 T(n) 함수의 일부가 나머지 부분을 압도하는 경향이 있습니다. 이 지배적인 용어는 결국 비교를 위해 사용됩니다. 크기 함수의 차수는 n의 값이 증가함에 따라 가장 빠르게 증가하는 T(n)의 부분을 설명합니다. 크기의 순서(order of magnitude)는 흔히 Big-O 표기법 (주문의 경우)이라고하며 O(f(n))로 작성됩니다. 계산의 실제 단계 수에 대한 유용한 근사값을 제공합니다. 함수 f(n)는 원래의 T(n)의 지배적 인 부분을 단순하게 나타냅니다.

위의 예에서 T(n) =1+n 입니다. n이 커지면, 상수 1은 최종 결과에 덜 중요해질 것입니다. T(n)에 대한 근사값을 찾고 있다면 1을 버리고 단순히 실행 시간이 O(n)라고 말할 수 있습니다. 1이 확실히 T(n)에 대해 유의하다는 것을 주목하는 것이 중요합니다. 그러나 n이 커지면 우리의 근사값도 정확하지 않을 것입니다.

또 다른 예로, 일부 알고리즘의 경우 정확한 단계 수는 T(n)=5n2+27n+1005라고 가정합니다. n이 작거나, 1 또는 2라고 할 때, 상수 1005가 함수의 지배적 인 부분 인 것처럼 보입니다. 그러나 n이 커질수록 n2 항이 가장 중요해집니다. 실제로, n이 실제로 클 때, 다른 두 용어는 최종 결과를 결정할 때 수행하는 역할에서 중요하지 않게됩니다. 다시, n이 클수록 T(n)을 근사화하기 위해 다른 용어를 무시하고 5n2에 집중할 수 있습니다. 또한 n이 클수록 계수 5는 중요하지 않습니다. 우리는 함수 T(n)의 크기가 f(n)=n2이거나 간단히 O(n2)라고 말합니다.

합산 예제에서 이를 볼 수는 없지만 때때로 알고리즘의 성능은 단순히 문제의 크기가 아닌 데이터의 정확한 값에 달려 있습니다. 이러한 종류의 알고리즘의 경우 최상의 성능, 최악의 성능 또는 평균 성능과 관련하여 성능을 특성화 해야 합니다. 최악의 경우의 성능은 알고리즘이 특히 저조한 특정 데이터 세트를 나타냅니다. 정확히 동일한 알고리즘에 대한 다른 데이터 세트가 뛰어난 성능을 제공 할 수 있습니다. 그러나 대부분의 경우 알고리즘은 이 두 극단 사이의 어딘가에서 수행됩니다 (평균 사례). 컴퓨터 과학자는 이러한 구분을 이해하여 한 가지 특별한 경우에 의해 잘못 인도되지 않도록하는 것이 중요합니다.

알고리즘을 연구 할 때 아주 많은 양의 크기 함수가 반복해서 나타납니다. 이것들은 표 1에 나와있습니다. 어떤 함수가 T(n) 함수의 지배적인 부분인지를 결정하기 위해, n이 커질 때 서로를 어떻게 비교해야 하는지를 알아야합니다.

f(n)	Name
1	Constant
logn	Logarithmic
n	Linear
nlogn	Log Linear
n2	Quadratic
n3	Cubic
2n	Exponential

그림 1은 표 1의 공통 기능 그래프입니다. n이 작 으면 함수는 서로에 대해 잘 정의되어 있지 않습니다. 어느 것이 지배적인지 알기는 어렵습니다. 그러나 n이 커지면 확연한 관계가 생겨 서로 비교하는 방법을 쉽게 볼 수 있습니다.

마지막 예제로, Listing 2에 표시된 Python 코드 단편이 있다고 가정 해 봅니다. 이 프로그램은 실제로 아무것도 하지 않지만 실제 코드를 취하고 성능을 분석하는 방법을 확인하는 것이 좋습니다.

Listing 2

a=5

b=6

c=10

for i in range(n):

   for j in range(n):

      x = i * i

      y = j * j

      z = i * j

for k in range(n):

   w = a*k + 45

   v = b*b

d = 33

할당 작업의 수는 네 가지 조건의 합계입니다. 첫 번째 용어는 상수 3이며 조각의 시작 부분에 있는 세 개의 할당 문을 나타냅니다. 두 번째 용어는 3n2입니다. 중첩 된 반복으로 인해 n2 번 수행되는 세 가지 구문이 있기 때문입니다. 세 번째 항은 2n이고 두 문장은 n 번 반복됩니다. 마지막으로, 네 번째 항은 상수 1이며 최종 할당 문을 나타냅니다. 이것은 T(n)=3+3n2+2n+1=3n2+2n+4를 제공합니다. 지수를 보면 n2 항이 지배적일 것이므로 이 코드 단편은 O (n2)라는 것을 쉽게 알 수 있습니다. 지배적인 항의 계수뿐만 아니라 다른 모든 항은 n이 커질수록 무시 될 수 있음에 유의하십시오.

그림 2는 위에서 설명한 T(n) 함수와 비교할 때 자주 사용되는 몇 가지 Big-O 함수를 보여줍니다. T(n)은 초기에 3 차 함수보다 크다는 점에 유의하십시오. 그러나 n이 커지면 3 차 함수는 T(n)을 빠르게 따라 잡습니다. n이 계속 증가함에 따라 T(n)이 2 차 함수를 따르는 것을 쉽게 알 수 있습니다.

Self Check

두 개의 파이썬 함수를 작성하여 목록에 있는 최소수를 찾으십시오. 첫 번째 함수는 각 숫자를 목록의 다른 모든 숫자와 비교해야합니다. O(n2). 두 번째 함수는 선형 이어야합니다. O(n).