4장 분석 도구

4.1 이 책에서 사용되는 7가지 함수 

이 절에서는 알고리즘 분석에 사용되는 가장 중요한 7가지 함수에 대해 간단히 설명한다. 

우리는 이 책에서 우리가 하는 거의 모든 분석에 이 7가지 단순 함수만 사용할 것이다. 

사실 이 7가지 함수 중 하나가 아닌 다른 함수를 사용하는 부분에는 

선택임을 나타내기 위해 star( )로 표시할 것이다. 

이 7가지 기본 함수 외에도 

자료 구조 및 알고리즘 분석의 맥락에서 적용되는 

다른 유용한 수학적 사실의 리스트가 부록 A에 수록되어 있다. 

 

4.1.1 상수 함수 

우리가 생각할 수 있는 가장 간단한 함수는 상수 함수(constant function)이다. 

이것은 c = 5, c = 27, 또는 c = 210 같은

어떤 고정 상수 c에 대한 함수 f(n) = c이다. 

즉, 어떤 인수 n에 대하여 상수 함수 f(n)은 c 값을 할당한다. 

즉, n 값이 무엇이든 상관없다;

f(n)은 항상 상수 c와 같아질 것이다. 

 

우리는 정수 함수에 가장 관심이 많으므로 

가장 기본적인 상수 함수는 g(n) = 1이며, 

이것이 이 책에서 사용하는 상수 함수이다. 

다른 상수 함수 f(n) = c는 상수 c배 g(n)로 쓸 수 있음을 주목하자. 

이 경우 f(n) = cg(n)이다. 

 

상수 함수는 단순하기는 하지만, 알고리즘 분석에서 유용한데, 

그 이유는 두 개의 수를 더하거나, 어떤 변수에 값을 할당하거나, 

두 개의 수를 비교하는 것과 같이 컴퓨터에서 기본 연산을 수행하는 데 

필요한 단계의 수를 특징으로 하기 때문이다. 

 

4.1.2 로그 함수 

자료 구조와 알고리즘 분석에서 흥미롭고 때로는 놀라운 점 중 하나는 

어떤 상수 b > 1에 대하여

로그 함수(logarithm function), f(n) = logb n이 어디에나 있다는 것이다. 

이 함수는 다음과 같이 정의된다:

x = logb n if and only if bx = n. 

정의에 의하여, 값 b는 로그의 기본값으로 알려져 있다. 

 

어떤 정수 n에 대하여 로그 함수를 정확히 계산하는 것은 

미적분학의 사용을 포함하지만, 

우리는 좋은 근사치를 사용할 수 있다. 

특히 로건보다 크거나 같은 최소 정수는 쉽게 계산할 수 있는데, 

이 수는 1보다 작거나 같은 수를 얻을 때까지 n을 a로 나눈 횟수와 같기 때문이다. 

예를 들어, 27/3/3 = 1 이므로 log3 27 = 3이다. 

마찬가지로, 64/4/4/4 = 1이므로 log4 64 = 4이고, 

12/2/2/2 = 0.75 ≤ 1이므로 log 2 12에 대한 근사치는 4이다. 

많은 알고리즘에서 일반적인 연산은 

입력을 반복적으로 반으로 나누는 것이기 때문에 

실제로 밑(base)이 2인 근사치는 알고리즘 분석에서 나타난다. 

 

실제로 컴퓨터는 정수를 이진법으로 저장하기 때문에 

컴퓨터 과학에서 로그 함수의 가장 일반적인 밑(base)은 2이다. 

사실 이 밑은 너무 흔하기 때문에 일반적으로 2일 때 생략한다. 

즉, 우리의 경우 logn = log2n이다. 

대부분의 휴대용 계산기에는 LOG로 표시된 버튼이 있지만 

일반적으로 밑이 10인 로그를 계산하기 위한 것이지 

밑이 2인 로그를 계산하기 위한 것은 아니다.

 

로그에는 지수 규칙과 유사한 몇 가지 중요한 규칙이 있다. 

명제 4.1 (로그 규칙):

실수 a > 0, b > 1, c > 0 및 d > 1이 주어졌을 때, 다음이 있다. 

1. logb ac = logb a + logb c

2. logb a/c = logb a - logb c

3. logb ac = clogb a

4. logb a = (logd a)/logd b

5. b^(logd a) = a^(logd b). 

또한 표기법의 약자로서, 함수 (logn)^c를 나타내기 위해 log^c n을 사용한다. 

로그와 지수의 정의에서 모두 이어지는 

위의 각 항등식을 어떻게 도출할 수 있는지를 보여주기 보다는, 

대신 몇 가지 예를 들어 이러한 항등식을 설명하겠다.

 

예제 4.2: 제안 4.1의 로그 규칙의 몇 가지 흥미로운 적용을 다음과 같이 보여준다

(로그의 밑은 2라는 일반적인 규칙을 사용).

• log(2n)= log2 + logn = 1 + logn, by 규칙 1

• log(n/2)= logn - log2= logn - 1= logn - 1, by 규칙 2

• logn^3= 3logn, by 규칙 3

• log2^n= nlog2 = n • 1 = n, by 규칙 3

• log4 n=(logn)/(log4)= (logn)/2, by 규칙 4

• 2^logn= n^log2 = n^1= n, by 규칙 5

실질적인 문제로서, 

규칙 4가 log2n = LOGn/LOG2에 대한 

밑이 10인 로그 버튼인 LOG를 갖는 계산기의 

밑인 2인 로그를 계산하는 방법을 제공한다는 것에 주목한다.

4.1.3 1차 함수

또 다른 단순하지만 중요한 함수는

1차 함수(선형 함수, linear function), f(n)= n이다. 

즉, 입력값 n이 주어지면 1차 함수 f는 n이라는 값을 스스로 할당한다. 

 

이 함수는 알고리즘 분석에서 n개의 원소 각각에 대해 

하나의 기본 연산을 수행해야 할 때마다 발생한다. 

예를 들어, n개의 크기를 가진 배열의 각 원소와 숫자 x를 비교하는 것은 n개의 비교를 필요로 한다.

또한 n개의 객체를 읽는 것 자체가 n개의 연산을 필요로 하기 때문에, 

일차함수는 컴퓨터 메모리에 아직 없는 n개의 객체를 처리하는 

어떤 알고리즘에서도 얻을 수 있는 최적의 실행 시간을 나타낸다.

 

4.1.4 N-Log-N 함수

이 절에서 다음으로 논의하는 함수는 

n-log-n 함수, f(n) = nlogn, 

즉 입력 n에 밑이 2인 로그 n의 n배의 값을 할당하는 함수이다.

 

이 함수는

1차 함수보다 조금 더 빠르게 증가하고

2차 함수보다 훨씬 느리게 증가한다. 

따라서 여러 번 보여주겠지만, 

문제를 푸는 실행 시간을 2차 함수에서 n-log-n으로 향상시킬 수 있다면 

일반적으로 훨씬 더 빨리 실행되는 알고리즘을 갖게 될 것이다. 

 

4.1.5 2차 함수

알고리즘 분석에서 매우 자주 등장하는 또 다른 함수는

2차 함수(quadratic function)인 f(n) = n^2이다. 

즉, 입력값 n이 주어지면 함수 f는 n의 곱을 자기 자신과 할당한다(즉, "n 제곱"). 

 

알고리즘 분석에서 2차 함수가 등장하는 주된 이유는 

중첩 반복문이 있는 알고리즘이 많기 때문인데, 

내부 반복문은 선형 연산 횟수를 수행하고

외부 반복문은 선형 연산 횟수를 수행한다. 

따라서 이러한 경우 알고리즘은 n · n = n^2 연산을 수행한다. 

 

중첩 반복문과 2차 함수

2차 함수는 중첩 반복문의 경우에도 발생할 수 있는데, 

첫 번째 반복문은 한 번의 반복 연산을 사용하고, 

두 번째 반복문은 두 번의 연산을 사용하고, 

세 번째 반복문은 세 번의 연산을 사용한다. 

즉, 연산의 수는 1+2 + 3 +... + (n - 2) + (n - 1) + n이다. 

즉, 이것은 외부 반복문을 반복할 때마다 

반복문 내부에서 수행되는 연산이 하나씩 증가할 때

중첩 반복문이 수행할 총 연산 수이다. 

 

명제 4.3: 임의의 정수 n ≥ 1에 대하여, 

1 + 2 + 3 + ... + (n - 2) + (n - 1) + n = n(n + 1)/2

