2.2. What Is Algorithm Analysis?

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

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. 

초보 컴퓨터 과학 학생들이 그들의 프로그램을 서로 비교하는 것은 매우 일반적입니다. 당신은 또한 컴퓨터 프로그램이 매우 유사하게 보일 수있는 것이 일반적이라는 것을 알았을 것입니다. 특히 간단한 것들입니다. 흥미로운 질문이 자주 발생합니다. 두 프로그램이 같은 문제를 해결하지만 다르게 보일 때 한 프로그램이 다른 프로그램보다 나은가요?

이 질문에 답하기 위해 프로그램과 프로그램 사이에 중요한 차이가 있음을 기억해야 합니다. 1 장에서 말했듯이, 알고리즘은 문제를 해결하기 위한 일반적인 단계별 지침 목록입니다. 특정 입력이 주어지면 알고리즘이 원하는 결과를 생성하도록 문제의 모든 인스턴스를 해결하는 방법입니다. 반면에 프로그램은 프로그래밍 언어로 인코딩된 알고리즘 입니다. 프로그래머와 사용 되는 프로그래밍 언어에 따라 동일한 알고리즘에 대한 많은 프로그램이 있을수 있습니다.

이 차이를 더 자세히 알아 보려면 ActiveCode 1에 표시된 함수를 고려하십시오. 이 함수는 익숙한 문제를 해결하여 첫 번째 n 정수의 합을 계산합니다. 알고리즘은 0으로 초기화되는 누산기 변수의 아이디어를 사용합니다. 그런 다음 솔루션은 n 개의 정수를 반복하여 누산기에 각각 더합니다.

RunLoad HistoryShow CodeLens

1

def sumOfN(n):

2

   theSum = 0

3

   for i in range(1,n+1):

4

       theSum = theSum + i

5

6

   return theSum

7

8

print(sumOfN(10))

9

Summation of the First n Integers (active1)

이제 ActiveCode 2의 기능을 살펴 보십시오. 언뜻 보면 이상하게 보일 수 있지만, 추가 검사를 통해 이 기능이 본질적으로 이전 기능과 동일한 기능을 수행하고 있음을 알 수 있습니다. 이유가 분명하지 않은 이유는 코딩이 좋지 않기 때문입니다. 가독성을 높이기 위해 좋은 식별자 이름을 사용하지 않았고, 실제로 필요하지 않은 누적 단계 동안 추가 할당 문을 사용했습니다.

RunLoad HistoryShow CodeLens

1

def foo(tom):

2

    fred = 0

3

    for bill in range(1,tom+1):

4

       barney = bill

5

       fred = fred + barney

6

7

    return fred

8

9

print(foo(10))

10

Another Summation of the First n Integers (active2)

이전에 제기 한 질문은 한 기능이 다른 기능보다 나은지 질문 했습니다. 대답은 당신의 기준에 달려 있습니다. 가독성에 관심이 있다면 sumOfN 함수는 foo 함수보다 확실히 좋습니다. 사실, 당신은 입문 프로그래밍 과정에서 많은 예를 보았을 것입니다. 읽기 쉽고 이해하기 쉬운 프로그램을 작성하는 데 도움이되는 목표 중 하나가 있기 때문입니다. 그러나 이 과정에서는 알고리즘 자체를 특성화하는 데에도 관심이 있습니다. (우리는 확실히 당신이 읽기 쉽고 이해할 수있는 코드를 작성하기 위해 계속 노력하기를 바랍니다.)

알고리즘 분석은 각 알고리즘이 사용하는 컴퓨팅 리소스의 양을 기반으로 알고리즘을 비교하는 것과 관련이 있습니다. 우리는 두 가지 알고리즘을 고려해 볼 수 있기를 원하며, 하나의 알고리즘이 다른 알고리즘보다 더 효율적이라고 말하고 싶습니다. 왜냐하면 그 알고리즘을 사용하는 것이 더 효율적이기 때문입니다. 이 관점에서 위의 두 함수는 매우 유사합니다. 둘 다 근본적으로 동일한 알고리즘을 사용하여 합계 문제를 푸십시오.

이 시점에서 컴퓨팅 리소스가 실제로 의미하는 바를 더 생각하는 것이 중요합니다. 이것을 보는 데에는 두 가지 다른 방법이 있습니다. 한 가지 방법은 알고리즘이 문제를 해결하는 데 필요한 공간이나 메모리의 양을 고려하는 것입니다. 문제 솔루션에 필요한 공간은 일반적으로 문제 인스턴스 자체에 의해 결정됩니다. 그러나 매우 빈번하게, 아주 특정한 공간 요구 사항을 가진 알고리즘이 있으며, 그러한 경우에 우리는 변형을 설명하기 위해 매우 조심할 것입니다.

공간 요구 사항의 대안으로, 우리는 그들이 실행하는 데 필요한 시간을 기준으로 알고리즘을 분석하고 비교할 수 있습니다. 이 측정 값은 알고리즘의 "실행 시간(execution time or running time)”이라고 합니다. 함수 sumOfN의 실행 시간을 측정 할 수 있는 한 가지 방법은 벤치 마크 분석을 하는 것입니다. 즉, 프로그램이 결과를 계산하는 데 필요한 실제 시간을 추적합니다. 파이썬에서는 우리가 사용하고있는 시스템과 관련하여 시작 시간과 종료 시간을 지적함으로써 벤치마킹 할 수 있습니다. time 모듈에는 임의의 시작 지점 이후 현재 시스템 시계 시간을 초 단위로 반환하는 time이라는 함수가 있습니다. 이 함수를 두 번 호출하고 시작과 끝에서 차이를 계산하면 실행을 위한 정확한 초 수 (대부분의 경우 분수)를 얻을 수 있습니다.