를 가진다. 

 

그림 4.1: 명제 4.3의 시각적 항등식은 두 개의 "시각적" 정당화를 제공한다. 

두 그림 모두 높이가 1,2,...,n인 단위폭 n 직사각형으로 덮인

전체 면적의 관점에서 항등식을 시각화한다. 

(a)에서 직사각형들은 (n^2)/2 영역의 큰 삼각형(밑변 n 및 높이 n)에 

각각 1/2 영역의 n개의 작은 삼각형(밑변 1 및 높이 1)을 덮는 것으로 표시된다.

(b)에서 n이 짝수일 때에만 적용되는 항등식은

n/2와 높이 n+1의 큰 직사각형을 덮는 것으로 표시된다. 

 

명제 4.3으로부터 배워야 할 교훈은 

내부 반복문의 연산이 한 번씩 증가하도록

중첩 반복문을 갖는 알고리즘을 수행하면, 

총 연산 수는 외부 반복문을 수행하는 횟수로 2차적이라는 것이다. 

즉, 그런 알고리즘은 내부 반복문을 수행할 때마다

n번의 연산을 수행하는 알고리즘보다 약간 나을 뿐이다. 

처음에는 이런 관측이 직관적이지 않은 것처럼 보일 수 있지만,

그림 4.1에서 보는 것처럼 사실이다.

 

4.1.6 3차 함수 및 기타 다항식

입력의 거듭제곱인 함수에 대한 논의를 계속하면서, 

입력값 n에 자신과 n의 곱을 세 번 할당하는 

3차 함수 f(n) = n^3를 고려한다.

이 함수는 알고리즘 분석의 맥락에서 앞에서 언급한

상수, 1차, 2차 함수보다 덜 자주 나타나지만, 가끔 나타난다. 

 

다항식

흥미롭게도 우리가 지금까지 열거한 함수들은

모두 더 큰 종류의 함수인 다항식(polynominal)에 속하는 것으로 볼 수 있다. 

다항식 함수: f(n)=a0 + a1 n+a2 n^2 + a3 n^3 +...+ad n^d의 형태로 이루어진 함수

 

여기서 a0,a1,...,ad는 상수로 다항식의 계수라고 하며, ad는 ≠ 0이다. 

다항식의 차수(degree): 다항식에서 가장 높은 거듭제곱을 나타내는 정수 d

 

예를 들어, 다음 함수들은 모두 다항식이다:

• f(n) = 2 + 5n+ n^2

• f(n) = 1 + n^3

• f(n) = 1

• f(n) = n

• f(n) = n^2.

따라서 우리는 이 책에서 알고리즘 분석에 사용되는 중요한 함수를 4개만 제시한다고 주장할 수 있다. 

하지만 상수, 일차, 이차 함수는 다른 다항식들과 묶기에는 너무 중요하기 때문에 7개라고 계속 말할 것이다. 

일반적으로 차수가 d인 다항식인 주행 시간은 차수가 큰 다항식 주행 시간보다 더 좋다.

 

합

자료 구조와 알고리즘의 분석에서 몇 번이고 나타나는 표기법이 합(summation)인데, ​

 

a와 b는 정수이고 a ≤ b이다.

자료 구조와 알고리즘 분석에서 합은

반복문의 실행 시간이 자연스럽게 합으로 이어지기 때문에 발생한다.

 

합을 사용하면 명제 4.3의 공식을 다음과 같이 다시 쓸 수 있다.

마찬가지로, 우리는 계수 a0, ..., ad로 d의 다항식 f(n)을 쓸 수 있다. 

 

따라서, 합 표기법은 규칙적인 구조를 갖는 증가 항의 합을

간단히 표현하는 방법을 제공한다.

4.1.7 지수 함수

알고리즘 분석에 사용되는 또 다른 함수는

지수 함수(exponential function)인 f(n) = b^n 이다.

b: 밑(base), 양의 상수

인수 n: 지수(expotent)

즉, 함수 f(n)은 밑 b에 자신의 n을 곱한 값을 입력 인수 n에 할당한다. 

알고리즘 분석에서 지수 함수의 가장 일반적인 밑은 b = 2이다. 

예를 들어, 한 번의 연산으로 시작하여 

각 반복에서 수행되는 연산 수를 2배로 늘린 반복문이 있다면, 

n번째 반복에서 수행되는 연산의 수는 2^n이다. 

또한 n개의 비트를 포함하는 정수 단어는

2^n보다 작은 모든 음이 아닌 정수를 나타낼 수 있다. 

따라서 밑이 2인 지수 함수는 상당히 일반적이다. 

지수 함수는 지수 함수(expontent function)라고도 한다.

 

그러나 n 이외에도 다른 지수가 있는 경우가 있으므로 

지수를 다룰 때 유용한 규칙을 몇 가지 알고 있는 것이 좋다. 

특히 다음과 같은 지수 규칙(exponent rule)이 상당히 유용하다.

명제 4.4 (지수 규칙): 양의 정수 a, b, c가 주어졌을 때, 우리는 

1. (b^a)^c= b^(ac)

2. (b^a)(b^c) = b^(a+c)

3. (b^a)/(b^c) = b^(a-c)

를 갖는다. 

 

예를 들어, 우리는 다음을 갖는다:

• 256 = 16^2 = (2^4)^2 = 2^4.2 = 2^8 = 256 (지수 규칙 1)

• 243 = 3^5 = 3^(2+3) = 3^2 · 3^3 = 9·27 = 243 (지수 규칙 2)

• 16 = 1024/64 = 2^10/2^6 = 2^(10-6) = 2^4 = 16 (지수 규칙 3).

 

우리는 지수 함수를 다음과 같이 분수 또는 실수인 지수와 음수인 지수로 확장할 수 있다. 

양의 정수 k가 주어지면, b^(1/k)를 b의 k번째 근,

즉 r^k = b가 되는 수 r로 정의한다. 

예를 들어 5^2 = 25이므로 25^(1/2) = 5이다. 

마찬가지로 27^(1/3) = 3과 16^(1/4) = 2이다. 

이 접근법을 통해 지수 규칙 1로

지수가 분수로 표현될 수 있는 모든 거듭제곱을 정의할 수 있다. 

예를 들어 9^(3/2) = (9^3)^(1/2 )= 729^(1/2) = 27이다. 

따라서 b^(a/c)는 실제로 적분 지수 b^a의 c번째 근에 불과하다.

우리는 x에 점점 더 가까워지는 분수 a/c에 대하여 ba/c 형태의 수열을 계산함으로써 

임의의 실수 x에 대하여 b^x를 정의하기 위하여 지수함수를 더 확장할 수 있다.

임의의 실수 x는 임의의 분수 a/c에 의하여 근사될 수 있으므로,

임의로 b^x에 접근하기 위하여 분수 a/c를 b의 지수로 사용할 수 있다.

예를 들어, 숫자 2^π는 잘 정의되어 있다.

마지막으로 음의 지수 d가 주어지면,

a = 0이고 c = -d인 지수 규칙 3을 적용하는 것에 해당하는

b^d = 1/(b^(-d))를 정의한다.

 

기하합

각 반복이 이전 반복보다 더 긴 곱셈 인자를 갖는 반복문이 있다고 가정하자. 

이 반복문은 다음 명제를 사용하여 분석할 수 있다.

명제 4.5: 임의의 정수 n ≥ 0과 a > 0과 a ≠ 1과 같은 임의의 실수 a에 대하여, 합을 고려한다

(a > 0이면 a^0 = 1이라는 기억하자). 

이 합은 (a^(n+ 1) - 1)/(a - 1)과 같다

명제 4.5와 같은 급수는 a > 1이면

각각의 항이 앞 항보다 기하학적으로 크기 때문에 기하급수(geometric summation)이라고 한다. 

기하급수 or 등비급수: 서로 이웃하는 항의 비가 일정한 수

 

예를 들어, 컴퓨팅 분야에서 일하는 모든 사람은

1+2+4+8+...+2n-1 =2^n - 1

이 n비트를 사용하는 이진법으로 표현할 수 있는

가장 큰 정수라는 것을 알아야 한다. 

4.1.8 성장률 비교

정리하면, 앞서 설명한 알고리즘 분석에 사용된 7가지 공통 함수를 Table 4.1에 각각 순서대로 보여준다.
표 4.1: 함수의 클래스. 여기서 a > 1은 상수라고 가정한다.

상수	로그	1차	n-log-n	2차	3차	지수
1	log n	n	nlogn	n^2	n^3	a^n

이상적으로 우리는 상수나 로그 함수에 비례하는 시간으로 자료 구조 연산을 실행하고, 

우리는 우리의 알고리즘을 1차 또는 n-log-n 시간으로 실행하기를 원한다. 

2차 또는 3차 실행 시간을 갖는 알고리즘은 실용성이 떨어지지만, 

지수 함수적 실행 시간을 갖는 알고리즘은

가장 작은 크기의 입력을 제외한 모든 입력에서 실행할 수 없다. 

7개 함수의 그림은 그림 4.2에 나와 있다.

그림 4.2 알고리즘 분석에 사용된 7가지 기본 함수의 성장률이다. 

우리는 지수 함수에 a = 2인 밑을 사용한다. 

함수들은 주로 기울기로 성장률을 비교하기 위해 로그-로그 차트에 표시된다. 

그런데도 지수 함수는 너무 빨리 성장하여 모든 값을 차트에 표시할 수 없다. 

또한 숫자에 대한 과학적 표기법을 사용한다. 

여기서 aE+b는 a10^b를 나타낸다. 

천장 함수와 바닥 함수

위의 함수들에 대한 추가적인 설명은 순서대로 되어 있다.

로그의 값은 일반적으로 정수는 아니지만

알고리즘의 실행 시간은 수행된 작업의 수와 같은 정수의 양으로 표현된다.

따라서 알고리즘을 분석하는 과정에서

바닥 함수와 천장 함수를 사용하는 경우가 있다.

 

바닥 함수(floor function)은 다음과 같이 정의된다.

•⌊x⌋= x보다 작거나 같은 최대 정수.

 

천장 함수(ceiling function)은 다음과 같이 정의된다.
•⌈x⌉= x보다 크거나 같은 최소 정수.

 

알고리즘 분석

이 책에서 우리는 '좋은' 자료 구조와 알고리즘을 설계하는 데 관심을 갖고 있다. 

자료 구조: 데이터를 체계적으로 정리하고 접근하는 방식

알고리즘: 어떤 작업을 유한한 시간 안에 수행하는 단계적인 절차

컴퓨팅의 핵심은 이런 개념들이지만, 

어떤 자료 구조와 알고리즘을 '좋은' 것으로 분류하기 위해서는 

이를 분석하는 정확한 방법이 있어야 한다.

이 책에서 우리가 사용할 주요 분석 도구는 

알고리즘과 자료 구조 연산의 실행 시간을 특징짓는 것이며, 

공간 사용도 관심사이다. 

컴퓨터 솔루션은 가능한 한 빨리 실행되어야 하고, 

시간은 소중한 자원이므로 실행 시간은 '좋음'의 자연스러운 척도이다.

 

일반적으로 알고리즘이나 자료 구조 방식의 실행 시간은 

입력 크기에 따라 증가하지만, 

같은 크기의 입력에도 차이가 있을 수 있다. 

또한 실행 시간은 알고리즘이 구현, 컴파일, 실행되는

하드웨어 환경과 소프트웨어 환경에 영향을 받는다.

하드웨어 환경 - 프로세서, 클럭 속도, 메모리, 디스크 등에 반영됨

소프트웨어 환경 - 운영체제, 프로그래밍 언어, 인터프리터 등에 반영됨

컴퓨터가 훨씬 빠른 프로세서를 가지고 있거나, 

가상 머신 상에서 실행되는 해석된 구현 대신 

네이티브 머신 코드로 컴파일된 프로그램에서 구현된다면 

다른 모든 요인은 동일하게

동일한 입력 데이터에 대한 동일한 알고리즘의 실행 시간은 더 작아질 것이다. 

그럼에도 불구하고 여러 환경 요인에 의해 발생할 수 있는 차이에도 불구하고 

알고리즘의 실행 시간과 입력 크기 사이의 관계에 초점을 맞추고자 한다. 

 

알고리즘의 실행 시간을 입력 크기의 함수로 특성화하는 데 관심이 있다. 

하지만 이를 측정하는 적절한 방법은 무엇일까?

4.2.1 실험 연구

알고리즘을 구현했다면 

다양한 테스트 입력에 대해 알고리즘을 실행하고 

각 실행에 소요된 실제 시간을 기록함으로써

실행 시간을 연구할 수 있다. 

다행히도 이러한 측정은 

언어나 운영 체제에 내장된 시스템 호출을 사용함으로써

정확한 방법으로 수행될 수 있다.

(예를 들어 System.currentTimeMillis() 메소드를 사용하거나 

프로파일링을 사용하도록 설정된 런타임 환경을 호출한다.)

이러한 테스트는 특정 실행 시간을 특정 입력 크기에 할당하지만 

일반적으로 실행 시간이 입력 크기에 따라 달라짐을 확인하는 데 관심이 있다. 

이러한 의존성을 확인하려면

다양한 크기의 다양한 테스트 입력에 대해 여러 실험을 수행해야 한다. 

그런 다음 알고리즘의 각 실행의 성능을

입력 크기와 동일한 x 좌표, n 및 y 좌표를

실행 시간과 동일한 점 t로 표시하여

그러한 실험의 결과를 시각화할 수 있다(그림 4.3 참조). 

이러한 시각화와 이를 뒷받침하는 데이터를 통해 

입력 크기의 최상의 기능을 실험 데이터에 맞추는 통계 분석을 수행할 수 있다. 

의미를 두려면 이 분석을 통해 좋은 샘플 입력을 선택하고 

알고리즘의 실행 시간에 대한 건전한 통계적 주장을 할 수 있을 만큼 충분히 테스트해야 한다. 

 

그림 4.3: 알고리즘의 실행 시간에 대한 실험 연구 결과

좌표(n, t)가 있는 점은 크기가 n인 입력에서

알고리즘의 실행 시간이 t밀리초(ms)임을 나타낸다. 

 

실행 시간에 대한 실험 연구의 3가지 주요 한계

• 실험은 제한된 테스트 입력 집합에 대해서만 수행할 수 있으므로 

실험에 포함되지 않은 입력의 실행 시간은 제외된다

(그리고 이러한 입력은 중요할 수 있다).

• 실험이 같은 하드웨어와 소프트웨어 환경에서 수행되지 않는 한, 

우리는 두 알고리즘의 실험 실행 시간을 비교하는 데 어려움을 겪을 것이다.

• 우리는 알고리즘의 실행 시간을 실험적으로 연구하기 위해

완전히 구현하고 실행해야 한다.

 이 마지막 요구 사항은 분명하지만,

알고리즘의 실험 분석을 수행할 때 가장 많은 시간이 소요되는 측면일 것이다. 

 

알고리즘의 실행 시간을 분석하는 일반적인 방법

• 가능한 모든 입력을 고려

• 하드웨어와 소프트웨어 환경으로부터 독립적인 방식으로

두 알고리즘의 상대적인 효율성을 평가할 수 있다

• 실제 구현하거나 실험을 실행하지 않고

알고리즘의 높은 수준의 설명을 연구하여 수행할 수 있다. 

 

이 방법론은 알고리즘의 실행 시간을 입력 크기 n의 함수로 특징짓는 함수 f(n)을 

각 알고리즘과 연관시키는 것을 목표로 한다. 

일반적인 함수들은 이 장에서 앞서 언급한 7개의 함수를 포함한다.

4.2.2 기초 연산

위에서 언급한 바와 같이, 실험적 해석은 가치가 있지만, 한계가 있다. 

만약 우리가 특정 알고리즘의 실행 시간에 대한 실험을 수행하지 않고 분석하고자 한다면, 

우리는 높은 수준의 의사 코드에 대해 직접 분석을 수행할 수 있다. 

우리는 다음과 같은 기초 연산들(primitive operation)의 집합을 정의한다.

• 변수에 값을 할당하기

• 메소드 호출

• 산술 연산 수행하기 (예를 들어, 두 개의 숫자를 추가하기)

• 두 개의 숫자를 비교하기

• 배열로 인덱싱하기

• 객체 참조를 따라하기

• 메소드에서 반환하기

 

기초 연산 계산하기

구체적으로, 기초 연산은 실행 시간이 일정한 저수준 명령어에 해당한다. 

각 기초 연산의 구체적인 실행 시간을 파악하는 대신, 

단순히 몇 개의 기초 연산이 실행되는지를 세어보고, 

이 숫자 t를 알고리즘의 실행 시간의 척도로 사용할 것이다.

 

각 기초 연산은 일정한 시간의 명령어에 해당하고 고정된 수의 기초 연산만 존재하기 때문에 