Listing 1

import time

def sumOfN2(n):

   start = time.time()

   theSum = 0

   for i in range(1,n+1):

      theSum = theSum + i

   end = time.time()

   return theSum,end-start

Listing 1은 합계 이전과 이후에 임베드된 타이밍 호출을 가진 원래의 sumOfN 함수를 보여준다. 이 함수는 결과와 계산에 필요한 시간 (초)으로 구성된 튜플을 반환합니다. 우리가 함수의 5 번의 호출을 수행한다면, 각각은 처음 10,000 개의 정수의 합을 계산할 때 다음과 같이됩니다 :

>>>for i in range(5):

       print("Sum is %d required %10.7f seconds"%sumOfN(10000))

Sum is 50005000 required  0.0018950 seconds

Sum is 50005000 required  0.0018620 seconds

Sum is 50005000 required  0.0019171 seconds

Sum is 50005000 required  0.0019162 seconds

Sum is 50005000 required  0.0019360 seconds

우리는 시간이 상당히 일정하다는 것을 발견하고 그 코드를 실행하는 데 평균 약 0.0019 초가 걸립니다. 처음 100,000 개의 정수를 더하는 함수를 실행하면 어떨까요?

>>>for i in range(5):

       print("Sum is %d required %10.7f seconds"%sumOfN(100000))

Sum is 5000050000 required  0.0199420 seconds

Sum is 5000050000 required  0.0180972 seconds

Sum is 5000050000 required  0.0194821 seconds

Sum is 5000050000 required  0.0178988 seconds

Sum is 5000050000 required  0.0188949 seconds

>>>

다시 한 번 각 실행에 필요한 시간은 더 길지만 일관성이 있으며 평균 약 10 배의 시간이 더 걸립니다. 1,000,000에 해당하는 n에 대해 다음을 얻습니다.

>>>for i in range(5):

       print("Sum is %d required %10.7f seconds"%sumOfN(1000000))

Sum is 500000500000 required  0.1948988 seconds

Sum is 500000500000 required  0.1850290 seconds

Sum is 500000500000 required  0.1809771 seconds

Sum is 500000500000 required  0.1729250 seconds

Sum is 500000500000 required  0.1646299 seconds

>>>

이 경우, 평균은 이전의 약 10 배로 다시 나타납니다.

이제 합계 문제를 해결하는 다른 방법을 보여주는 ActiveCode 3을 고려해보십시오. 이 함수 sumOfN3은 닫힌 방정식 를 사용하여 반복하지 않고 처음 n 개의 정수의 합계를 계산합니다.

RunLoad HistoryShow CodeLens

1

def sumOfN3(n):

2

   return (n*(n+1))/2

3

4

print(sumOfN3(10))

5

Summation Without Iteration (active3)

n (10,000, 100,000, 1,000,000, 10,000,000 및 100,000,000)에 대해 5 가지 값을 사용하여 sumOfN3에 대해 동일한 벤치 마크 측정을 수행하면 다음과 같은 결과를 얻습니다.

Sum is 50005000 required 0.00000095 seconds

Sum is 5000050000 required 0.00000191 seconds

Sum is 500000500000 required 0.00000095 seconds

Sum is 50000005000000 required 0.00000095 seconds

Sum is 5000000050000000 required 0.00000119 seconds

이 출력에 대해 알아야 할 두 가지 중요한 사항이 있습니다. 첫째, 위에 기록 된 시간은 이전 예보다 짧습니다. 둘째, 그들은 n의 가치에 상관없이 매우 일관성이 있습니다. sumOfN3은 추가되는 정수의 수에 거의 영향을 받지 않습니다.

그러나 이 벤치마킹은 실제로 우리에게 무엇을 말해 줍니까? 직관적으로, 반복적인 솔루션은 일부 프로그램 단계가 반복되고 있기 때문에 더 많은 작업을 수행하고 있는 것으로 보입니다. 이것이 더 오래 걸리는 이유일 수 있습니다. 또한, n의 값을 증가 시키면 반복 솔루션에 필요한 시간이 증가하는 것처럼 보입니다. 그러나 문제가 있습니다. 다른 컴퓨터에서 동일한 기능을 실행하거나 다른 프로그래밍 언어를 사용했다면 다른 결과가 나타날 수 있습니다. 컴퓨터가 오래되면 sumOfN3을 수행하는 데 더 오래 걸릴 수 있습니다.

실행 시간과 관련하여 이러한 알고리즘을 특성화하는 더 좋은 방법이 필요합니다. 벤치 마크 기법은 실제 실행 시간을 계산합니다. 특정 기계, 프로그램, 시간, 컴파일러 및 프로그래밍 언어에 의존하기 때문에 실제로 유용한 측정 값을 제공하지 않습니다. 대신, 우리는 사용되는 프로그램이나 컴퓨터와 독립적인 특성화를 원합니다. 이 측정 값은 알고리즘을 단독으로 판단 할 때 유용 할 수 있으며 구현 전반에서 알고리즘을 비교하는 데 사용할 수 있습니다.