이 연산 카운트는 특정 컴퓨터의 실제 실행 시간과 관련이 있을 것이다. 

이 접근법에서 암시적인 가정은 서로 다른 기초 연산의 실행 시간이 상당히 비슷할 것이라는 것이다. 

따라서 알고리즘이 수행하는 기초 연산의 수 t는 해당 알고리즘의 실제 실행 시간에 비례할 것이다.

 

어떤 알고리즘은 같은 크기의 다른 입력들보다 더 빨리 실행될 수도 있다. 

따라서 알고리즘의 실행 시간을

같은 크기의 모든 입력들에 대한 평균을 구한 입력 크기의 함수로 표현하고자 할 수도 있다. 

불행하게도 그런 평균의 경우(average-case)의 분석은 일반적으로 매우 어렵다. 

입력들의 집합에 확률분포를 정의하는 것이 필요한데, 이것은 종종 어려운 일이다. 

그림 4.4는 입력 분포에 따라 알고리즘의 실행 시간이 

어떻게 최악의 경우와 최악의 경우 사이에 있는지를 개략적으로 보여준다. 

예를 들어, 입력이 실제로 "A"나 "D"의 타입들뿐이라면 어떨까? 

 

그림 4.4: 최상의 경우와 최악의 경우 시간의 차이이다. 

각 막대는 가능한 다른 입력에 대한 어떤 알고리즘의 실행 시간을 나타낸다. 

 

최악의 경우를 중심으로

평균 사례 분석에서는 

일반적으로 주어진 입력 분포를 기반으로 예상 실행 시간을 계산해야 하는데, 

여기에는 보통 정교한 확률 이론이 포함된다. 

따라서 이 책의 나머지 부분에서는 달리 명시하지 않는 한 

알고리즘의 입력 크기 n에 대한 함수로 실행 시간을

최악의 경우(worst case)로 분류할 것이다.

 

최악의 경우 입력을 식별하는 기능만 있으면 되기 때문에

평균 사례 분석보다 최악의 경우 분석이 훨씬 쉽다. 

또한 이 접근 방식은 일반적으로 더 나은 알고리즘으로 이어진다. 

알고리즘이 최악의 경우에 잘 작동하도록 성공의 기준을 만들려면

모든 입력에서 잘 작동해야 한다. 

즉, 항상 경사면을 뛰어올라 연습하는 트랙 스타처럼 

최악의 경우에 대한 설계를 수행하면 

더 강력한 알고리즘 '근육'이 생성된다.

 

4.2.3 점근 표기법

일반적으로 의사 코드 설명 또는 고급 언어 구현의 각 기본 단계는 

소수의 기초 연산에 해당한다(물론 메소드 호출은 제외). 

따라서 의사 코드 단계를 통해

일정 인자까지 실행되는 기초 연산의 수를 추정하는

의사 코드로 작성된 알고리즘을 간단한 분석을 수행할 수 있다

(그러나 의사 코드의 한 줄은 경우에 따라 단계 수를 의미할 수 있으므로 주의해야 한다).

 

분석을 더욱 단순화

알고리즘 분석에서는 작은 세부 사항에 수렁에 빠지기보다는 

'큰 그림' 접근 방식을 취하면서 입력 크기 n의 함수로서 실행 시간의 증가율에 초점을 둔다. 

arrayMax와 같은 알고리즘의 실행 시간은 1.9.2절에 주어진 것처럼 n에 비례하여 증가하며, 

실제 실행 시간은 특정 컴퓨터에 의존하는 n배의 상수 요인임을 알면 충분할 때가 많다.

 

상수 요인을 무시하는 함수에 대한 수학적 표기법을 사용하여 데이터 구조와 알고리즘을 분석한다. 

즉, n의 관점에서 성장률을 결정하는 주요 요인에 해당하는 값에 

입력의 크기인 n을 매핑하는 함수를 사용하여 알고리즘의 실행 시간을 특성화한다.

그러나 우리는 n이 무엇을 의미하는지 공식적으로 정의하지 않고, 

대신 n이 분석하는 알고리즘마다 다르게 정의될 수 있는

입력 "크기"의 선택된 척도를 참조하도록 한다. 

이 방법을 사용하면 실행 시간 함수의 주요 "큰 그림" 측면에 초점을 맞출 수 있다. 

또한 동일한 방법을 사용하여 데이터 구조와 알고리즘의 공간 사용을 특성화할 수 있으며, 

여기서 공간 사용(sace usage)은 사용된 메모리 셀의 총 개수로 정의된다.

"빅오" 표기법

f(n)과 g(n)을 음이 아닌 정수를 실수에 대응시키는 함수라고 하자. 

n ≥ n0에 대하여 f(n) ≤ c · g(n)을 만족하는 

c > 0인 실수 c와 n0 ≥ 1인 정수 n0이 존재하는 경우

f(n)은 O(g(n))라고 한다

이 정의는 "f(n)은 g(n)의 빅오(big-Oh)"로 발음되기 때문에

종종 "빅오(big-Oh)" 표기법이라고도 한다.

또는 "f(n)은 is order of g(n)"이라고 말할 수도 있다.

(이 정의는 그림 4.5에 나와 있다.)
그림 4.5: "big-Oh" 표기법을 보여준다. 

함수 f(n)은 O(g(n))이며,

이는 n ≥n0일 때 f(n) ≤ c · g(n)이기 때문이다.  

 

예제 4.6: 함수 8n - 2는 O(n)이다.
정당성: 빅오 정의에 의해, 

우리는 모든 정수 n ≥n0에 대해

8n-2 ≤ cn이 되는 실수 상수 c > 0과 정수 상수 n0 ≥1을 찾아야 한다.
가능한 선택은 c=8이고 n0 =1이라는 것을 쉽게 알 수 있다.
실제로 이것은 8 이상의 실수는 c에 대해 작용하고 

1 이상의 정수는 n0에 대해 작용하기 때문에 

사용할 수 있는 무한히 많은 선택 중 하나이다

 

big-Oh 표기법을 사용하면 함수 f(n)가 다른 함수 g(n)를 상수까지 

그리고 n이 무한대를 향해 증가함에 따라

점근적(asymptotic) 의미로 "이하"라고 말할 수 있다. 

이 능력은 n ≥n0일 때 점근적인 경우에 대해 "≤"를 사용하여

f(n)을 상수의 g(n)배, c와 비교한다는 사실에서 비롯된다.

 

빅오 표기법을 이용한 실행 시간 특성화

빅오 표기법은 어떤 매개변수 n을 기준으로 

실행 시간과 공간 경계를 특성화하는 데 널리 사용되며, 

이는 문제마다 다르지만 항상 문제의 크기를 나타내는 선택된 척도로 정의된다. 

예를 들어 arrayMax 알고리즘처럼 정수 배열에서 가장 큰 원소를 찾는 데 관심이 있다면 

배열의 원소 수를 n으로 표기해야 한다.

빅오 표기법을 사용하면 어떤 컴퓨터에서든 arrayMax 알고리즘의 실행 시간에 대해

다음과 같은 수학적으로 정확한 문장을 쓸 수 있다. 

예제 4.7: n개의 정수 배열에서 최대 요소를 계산하기 위한

알고리즘 arrayMax는 O(n) 시간 내에 실행된다.

정당성: 각 반복에서 알고리즘 arrayMax가 수행하는 기초 연산의 수는 상수이다. 

따라서, 각 기초 연산은 일정한 시간에 실행되므로, 

n 크기의 입력에서 알고리즘 arrayMax의 실행 시간은 최대 상수 n이라고 할 수 있으며, 

즉 알고리즘 arrayMax의 실행 시간은 O(n)이라고 결론지을 수 있다.

빅오 표기법의 몇 가지 성질

빅오 표기법을 사용하면 상수 요인과 낮은 차수항을 무시하고

함수의 성장에 영향을 미치는 함수의 주요 성분에 초점을 맞출 수 있다.

 

예제 4.8: 5n^4 + 3n^3 + 2n^2 + 4n + 1 is O(n^4). 
정당성: n≥n0 =1 일 때 5n^4 +3n^3 +2n^2 +4n+1 ≤ (5+3+2+4+1)n^4 = cn^4, c = 15
사실, 우리는 어떤 다항식 함수의 증가율을 특징 지을 수 있다. 

 

예제 4.9: 만약 f(n)이 d의 다항식,

즉 f(n) = a0+ a1n+ ... + adnd이고, ad > 0이면, f(n)은 O(nd)이다.
정당성: n ≥ 1에 대하여 1 ≤ n ≤ n^2 ≤ ... ≤ n^d이다.

따라서, a0 +a1 n+a2 n^2 +...+ad n^d ≤(a0 +a1 +a2 +...+ad)n^d. 

그러므로, c = a0 +a1 +...+ad 이고 n0 = 1 으로 정의하므로써 f(n)이 O(n^d)이다.

따라서 다항식에서 가장 높은 차수의 항은 그 다항식의 점근적 증가율을 결정하는 항이다. 

우리는 연습문제에서 빅오 표기법의 몇 가지 추가적인 성질을 고려한다. 

그러나 여기서 알고리즘 설계에 사용된

7가지 기본 함수의 조합에 초점을 맞춘 몇 가지 예를 더 생각해 보겠다.

 

예제 4.10: 5n^2 + 3nlog n+ 2n+ 5는 O(n^2)이다.   
정당성: 5n^2 + 3nlog n + 2n + 5 ≤ (5 + 3 + 2 + 5)n^2 = cn, c = 15

n ≥n0 = 2일 때(n=1일 때 nlog n이 0임에 유의).

 

예제 4.11: 20n^3 + 10n log n + 5는 O(n^3)이다. 
정당성 : n ≥ 1에 대하여 20n^3 + 10n log n + 5 ≤ 35n^3.

 

예제 4.12: 3log n + 2는 O(log n)이다.
정당성 : n ≥ 2의 경우 3 log n + 2 ≤ 5 log n. 
n=1일 때 log n은 0이다.

이것이 우리가 n ≥n0 = 2를 사용하는 이유이다.

 

예제 4.13: 2^(n+2)는 O(2n)이다.
정당성: 2^(n+2) = 2^n · 2^2 = 4·2n; 
따라서 이 경우 c = 4와 n0 = 1을 취할 수 있다.

 

예제 4.14: 2n + 100 log n은 O(n)이다.
정당성: 2n + 100 log n ≤ 102 n, n ≥ n0 = 2; 
따라서 이 경우 c=102를 취할 수 있다.

 

가장 단순한 용어로 함수 특성화

일반적으로, 우리는 함수를 가능한 한 가깝게 특성화하기 위해 빅오 표기법을 사용해야 한다. 

함수 f(n) = 4n^3 + 3n^2가 O(n^5) 또는 심지어 O(n^4)인 것은 사실이지만, 

f(n)이 O(n^3)이라고 말하는 것이 더 정확하다. 

 

또한 상수항과 낮은 차수항을 빅-오 표기법에 포함시키는 것도 맛이 없다고 여겨진다.

예를 들어, 이것은 완전히 맞지만,

함수 2n^2가 O(4n^2 + 6n log n)라고 말하는 것은 유행에 맞지 않다.

대신에 함수를 빅오 중 가장 단순한 용어(simplest terms)로

기술하려고 노력해야 한다.

4.1절에 나열된 7개의 함수는 

알고리즘의 실행 시간과 공간 사용을 특성화하기 위해 

big-Oh 표기법과 함께 사용되는 가장 일반적인 함수이다. 

실제로 우리는 일반적으로 이 함수들의 이름을 사용하여 알고리즘의 실행 시간을 나타낸다. 

예를 들어, O(n^2) 시간에 실행되므로 

최악의 경우 4n^2 + n log n에서 실행되는 알고리즘을

2차 시간(quadratic-time) 알고리즘이라고 한다. 

마찬가지로 최대 5n + 20 log n + 4에서 시간에 실행되는 알고리즘을

선형 시간(linear time) 알고리즘이라고 한다.

빅오메가

빅오 표기법이 함수가 다른 함수보다

작거나 같다고 말하는 점근적인 방법을 제공하는 것처럼, 

다음 표기법은 함수가 다른 함수보다

"더 크거나 같은" 속도로 증가한다고 말하는 점근적인 방법을 제공한다.

 

f(n)과 g(n)을 음이 아닌 정수를 실수에 대응시키는 함수라고 하자. 

만약 g(n)이 O(f(n))이면 f(n)은 Ω(g(n)이다.

(f(n)는 g(n)의 빅오메가(big-Omega)라고 발음한다.)

즉, n ≥ n0에 대하여 f(n) ≥ c · g(n)을 만족하는

c > 0인 실수 상수 c와 n0 ≥ 1인 정수 상수 n0이 존재한다.

 

이 정의를 통해 한 함수가 상수항까지

다른 함수보다 크거나 같다고 점근적으로 말할 수 있다.

 

예제 4.15: 3nlog n + 2n is Ω(n log n). 
정당성: n ≥ 2의 경우 3n log n + 2n ≥ 3n log n.

 

빅테타

또한 두 함수가 상수항까지 같은 속도로 성장한다고 말할 수 있는 표기법이 있다. 

만약 f(n)이 O(g(n)이고 f(n)이 Ω(g(n)이라면, f(n)을 θ(g(n))라고 한다. 

(f(n)은 g(n)의 빅세타(big-Theta)라고 발음한다.)

즉, n ≥ n0에 대해  c'g(n) ≤ f(n) ≤ c''g(n)을 만족하는

c'>0, c''>0을 만족하는 실수 상수 c', c'',

n0 ≥1을 만족하는 정수 상수 n0이 존재한다.

예제 4.16: 3 n log n + 4n + 5log n는 θ(n log n)이다.
정당성 : n ≥ 2에 대하여

3n log n ≤ 3n log n + 4n + 5n log n ≤ (3 + 4 + 5)n log n

 

4.2.4 점근적 분석

동일한 문제를 해결하는 두 알고리즘, 

즉 실행 시간이 O(n)인 알고리즘 A와 실행 시간이 O(n^2)인 알고리즘 B가

이용 가능하다고 가정하자.

어떤 알고리즘이 더 나은가? 

우리는 n이 O(n^2)라는 것을 알고 있는데, 

이것은 알고리즘 A가 알고리즘 B보다 점근적으로 더 낫다는 것을 의미하지만, 

n의 값이 작으면 B가 A보다 실행 시간이 더 낮을 수도 있다.

우리는 빅오 표기법을 사용하여 점근 성장률로 함수의 클래스를 정렬할 수 있다. 

우리의 7가지 함수는 아래의 순서에서 증가 속도에 의해 정렬된다. 

즉, 함수 f(n)이 순서에서 함수 g(n)보다 앞에 있으면, f(n)은 O(g(n))이다:
1  logn  n  nlogn  n^2  n^3  2^n.

우리는 그림 4.2에 몇 가지 중요한 함수의 증가율을 보여준다.
표 4.2: 알고리즘 분석에서 기본 함수의 선택값.

n	logn	n	nlogn	n^2	n^3	2^n
8	3	8	24	64	512	256
16	4	16	64	256	4,096	65,536
32	5	32	160	1,024	32,768	4,294,967,296
64	6	64	384	4,096	262,144	1.84 × 10^19
128	7	128	896	16,384	2,097,152	3.40 × 10^38
256	8	256	2,048	65,536	16,777,216	1.15 × 10^77
512	9	512	4,608	262,144	134,217,728	1.34 × 10^154

 

표 4.3에서 점근적 관점의 중요성을 자세히 설명한다.

이 표는 알고리즘에 의해 1초, 1분, 1시간 안에 처리되는

입력 인스턴스에 대해 허용되는 최대 크기에 대해 설명한다.

점근적으로 더 빠른 알고리즘에 대한 상수 요인이 더 나쁘더라도

점근적으로 더 빠른 알고리즘에 의해 장기적으로 극복되기 때문에

좋은 알고리즘 설계의 중요성을 보여준다.

 

표 4.3: 마이크로초 단위로 측정된 다양한 실행 시간에 대해

1초, 1분, 1시간 안에 해결할 수 있는 문제의 최대 크기. 

실행 최대 문제 크기(n)	1초	1분	1시간
400n	2,500	150,000	9,000,000
2n^2	707	5,477	42,426
2^n	19	25	31

 

 

그러나 좋은 알고리즘 설계의 중요성은

주어진 컴퓨터에서 효과적으로 해결할 수 있는 수준을 뛰어 넘는다.

표 4.4에 나타난 바와 같이 하드웨어에서 극적인 속도 향상을 달성하더라도

여전히 점근적으로 느린 알고리즘의 단점을 극복할 수 없다.

이 표는 주어진 실행 시간을 가진 알고리즘이

이전보다 256배 빠른 컴퓨터에서 실행된다고 가정할 때

어떤 고정된 시간 동안 달성할 수 있는 새로운 최대 문제 크기를 보여준다.

 

표 4.4: 이전보다 256배 빠른 컴퓨터를 사용하여

고정된 시간 내에 해결할 수 있는 문제의 최대 크기를 늘린다.

각 항목은 이전 최대 문제 크기인 m의 함수이다.

실행 시간	새로운 최대 문제 크기
400n	256m
2n^2	16m
2^n	m+8

 

4.2.5 빅오 표기법을 사용하여

알고리즘을 분석할 때 빅오 표기법을 사용하는 경우를 예로 든 다음, 

그것의 사용과 관련된 몇 가지 문제를 간단히 논의하자. 

 

일반적으로 빅오는 이미 "작거나 같은" 개념을 나타내기 때문에 

"f(n) ≤ O(g(n))"라고 말하는 것은 좋지 않은 것으로 여겨진다. 

마찬가지로, 비록 일반적이지만 

"O(g(n) = f(n)"라는 문장을 이해할 방법이 없으므로 

"f(n) = O(g(n)"라고 말하는 것은 완전히 옳지는 않다.

또한 "f(n) ≥ O(g(n)" 또는 "f(n) > O(g(n))"라고 말하는 것도

빅오의 g(n)는 f(n)에 상한을 표현하기 때문에 완전히 잘못된 것이다.

 

"f(n)는 O(g(n))이다"라고 말하는 것이 가장 좋다.

 

수학적으로 좀 더 기울어진 것에 대해서는, 

"f(n) ∈ O(g(n))"라고 말하는 것이 정확한데,

빅오 표기법은 엄밀히 말하면 전체 함수 집합을 가리키는 것이기 때문이다.

 

이 책에서는 빅오 표기가 "f(n)은 O(g(n)이다"이라고 계속 제시할 것이다.

이러한 해석을 하더라도

빅오 표기로 산술 연산을 사용할 수 있는 방법에는 상당한 자유가 있으며

이러한 자유로 인해 어느 정도의 책임이 뒤따른다.

 

몇 가지 주의사항

1. 빅오 및 관련 표기법의 사용은 이들이 "숨긴" 일정한 요인이 매우 클 경우 

다소 오해의 소지가 있을 수 있다는 점에 주목한다.

 

예를 들어 함수 10^100 · n이 O(n)인 것은 맞지만, 

이것이 실행 시간이 10n logn인 알고리즘과 비교되는 알고리즘의 실행 시간이라면, 

선형 시간 알고리즘이 점근적으로 더 빠르더라도 O(n logn) 시간 알고리즘을 선호해야 한다. 

이러한 선호도는 많은 천문학자들이 상수 요인 10^100을 "하나의 구골"이라고 부르며, 

관측 가능한 우주의 원자 수에 대한 상한으로 믿고 있기 때문이다. 

따라서 이 숫자를 입력 크기로 하는 실제 문제는 결코 발생하지 않을 것이다. 

 

2. 빅오 표기법을 사용할 때에도 

적어도 상수 요인과 우리가 "숨긴" 낮은 차수항을 어느 정도 염두에 두어야 한다

위의 관찰은 무엇이 "빠른" 알고리즘을 구성하는지에 대한 문제를 제기한다. 

일반적으로 O(n logn) 시간에서 실행되는 모든 알고리즘은 

(합리적인 상수 계수를 가진) 효율적인 것으로 간주되어야 한다. 

심지어 O(n^2) 시간 방법도 어떤 맥락에서는 충분히 빠를 수 있다. 

하지만 O(2^n) 시간에서 실행되는 알고리즘은 거의 절대 효율적이라고 간주되어서는 안 된다.

지수 실행 시간

체스 게임의 발명가에 대한 유명한 이야기가 있다. 

그는 왕에게 보드의 첫 번째 제곱 값으로 쌀 1알, 두 번째 제곱 값으로 2알, 

세 번째 곡물 4알, 네 번째 곡물 8알 등을 지급하라고만 요청했다. 

왕이 지불해야 할 쌀알의 수를 정확하게 계산하기 위한 프로그램을 작성하는 것은 

프로그래밍 기술의 흥미로운 시험이다. 

사실, 이 수를 하나의 정수 값으로 계산하기 위해 작성된 자바 프로그램은 

(비록 런타임 기계는 불평하지 않을지라도) 정수 오버플로를 발생시킨다. 

이 수를 정확하게 정수로 나타내려면 BigInteger 클래스를 사용해야 한다.

따라서 효율적인 알고리즘과 비효율적인 알고리즘을 구별해야 한다면, 

다항식 시간에 실행되는 알고리즘과

지수 시간에 실행되는 알고리즘을 구별하는 것은 당연하다. 

즉, 어떤 상수 c > 1에 대해 실행 시간이 O(n^c)인 알고리즘과 

어떤 상수 b > 1에 대해 실행 시간이 O(b^n)인 알고리즘을 구별하자. 

이 절에서 논의한 많은 개념과 마찬가지로, 

이 역시 O(n^100) 시간에 실행되는 알고리즘이

"효율적"이라고 간주되어서는 안 될 것이기 때문에 

"소금 낟알"과 함께 고려해야 한다. 

그렇다고 하더라도, 다항식 시간과 지수 시간 알고리즘의 구별은

다루기 쉬운 강력한 척도로 여겨진다.

정리하자면, 빅오, 빅오메가, 빅세타의 점근적 표기법은 

우리가 자료 구조와 알고리즘을 분석하는 데 편리한 언어를 제공한다. 

앞서 언급했듯이 이 표기법들은 우리가 낮은 수준의 세부 사항이 아니라 

'큰 그림'에 집중할 수 있도록 해주기 때문에 편리함을 제공한다.

 

점근 알고리즘 분석의 두 가지 예

우리는 같은 문제를 풀지만

실행 시간이 다소 다른 두 알고리즘을 분석함으로써

이 절을 마무리하고자 한다. 

우리가 관심을 가지는 문제는

수열의 소위 누적 평균(prefix average)을 계산하는 것이다. 

즉, n개의 수를 저장하는 배열 X가 주어졌을 때, 

우리는 i = 0,..., n - 1에 대하여

A[i]가 원소 X[0],..., X[i]의 평균이 되도록 배열 A를 계산하고자 한다,

누적 평균 계산은 경제학과 통계학에서 많은 응용이 있다. 

예를 들어, 뮤추얼 펀드의 연도별 수익률을 고려할 때, 

투자자들은 일반적으로 펀드의

최근 1년, 최근 3년, 최근 5년 및 최근 10년의 연평균 수익률을 보기를 원할 것이다. 

마찬가지로, 매일 웹 사용 로그 스트림이 주어지면 

웹 사이트 관리자는 다양한 기간 동안의 평균 사용 추세를 추적하기를 원할 수 있다.

2차 시간 알고리즘

누적 평균 문제에 대한 우리의 첫 번째 알고리즘인 

prefixAverages1은 코드 조각 4.1에 나와 있다. 

정의에 따라 A의 모든 요소를 개별적으로 계산한다.

코드 조각 4.1: 알고리즘 prefixAverages1.   

Algorithm prefixAverages1(X):

      Input: An n-element array X of numbers.

      Output: An n-element array X of numbers such that A[i] is

          the average of elements X[0],....,X[i].

    Let A be an array of n numbers.

    for i ← 0 to n - 1 do

        a ← 0

        for j ← 0 to i do

            a ← a + X[j]

        A[i] ← a / (i + 1)

     return array A

 

prefixAverages1 알고리즘을 분석해 보겠다.
• A 배열을 처음과 끝에서 초기화하고 되돌리는 연산은 

요소당 일정한 수의 기초 연산으로 수행할 수 있으며

O(n) 시간이 걸린다.

• 반복문에는 두 개의 for문이 중첩된 것이 있으며, 각각 카운터 i와 j에 의해 제어된다. 

카운터 i에 의해 제어되는 외부 반복문의 본문은 i = 0,...,n - 1에 대해 n번 실행된다. 

따라서 문장 a = 0과 A[i] = a/(i+ 1)은 각각 n번 실행된다. 

이 두 문장과 카운터 i의 증분 및 테스트는 n, 

즉 O(n) 시간에 비례하는 많은 기초 연산에 기여한다는 것을 의미한다.

• 카운터 j에 의해 제어되는 내부 반복문 본체는

외부 반복문 카운터 i의 전류 값에 따라 i+1번 실행된다. 

따라서 내부 반복문의 문장 a = a + X[j]는 1 + 2 + 3 +... +n번 실행된다. 

명제 4.3을 상기시킴으로써, 

1 + 2 + 3 +... +n, = n(n + 1)/2임을 알 수 있으며, 

이는 내부 반복문의 문장이 O(n^2) 시간에 기여함을 의미한다. 

증가 및 테스트 카운터 j와 관련된 기초 연산에 대해서도 유사한 논증을 수행할 수 있으며, 

이 역시 O(n^2) 시간이 소요된다.

알고리즘 prefixAverages1의 실행 시간은 세 항의 합으로 주어진다. 

첫 번째 항과 두 번째 항은 O(n)이고 세 번째 항은 O(n^2)이다. 

명제 4.9를 간단히 적용하면 prefixAverages1의 실행 시간은 O(n^2)이다.

 

선형 시간 알고리즘

누적평균을 보다 효율적으로 계산하기 위해 

두 개의 연속적인 평균 A[i - 1]과 A[i]가 유사하다는 것을 관찰할 수 있다: 

A[i - 1] = (X[0] + X[1] + ... + X[i - 1])/i

A[i] = (X[0] + X[1] + ... + X[i - 1] + X[i]/(i + 1).

 

누적합 X[0] + X[1] + ... + X[i]를 Si로 표시하면 

누적평균을 A[i] = Si/(i + 1)로 계산할 수 있다. 

X 배열을 반복문으로 스캔하는 동안 현재의 누적합을 쉽게 추적할 수 있다. 

이제 코드 조각 4.2에서 알고리즘 prefixAverages2를 제시할 준비가 되었다.
코드 조각 4.2: 알고리즘 prefixAverages2. 

Algorithm prefixAverages2(X):

      Input: An n-element array X of numbers.

      Output: An n-element array X of numbers such that A[i] is

          the average of elements X[0],....,X[i].

    Let A be an array of n numbers.

    s ← 0

    for i ← 0 to n - 1 do

       s ← s + X[j]

       A[i] ← s / (i + 1)

    return array A

 

알고리즘 prefixAverages2의 실행 시간 분석은 다음과 같다:

• A 배열을 처음과 끝에서 초기화하고 되돌리는 작업은 

요소당 일정한 수의 기초 연산으로 수행할 수 있으며 O(n) 시간이 걸린다.

• 변수를 초기화하는 데는 O(1) 시간이 걸린다.

• 카운터 i에 의해 제어되는 for문이 하나 있다. 

반복문 본문은 i = 0,...,n - 1에 대해 n번 실행된다. 

따라서 문장 s = s + X[i] 및 A[i] = s/(i+ 1)은 각각 n번 실행된다. 

이 두 문장과 카운터 i의 증분 및 테스트가 n, 

즉 O(n) 시간에 비례하는 많은 기본 연산에 기여한다는 것을 의미한다.

알고리즘 prefixAverages2의 실행 시간은 세 항의 합으로 주어진다. 

첫 번째 항과 세 번째 항은 O(n)이고 두 번째 항은 O(1)이다. 

명제 4.9를 간단히 적용하면 prefixAverages2의 실행 시간은 O(n)이며, 

이는 2차 시간 알고리즘 prefixAverages1보다 훨씬 좋다.

4.2.6 연산 능력에 대한 재귀적 알고리즘

알고리즘 분석의 더 흥미로운 예로 

임의의 음이 아닌 정수인 n으로 숫자 x를 올리는 문제를 생각해 보겠다. 

즉, p(x,n) = x^n으로 정의되는

거듭제곱 함수(power function) p(x,n)를 계산하고자 한다. 

이 함수는 선형 재귀를 기반으로 한 즉각적인 재귀적 정의를 가지고 있다. 

 

이 정의는 바로 O(n) 메소드 호출을 사용하여

p(x,n)를 계산하는 재귀적 알고리즘으로 이어진다. 

그러나 다음과 같은 대체 정의를 사용하여 

제곱 기법을 사용하는 선형 재귀를 기반으로 하여

더 빠르게 거듭제곱 함수를 계산할 수 있다:

이 정의의 작동 방식을 설명하려면 다음 예제를 고려한다: 
2^4 = 2^((4/2)2) = (2^4/2)^2 = (2^2)^2 = 4^2 = 16

2^5 = 2^(1 + (4/2)*2) = 2*(2^4/2)^2 = 2*(2^2)^2 = 2(4^2) = 32 

2^6 = 2^((6/2)2) = (2^6/2)^2 = (2^3)^2 = 8^2 = 64

2^7 = 2^(1 + (6/2)2) = 2*(2^6/2)^2 = 2*(2^3)^2 = 2(8^2) = 128.

 

이 정의는 코드 조각 4.3의 알고리즘을 제안한다.

코드 조각 4.3: 선형 재귀를 사용하여 거듭제곱 함수를 계산한다. 

Algorithm Power(x, n):

      Input: A nunber x and integer n ≥ 0

      Output: The value x^n

      if n = 0 then

          return 1

      if n is odd then

           y ← Power(x, (n - 1)/2)

          return x · y · y

      else

           y ← Power(x, n/2)

          return y · y

 

알고리즘의 실행 시간을 분석하기 위해 

Power(x, n) 메소드의 각 재귀 호출은 지수 n을 2로 나누는 것을 관찰한다. 

따라서 O(n)이 아닌 O(logn) 재귀 호출이 있다. 

즉, 선형 재귀와 제곱 기법을 사용하여 

멱함수 계산을 위한 실행 시간을 O(n)에서 O(logn)으로 줄이는 것은 큰 개선이다.

 

4.3. 간단한 정당화 기법

때때로 우리는 알고리즘이 옳다는 것을 증명하거나

빠르게 실행된다는 것을 보여주는 것과 같은 주장을 하고 싶을 것이다. 

그런 주장을 엄밀하게 하기 위해서는 수학적 언어를 사용해야 하고, 

그런 주장을 뒷받침하기 위해서는 우리의 진술을 정당화하거나 증명(prove)해야 한다. 

다행히 이렇게 하는 데는 몇 가지 간단한 방법이 있다.

 

4.3.1 예를 들어

어떤 주장들은 "집합 S에 성질 P를 갖는 원소 x가 있다"는 일반적인 형태이다. 

그러한 주장을 정당화하기 위해서,

우리는 성질 P를 갖는 S의 특정한 x만 생성하면 된다. 

마찬가지로, 어떤 믿기 어려운 주장들은

"집합 S의 모든 원소 x는 성질 P를 갖는다"는 일반적인 형태이다. 

그러한 주장이 거짓임을 정당화하기 위해서,

우리는 성질 P를 갖지 않는 특정한 x만 S로부터 생성하면 된다. 

그러한 경우를 반례(counterexample)라고 한다.

 

예제 4.17: Amongus 교수는 i가 1보다 큰 정수일 때,

2^i - 1 형태의 모든 수는 소수라고 주장한다. 

Amongus 교수는 틀렸다.

정당화: Amongus 교수가 틀렸다는 것을 증명하기 위해, 우리는 반례를 찾는다. 

2^4 - 1 = 15 = 3 · 5이다.

 

4.3.2 "반대" 공격

또 다른 일련의 정당화 기법은 부정적인 것의 사용을 포함한다. 

두 가지 주요한 방법은 대위법(contrapositive)과 모순(contradiction)의 사용이다. 

대위법의 사용은 부정적인 거울을 통해 보는 것과 같다. 

"p가 참이면 q는 참이다"라는 문장을 정당화하기 위해, 

우리는 "q가 참이 아니면 p는 참이 아니다"라고 정의한다. 

논리적으로 이 두 문장은 같지만, 

첫 번째 문장의 대위법이라고 불리는 후자가 더 쉽게 생각될 수 있다.

 

예제 4.18: a와 b를 정수라고 하자. 

ab가 짝수이면 a는 짝수이고 b는 짝수이다.

정당화:이 주장을 정당화하기 위해,

"a가 홀수이고 b가 홀수이면, ab는 홀수이다"라는 대위법을 생각해 보자. 

따라서, 어떤 정수 i와 j에 대하여 a = 2i + 1이고, b = 2j + 1이라고 가정한다. 

그러면 ab = 4ij + 2i + 2j + 1 = 2(2ij + i + j) + 1이므로, ab은 홀수이다.  

앞의 예는 대위적 정당화 기술의 사용을 보여주는 것 외에도, 

드모르간의 법칙(DeMorgan's Law)의 적용도 포함하고 있다. 

이 법칙은 "p or q" 형태의 진술의 부정이 "not p and not q"라고 진술하기 때문에 

부정을 처리하는 데 도움이 된다. 

마찬가지로, "p and q" 형태의 진술의 부정이 "not p or not q"라고 진술한다

 

모순

또 다른 부정적인 정당화 기법은 모순에 의한 정당화인데, 

이는 종종 드모르간의 법칙을 사용하기도 한다. 

모순 기법에 의한 정당화를 적용할 때, 

우리는 먼저 q가 거짓이라고 가정한 다음 

이 가정이 모순(예를 들어, 2 ≠ 2 또는 1 > 3)으로 이어진다는 것을 보여줌으로써

진술 q가 참임을 증명한다. 

이러한 모순에 도달함으로써

q가 거짓이라는 일관된 상황이 존재하지 않음을 보여주므로 q가 참이어야 한다. 

물론 이러한 결론에 도달하기 위해서는

q가 거짓이라고 가정하기 전에 우리의 상황이 일관적인지 확인해야 한다.

 

예제 4.19: a와 b를 정수라고 한다. 

만약 ab가 홀수이면, a는 홀수이고 b는 홀수이다.

 

정당화: ab이 홀수라고 하자.

우리는 a가 홀수이고 b가 홀수임을 보이고자 한다. 

모순에 이르게 할 희망으로, 그 반대, 즉 a가 짝수이거나 b가 짝수라고 가정하자. 

사실, 일반성의 상실 없이, 우리는 a가 짝수라고 가정할 수 있다(b의 경우는 대칭이므로). 

그러면 어떤 정수 i에 대하여 a = 2i이다.

따라서, ab = (2i)b = 2(ib), 즉 ab는 짝수이다. 

그러나 이것은 모순이다: ab은 홀수이면서 동시에 짝수일 수 없다. 

따라서 a는 홀수이고, b는 홀수이다.

4.3.3 귀납법 및 루프 불변성

우리가 흐르는 시간이나 공간 경계에 대해 주장하는 대부분의 내용은 정수 매개변수 n을 포함한다

(일반적으로 문제의 "크기"에 대한 직관적인 개념을 나타낸다). 

더욱이, 이러한 주장들의 대부분은 "모든 n ≥ 1에 대하여" 

어떤 문장 q(n)이 참이라고 말하는 것과 같다. 

이것은 무한히 많은 수들의 집합에 대한 주장이므로, 

우리는 이것을 직접적인 방식으로 완전히 정당화할 수 없다.

 

귀납법

그러나 우리는 종종 귀납법(induction)을 사용하여 위와 같은 주장을 참이라고 정당화할 수 있다. 

이 기술은 임의의 특정한 n ≥ 1에 대하여 참이라고 알려진 것으로 시작하여 

궁극적으로 q(n)이 참임을 보여주는 유한한 함축 순서가 있음을 보여주는 것과 같다. 

1. n = 1에 대하여

(그리고 어떤 상수 k에 대하여 다른 값 n = 2,3,..., k 도 있을 수 있다.)

q(n)이 참임을 보여줌으로써 귀납법에 의한 정당화를 시작한다. 

2. 귀납법 "단계"가 n> k에 대하여 참임을 정당화하며, 

즉 "만약 q(i)가 i > n에 대하여 참이라면, q(n)은 참"임을 보여준다. 

3.  두 조각의 결합은 귀납법에 의한 정당화를 완성한다.

제안 4.20: 피보나치 함수 F(n)를 생각해 보자. 

여기서 우리는 F(1) = 1, F(2) = 2,

그리고 F(n) = F(n - 1) + F(n - 2)를 n > 2에 대해 정의한다. 

(2.2.3절 참조) 우리는 F(n) < 2^n이라고 주장한다.

 

정당성: 귀납법으로 우리의 주장이 옳다는 것을 보여줄 것이다. 
기본 경우:(n ≤ 2). F(1) = 1 < 2 = 2^1 그리고 F(2) = 2 < 4 = 2^2.
귀납 단계: (n > 2). n' < n에 대해 우리의 주장이 사실이라고 가정한다. 

F(n)을 고려해 보자. n > 2이므로 F(n) = F(n - 1) + F(n - 2)이다. 

또한 n - 1 < n과 n - 2 < n이기 때문에, 

2^(n-1) +2^(n-2) < 2^(n-1) +2^(n-1) = 2 · 2^(n-1) = 2^n

그리고 나서 F(n)< 2^(n-1) +2^(n-2)임을 암시하기 위해

귀납적 가정(때로는 "귀납적 가설"이라고도 함)을 적용할 수 있다.

 

전에 본 사실에 대해 귀납적 주장을 한 번 더 해 보자.

 

제안 4.21: (제안 4.3과 동일).

정당화: 우리는 귀납에 의해 이 등식을 정당화할 것이다.
기본 경우: n = 1. n =1일 때 1 = n(n + 1)/2이 성립한다.
귀납 단계: n ≥ 2. n' < n에 대해 주장이 사실이라고 가정한다. n을 고려한다.

그렇다면 귀납 가설에 의해, 

우리가 단순화할 수 있는 것은
n + (n−1)n/2 = 2n + n^2 −n/2=n^2 +n/2=n(n+1)/2

 

우리는 때때로 모든 n ≥1에 대하여

참인 것을 정당화하는 작업에 압도당할지도 모른다. 

그러나 우리는 귀납법의 구체성을 기억해야 한다. 

그것은 임의의 특정한 n에 대하여, 

참인 것으로부터 시작하여 n에 대한 진리로 이어지는

유한한 단계별 함축 순서가 있다는 것을 보여준다. 

간단히 말해서 귀납법은 직접적인 정당화 순서를 만드는 공식이다.

루프 불변량

이 절에서 논의하는 마지막 정당화 기법은 루프 불변량(loop invariant)이다. 

루프에 관한 문장 S가 옳다는 것을 증명하려면,

S를 일련의 더 작은 문장 S0, S1, ..., Sk로 정의하자. 

여기서 S는 다음과 같다:
1. 초기 주장인 S0은 루프가 시작되기 전에 참이다.
2. 반복 i 이전에 Si-1이 참이면 반복 i 이후에 Si가 참이 된다.
3. 마지막 문장인 Sk는 우리가 사실이 되기를 바라는 문장 S를 암시한다.

실제로 1.9.2절에서 (알고리즘 ArrayMax의 정확성에 대한)

루프 불변량의 논쟁을 보았지만, 

여기서 한 가지 예를 더 들어보겠다. 

특히 A 배열에서 x 원소를 찾기 위해 

코드 조각 4.4에 표시된 arrayFind의 정확성을 정당화하기 위해 

루프 불변량을 사용하는 것을 고려해 보겠다.

코드 조각 4.4: 알고리즘 arrayFind 배열에서 주어진 요소를 찾기 위해 찾는다.   

Algorithm arrayFind(x, n):

      Input: A element x an n-element array, A.

      Output: The index i such that x = A[i] or -1 if no element of A is equal to i ← 0

   while i < n do

      if x = A[i] then

          return i

      else

           i ← i + 1

    return -1

arrayFind가 정확하다는 것을 보여주기 위해 

알고리즘의 정확성을 유도하는 일련의 문장 Si를 유도적으로 정의한다. 

구체적으로, 저희는 while문의 반복 i의 시작 부분에서 다음이 참이라고 주장한다:
Si: x는 A의 어떤 첫 번째 i 원소와도 같지 않는다.
이 주장은 루프의 첫 번째 반복의 시작에서 참인데, 

왜냐하면 A의 첫 번째 0에는 원소가 없기 때문이다

(이런 종류의 사소하게 참인 주장은 공백 상태로 유지된다고 한다). 

반복 i에서 원소 x를 원소 A[i]와 비교하고 이 두 원소가 같으면 인덱스 i를 반환한다. 

만약 두 원소 x와 A[i]가 같지 않으면 

x와 같지 않은 원소를 하나 더 발견하고 인덱스 i를 증가시킨다. 

따라서 이 새로운 i 값에 대해서는 주장 Si가 참이므로 다음 반복의 시작에서는 참이다. 

만약 while문이 A에서 인덱스를 반환하지 않고 종료된다면, 우리는 i = n을 갖게 된다. 

즉 Sn은 참이므로 A에는 x와 같은 원소가 없다. 

따라서 알고리즘은 x가 A에 없다는 것을 나타내기 위해 -1을 정확하게 반환한다.