algorithm-analysis Archives - Page 3 of 3

알고리즘의 실행 시간을 분석하는 방법에 대한 많은 질문이 있습니다 (예 : 런타임 분석 및 알고리즘 분석 참조 ). 예를 들어 중첩 루프 또는 분할 및 정복 알고리즘의 비용 분석을 요구하는 경우와 유사하지만 대부분의 답변은 맞춤형으로 보입니다.

반면에, 다른 일반적인 질문에 대한 답변 은 몇 가지 예를 통해 더 큰 그림 (특히 점근 분석에 관한)을 설명하지만 손을 더럽히는 방법은 설명하지 않습니다.

알고리즘 비용을 분석하는 체계적이고 일반적인 방법이 있습니까? 비용은 실행 시간 (시간 복잡성) 또는 실행 횟수, 공간 복잡성 또는 기타 다른 요소와 같은 다른 비용 측정 값일 수 있습니다.

^{이것은 초보자를 가리키는 데 사용할 수 있는 참조 질문 이되어야합니다. 따라서 일반적인 범위보다 광범위합니다. 적어도 하나의 예로 설명되어 있지만 많은 상황을 다루는 일반적이고 교훈적으로 제시된 답변을 제공하도록주의하십시오. 감사!}

답변

코드를 수학으로 번역

공식적인 연산 의미론 이 주어지면 알고리즘의 (의사) 코드를 문자 그대로 수학적인 표현으로 변환하여 결과를 제공하는 수식을 유용한 형식으로 조작 할 수 있습니다. 이는 비교 횟수, 스왑, 명령문, 메모리 액세스, 일부 추상 머신 요구주기 등과 같은 추가 비용 측정에 효과적 입니다.

예 : Bubblesort의 비교

주어진 배열을 정렬하는이 알고리즘을 고려하십시오 A.

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

일반적인 정렬 알고리즘 분석을 수행하고 싶다고 가정 해 봅시다. 즉, 요소 비교 횟수를 계산합니다 (라인 5). 우리는이 수량이 배열의 내용에 의존하지 않고 A길이 에만 의존한다는 것을 즉시 주목한다 . 따라서 (중첩) 루프를 문자 그대로 (중첩) 합계로 변환 할 수 있습니다 . 루프 변수는 합산 변수가되고 범위는 계속됩니다. 우리는 얻는다 : $n$

for

$C_{cmp} (n) = \sum_{i = 0}^{n - 2} \sum_{j = 0}^{n - i - 2} 1 = \dots = \frac{n (n - 1)}{2} = (\binom{n}{2})$

Ccmp(n)=∑i=0n−2∑j=0n−i−21=⋯=n(n−1)2=(n2)

여기서 은 5 행 (각 카운트)의 각 실행에 대한 비용입니다. $1$

예 : Bubblesort에서 스왑

I 의해 나타내는 것이다 라인으로 구성 서브 행 과 의해 이 서브 프로그램 (회) 실행 비용. $P_{i, j}$

Pi,j

ij $C_{i, j}$

Ci,j

이제 스왑 을 계산하려고한다고 가정 해 봅시다. 이것이 이 얼마나 자주 실행 되는지 입니다. 이것은 “기본 블록”으로, 항상 원자 적으로 실행되며 일정한 비용 (여기서는 )을 갖는 서브 프로그램입니다 . 그러한 블록을 계약하는 것은 우리가 생각하거나 이야기하지 않고 종종 적용하는 유용한 단순화 중 하나입니다. $P_{6, 8}$

P6,8

$1$

위와 비슷한 번역으로 우리는 다음 공식을 얻습니다.

$C_{swaps} (A) = \sum_{i = 0}^{n - 2} \sum_{j = 0}^{n - i - 2} C_{5, 9} (A^{(i, j)})$

Cswaps(A)=∑i=0n−2∑j=0n−i−2C5,9(A(i,j))

$A^{(i, j)}$

A(i,j)

는 의 번째 반복 이전의 배열 상태를 나타냅니다 . $(i, j)$

(i,j)

$P_{5, 9}$

P5,9

매개 변수 로 대신 를 사용합니다 . 곧 이유를 알 수 있습니다. 비용이 여기에 의존하지 않기 때문에 매개 변수로 와 를 추가 하지 않습니다 ( 균일 한 비용 모델 에서). 일반적으로, 그들은 단지 수도 있습니다. $A$

$n$

$i$

$j$

$C_{5, 9}$

C5,9

분명히, 의 비용은 의 내용 (값 과 구체적으로) 에 따라 달라 지므로 우리는이를 고려해야합니다. 이제 우리는 도전에 직면합니다. 어떻게 “포장 해제” 합니까? 음, 우리는 의 내용에 의존 할 수 있습니다 : $P_{5, 9}$

P5,9

$A$

A[j]A[j+1] $C_{5, 9}$

C5,9

$A$

$C_{5, 9} (A^{(i, j)}) = C_{5} (A^{(i, j)}) + {\begin{cases} 1 & , A^{(i, j)} [j] > A^{(i, j)} [j + 1] \\ 0 & , else \end{cases}$

C5,9(A(i,j))=C5(A(i,j))+{1,A(i,j)[j]>A(i,j)[j+1]0,else

입니다.

주어진 입력 배열에 대해 이러한 비용은 잘 정의되어 있지만보다 일반적인 설명을 원합니다. 우리는 더 강력한 가정을해야합니다. 세 가지 일반적인 사례를 조사하겠습니다.

최악의 경우

합계를보고 주목하면 비용에 대한 상한을 찾을 수 있습니다. $C_{5, 9} (A^{(i, j)}) \in {0, 1}$
C5,9(A(i,j))∈{0,1}
$C_{swaps} (A) \leq \sum_{i = 0}^{n - 2} \sum_{j = 0}^{n - i - 2} 1 = \frac{n (n - 1)}{2} = (\binom{n}{2})$
Cswaps(A)≤∑i=0n−2∑j=0n−i−21=n(n−1)2=(n2)
입니다.

그러나 이것이 일어날 수 있습니까 , 즉 이 상한에 대한 가 달성 되었습니까? 알 수 있듯이, 그렇습니다 : 쌍으로 구별되는 요소로 역 정렬 된 배열을 입력하면 모든 반복이 스왑을 수행해야합니다 ¹. 따라서, 우리는 Bubblesort의 최악 의 정확한 스왑 수를 도출했습니다. $A$
A
가장 좋은 경우

반대로, 사소한 하한이 있습니다.

$C_{swaps} (A) \geq \sum_{i = 0}^{n - 2} \sum_{j = 0}^{n - i - 2} 0 = 0$
Cswaps(A)≥∑i=0n−2∑j=0n−i−20=0
.

이미 정렬 된 어레이에서 Bubblesort는 단일 스왑을 실행하지 않습니다.
평균 사례

최악의 상황과 가장 좋은 경우는 상당히 차이가 있습니다. 그러나 일반적인 스왑 수는 얼마입니까? 이 질문에 답하기 위해서는 “일반적인”의 의미를 정의해야합니다. 이론적으로, 우리는 하나의 입력을 다른 입력보다 선호 할 이유가 없으므로 모든 가능한 입력에 대해 균일 한 분포 를 가정합니다 . 즉, 모든 입력이 똑같이 가능합니다. 페어별로 구별되는 요소가있는 배열로 제한하므로 랜덤 순열 모델 을 가정합니다 .

그러면 다음과 같이 비용을 다시 쓸 수 있습니다 ² :

$E [C_{swaps}] = \frac{1}{n!} \sum_{A} \sum_{i = 0}^{n - 2} \sum_{j = 0}^{n - i - 2} C_{5, 9} (A^{(i, j)})$
E[Cswaps]=1n!∑A∑i=0n−2∑j=0n−i−2C5,9(A(i,j))
이제 우리는 단순한 합 조작을 넘어서야합니다. 알고리즘을 살펴보면 모든 스왑 이 에서 정확히 하나의 반전 을 제거한다는 것을 알 수 있습니다. 즉, 수행 교환 수있다 정확히 역전의 개수 의 . 따라서 우리는 내부 두 합계를 대체하고 얻을 수 있습니다. $A$
A
$A$
A
$inv (A)$
inv⁡(A)
$A$
A
$E [C_{swaps}] = \frac{1}{n!} \sum_{A} inv (A)$
E[Cswaps]=1n!∑Ainv⁡(A)
.

운 좋게도, 평균 반전 횟수는

$E [C_{swaps}] = \frac{1}{2} \cdot (\binom{n}{2})$
E[Cswaps]=12⋅(n2)
이것이 우리의 최종 결과입니다. 이 유의 정확히 절반 최악의 경우의 비용입니다.

i = n-1아무것도하지 않는 외부 루프를 사용한 “마지막”반복이 실행되지 않도록 알고리즘을 신중하게 구성했습니다 .
” “는 “예상 값”에 대한 수학적 표기법으로 평균입니다. $E$
우리는 그 길을 따라 배울 수 없는 유일한 이웃 요소를 스왑 알고리즘은 점근 적으로 빠른 (심지어 평균) 거품 정렬보다 수 – 역전의 수는 하한 이러한 모든 알고리즘이다. 이는 예를 들어 삽입 정렬 및 선택 정렬에 적용됩니다 .

일반적인 방법

우리는 예제에서 제어 구조를 수학으로 변환해야한다는 것을 보았습니다. 나는 전형적인 번역 규칙 앙상블을 제시 할 것이다. 우리는 또한 주어진 서브 프로그램의 비용이 현재 상태 , 즉 (대략) 변수의 현재 값에 의존 할 수 있음을 보았습니다 . 알고리즘은 일반적으로 상태를 수정하므로 일반적인 방법은 약간 번거 롭습니다. 혼란스러워지기 시작하면 모범으로 돌아가거나 직접 구성하는 것이 좋습니다.

현재 상태 를 합니다 (변수 할당 세트로 상상해보십시오). 상태에서 시작 하는 프로그램을 실행하면 상태로 종료됩니다 (제공된 경우 ). $ψ$

P $ψ$

$ψ / P$

ψ/P

P

개별 진술

단 하나의 명령문 만 S;지정하면 비용이 지정됩니다 . 이것은 일반적으로 일정한 함수입니다. $C_{S} (ψ)$
CS(ψ)
표현

E양식 의 표현이있는 경우 E1 ∘ E2(예 : ∘덧셈 또는 곱셈 일 수 있는 산술 식) 비용을 재귀 적으로 추가합니다.

$C_{E} (ψ) = c_{\circ} + C_{E_{1}} (ψ) + C_{E_{2}} (ψ)$
CE(ψ)=c∘+CE1(ψ)+CE2(ψ)
.

참고
- 동작 비용 일정하게하지만,의 값에 의존하지 않을 수 및 및 $c_{\circ}$ $E_{1}$ $E_{2}$
- 표현의 평가는 많은 언어로 상태를 바꿀 수 있습니다.
따라서이 규칙을 유연하게 사용해야 할 수도 있습니다.
순서

프로그램 P을 일련의 프로그램 Q;R으로 지정하면 비용이 추가됩니다.

$C_{P} (ψ) = C_{Q} (ψ) + C_{R} (ψ / Q)$
CP(ψ)=CQ(ψ)+CR(ψ/Q)
.
조건부

P형식 의 프로그램 이 주어지면 if A then Q else R end비용은 주에 따라 다릅니다.

$C_{P} (ψ) = C_{A} (ψ) + {\begin{cases} C_{Q} (ψ / A) & , A evaluates to true under ψ \\ C_{R} (ψ / A) & , else \end{cases}$
CP(ψ)=CA(ψ)+{CQ(ψ/A),A evaluates to true under ψCR(ψ/A),else
일반적으로 평가 A하면 상태가 매우 잘 변할 수 있으므로 개별 지점의 비용이 업데이트됩니다.
루프

P양식 의 프로그램 이 주어지면 for x = [x1, ..., xk] do Q end비용을 할당하십시오.

$C_{P} (ψ) = c_{init_for} + \sum_{i = 1}^{k} c_{step_for} + C_{Q} (ψ_{i} \circ {x := x i})$
CP(ψ)=cinit_for+∑i=1kcstep_for+CQ(ψi∘{x:=xi})
여기서 는 value 를 처리하기 전 , 즉 반복이 , …, 로 설정된 후의 상태 입니다. $ψ_{i}$
ψi
Qxixx1xi-1

루프 유지 보수를위한 추가 상수에 유의하십시오. 루프 변수를 작성하고 ( ) 값을 지정해야합니다 ( ). 이후로 관련이 있습니다 $c_{init_for}$
cinit_for
$c_{step_for}$
cstep_for
- 다음 계산은 xi비용이 많이 들고
- for빈 본문이 있는 -loop (예 : 특정 비용으로 최상의 경우 설정을 단순화 한 후)는 반복을 수행하는 경우 비용이 없습니다.
동안 루프

P양식 의 프로그램 이 주어지면 while A do Q end비용을 할당하십시오.

$C_{P} (ψ) = C_{A} (ψ) + {\begin{cases} 0 & , A evaluates to false under ψ \\ C_{Q} (ψ / A) + C_{P} (ψ / A; Q) & , else \end{cases}$
CP(ψ) =CA(ψ)+{0,A evaluates to false under ψCQ(ψ/A)+CP(ψ/A;Q), else
알고리즘을 검사함으로써,이 반복은 종종 for-loops와 유사한 합계로 멋지게 표현 될 수 있습니다.

예 : 이 짧은 알고리즘을 고려하십시오.
```
while x > 0 do    1
  i += 1          2
  x = x/2         3
end               4
```
규칙을 적용하면

$C_{1, 4} ({i := i_{0}; x := x_{0}}) = c_{<} + {\begin{cases} 0 & , x_{0} \leq 0 \\ c_{+ =} + c_{/} + C_{1, 4} ({i := i_{0} + 1; x := ⌊ x_{0} / 2 ⌋}) & , else \end{cases}$
C1,4({i:=i0;x:=x0}) =c<+{0,x0≤0c+=+c/+C1,4({i:=i0+1;x:=⌊x0/2⌋}), else
개별 명세서에 대해 일정한 비용 로 우리는 이러한 않음을 암시 적으로 가정 하지 (의 값 상태에 의존 하고 ); 이것은 "실제"에서 사실 일 수도 있고 아닐 수도 있습니다 : 오버플로를 생각하십시오! $c_{\dots}$
c…
ix

이제 대한이 반복을 해결해야합니다 . 루프 바디의 비용이 아닌 반복 횟수는의 값에 의존하지 않으므로 드롭 할 수 있습니다. 우리는이 재발로 떠납니다. $C_{1, 4}$
C1,4
i

$C_{1, 4} (x) = {\begin{cases} c_{>} & , x \leq 0 \\ c_{>} + c_{+ =} + c_{/} + C_{1, 4} (⌊ x / 2 ⌋) & , else \end{cases}$
C1,4(x)={c>,x≤0c>+c+=+c/+C1,4(⌊x/2⌋), else
이것은 기본 수단 으로 해결 합니다.

$C_{1, 4} (ψ) = ⌈ \log_{2} ψ (x) ⌉ \cdot (c_{>} + c_{+ =} + c_{/}) + c_{>}$
C1,4(ψ)=⌈log2⁡ψ(x)⌉⋅(c>+c+=+c/)+c>
,

전체 상태를 상징적으로 다시 소개; 만약 다음 . $ψ = {\dots, x := 5, \dots}$
ψ={…,x:=5,…}
$ψ (x) = 5$
ψ(x)=5
절차 호출

프로그램 감안할 때 P양식을 M(x)일부 매개 변수 (들)에 대한 (이름) 매개 변수와 절차 , 비용을 할당xMp

$C_{P} (ψ) = c_{call} + C_{M} (ψ_{glob} \circ {p := x})$
CP(ψ)=ccall+CM(ψglob∘{p:=x})
.

여분의 상수 (실제로 ! 에 의존 할 수 있음 )에주의하십시오. 프로 시저 호출은 실제 머신에서 구현되는 방식으로 인해 비싸고 때로는 런타임을 지배하기도합니다 (예 : 피보나치 수의 순진한 평가). $c_{call}$
ccall
$ψ$
ψ
나는 당신이 여기 상태에있을 수있는 의미 론적 문제에 대해 광택을냅니다. 전역 상태와 이러한 로컬 대 프로 시저 호출을 구별하려고합니다. 여기서 전역 상태 만 전달 M하고 값을 p로 설정하여 초기화 된 새로운 로컬 상태를 얻는다고 가정 해 봅시다 x. 또한, x전달하기 전에 평가하는 것으로 가정하는 표현 일 수도 있습니다.

예 : 절차 고려
```
fac(n) do
  if ( n <= 1 ) do         1
    return 1               2
  else                     3
    return n * fac(n-1)    4
  end                      5
end
```
규칙에 따라 다음을 얻습니다.

$\begin{aligned} C_{fac} ({n := n_{0}}) & = C_{1, 5} ({n := n_{0}}) \\ = c_{\leq} + {\begin{cases} C_{2} ({n := n_{0}}) & , n_{0} \leq 1 \\ C_{4} ({n := n_{0}}) & , else \end{cases} \\ = c_{\leq} + {\begin{cases} c_{return} & , n_{0} \leq 1 \\ c_{return} + c_{*} + c_{call} + C_{fac} ({n := n_{0} - 1}) & , else \end{cases} \end{aligned}$
Cfac({n:=n0})=C1,5({n:=n0})=c≤+{C2({n:=n0}),n0≤1C4({n:=n0}), else=c≤+{creturn,n0≤1creturn+c∗+ccall+Cfac({n:=n0−1}), else
우리는 fac명확하게 액세스 할 수 없으므로 글로벌 상태를 무시 합니다. 이 특정 재발은 해결하기 쉽습니다.

$C_{fac} (ψ) = ψ (n) \cdot (c_{\leq} + c_{return}) + (ψ (n) - 1) \cdot (c_{*} + c_{call})$
Cfac(ψ)=ψ(n)⋅(c≤+creturn)+(ψ(n)−1)⋅(c∗+ccall)

일반적인 의사 코드에서 발생하는 언어 기능에 대해 설명했습니다. 고급 의사 코드를 분석 할 때 숨겨진 비용에주의하십시오. 의심스러운 경우 전개하십시오. 이 표기법은 번거롭고 맛의 문제 일 수 있습니다. 그러나 나열된 개념은 무시할 수 없습니다. 그러나 일부 경험을 통해 "문제 크기"또는 "정점 수"와 같이 국가의 어느 부분이 어떤 비용 측정과 관련이 있는지 즉시 확인할 수 있습니다. 나머지는 떨어 뜨릴 수 있습니다. 이렇게하면 상황이 크게 단순화됩니다!

당신이 너무 복잡 것을 지금 생각하면, 통보 : 그것은 이다 ! 실제 기계에 가까운 모델에서 알고리즘의 정확한 비용을 도출하여 런타임 예측 (상대적인 예측조차 가능)을 가능하게하는 것은 어려운 노력입니다. 그리고 실제 머신에 대한 캐싱 및 기타 불쾌한 영향도 고려하지 않습니다.

따라서 알고리즘 분석은 수학적으로 다루기 쉬운 수준으로 단순화되는 경우가 많습니다. 예를 들어 정확한 비용이 필요하지 않은 경우 어느 시점에서나 상한 또는 하한을 과대 평가하거나 과소 평가할 수 있습니다. 상수 세트를 줄이고 조건을 제거하고 합계를 단순화하는 등의 작업을 수행 할 수 있습니다.

점근 적 비용에 대한 메모

일반적으로 문헌과 웹에서 찾을 수있는 것은 "빅오 분석"입니다. 적절한 용어는 점근 분석입니다. 이는 예에서했던 것처럼 정확한 비용을 도출하는 대신 비용을 일정한 요소와 한계 (대략 말하기, "큰 ") 까지만 제공한다는 것을 의미합니다 . $n$

이 추상 문이 있기 때문에 (보통) 공정한 일부 컴퓨터, 운영 체제 및 기타 요인에 따라 현실에서 (일반적으로 알 수없는) 비용, 짧은 런타임은 처음과 이것 저것에 과정을 설정 운영 체제에 의해 지배 될 수 있습니다. 어쨌든 당신은 약간의 혼란을 얻습니다.

다음은 점근 분석이이 방법과 어떤 관련이 있는지 보여줍니다.

지배적 인 운영 (비용을 유발하는), 즉 가장 자주 발생하는 운영 (최대의 일정한 요인)을 식별하십시오 . Bubblesort 예제에서 한 가지 가능한 선택은 5 행의 비교입니다.

또는 기본 연산에 대한 모든 상수를 최대 (위에서)로 제한합니다. 최소값 (아래에서)과 일반적인 분석을 수행합니다.
이 작업의 실행 횟수를 비용으로 사용하여 분석을 수행하십시오.
단순화 할 때 추정을 허용하십시오. 목표가 상한 ( ) 인 경우 위에서 만 추정을 허용하도록주의하십시오 . 하한을 원하면 아래에서 ( ). $O$ $Ω$

Landau 기호의 의미 를 이해해야 합니다 . 이러한 한계 는 세 가지 경우 모두에 존재한다는 것을 기억하십시오 . 사용 한다고해서 최악의 경우는 아닙니다. $O$

추가 자료

알고리즘 분석에는 더 많은 도전과 트릭이 있습니다. 다음은 몇 가지 권장 사항입니다.

이와 유사한 기술을 사용하는 알고리즘 분석 태그가 붙은 많은 질문 이 있습니다.

답변

실행 횟수

Donald E. Knuth가 그의 The Art of Computer Programming 시리즈 에서 우승 한 또 다른 방법이 있습니다 . 전체 알고리즘을 하나의 공식으로 변환하는 것과 달리 , "함께 넣기"측면에서 코드 시맨틱과 독립적으로 작동하며 "독수리"관점에서 시작하여 필요할 때만 더 낮은 레벨로 이동할 수 있습니다. 모든 계산서는 나머지와 독립적으로 분석 할 수있어보다 명확한 계산이 가능합니다. 그러나이 기술은 그보다 더 높은 수준의 의사 코드가 아니라 자세한 코드에 적합합니다.

방법

원칙적으로 매우 간단합니다.

모든 명세서에 이름 / 번호를 지정하십시오.
모든 명령문 비용 지정하십시오 . $S_{i}$ $C_{i}$
모든 명령문 대해 실행 횟수 결정하십시오 . $S_{i}$ $e_{i}$
총 비용 계산

$C = \sum_{i} e_{i} \cdot C_{i}$
C=∑iei⋅Ci
입니다.

어느 시점에서든 추정치 및 / 또는 기호 수량을 삽입하여 Resp를 약화시킬 수 있습니다. 그에 따라 결과를 일반화합니다.

3 단계는 임의로 복잡 할 수 있습니다. 일반적으로 결과를 얻으려면 " " 과 같은 (점근) 추정값을 사용해야 합니다. $e_{77} \in O (n \log n)$

e77∈O(nlog⁡n)

예 : 깊이 우선 검색

다음과 같은 그래프 탐색 알고리즘을 고려하십시오.

dfs(G, s) do
  // assert G.nodes contains s
  visited = new Array[G.nodes.size]     1
  dfs_h(G, s, visited)                  2
end

dfs_h(G, s, visited) do
  foo(s)                                3
  visited[s] = true                     4

  v = G.neighbours(s)                   5
  while ( v != nil ) do                 6
    if ( !visited[v] ) then             7
      dfs_h(G, v, visited)              8
    end
    v = v.next                          9
  end
end

(방향이 지정되지 않은) 그래프는 노드 인접 목록 에 의해 제공되는 것으로 가정합니다 . 모서리 수를 이라고하자 . ${0, \dots, n - 1}$

{0,…,n−1}

$m$

알고리즘을 살펴보면 일부 명령문이 다른 명령문과 동일하게 자주 실행되는 것을 볼 수 있습니다. 실행 횟수 대한 자리 표시 자 , 및 를 소개합니다 . $A$

$B$

$C$

$e_{i}$

$\begin{array}{cccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ e_{i} & A & A & B & B & B & B + C & C & B - 1 & C \end{array}$

i123456789eiAABBBB+CCB−1C

특히, 라인 8의 모든 재귀 호출 은 라인 3 의 호출을 유발하기 때문에 (그리고 하나는의 원래 호출로 인해 발생하기 때문에) 입니다. 또한, 때문에 조건을 확인하는 반복 당하지만 한 번 더 위해서는 일단을 남겨합니다. $e_{8} = e_{3} - 1$

e8=e3−1

foodfs $e_{6} = e_{5} + e_{7}$

e6=e5+e7

while

그것은 그 분명 . 이제 정확성을 검증하는 동안 노드 당 정확히 한 번만 실행 됨을 보여줍니다 . 즉, 입니다. 그러나 모든 인접 목록을 정확히 한 번 반복하고 모든 에지는 총 두 개의 항목 (사건 노드마다 하나씩)을 의미합니다. 우리는 반복을 얻습니다 . 이를 사용하여 다음 테이블을 파생시킵니다. $A = 1$

A=1

foo $B = n$

B=n

$C = 2 m$

C=2m

$\begin{array}{cccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ e_{i} & 1 & 1 & n & n & n & 2 m + n & 2 m & n - 1 & 2 m \end{array}$

i123456789ei11nnn2m+n2mn−12m

이로 인해 총 비용이 정확히

$\begin{aligned} C (n, m) = (C_{1} + C_{2} - C_{8}) & + n \cdot (C_{3} + C_{4} + C_{5} + C_{6} + C_{8}) \\ + 2 m \cdot (C_{6} + C_{7} + C_{9}) . \end{aligned}$

C(n,m)=(C1+C2−C8)+ n⋅(C3+C4+C5+C6+C8)+ 2m⋅(C6+C7+C9).

적합한 값을 인스턴스화하면 보다 구체적인 비용을 얻을 수 있습니다. 예를 들어, 단어 당 메모리 액세스 수를 계산하려면 $C_{i}$

$\begin{array}{cccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ C_{i} & n & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array}$

i123456789Cin00110101

그리고 얻다

$C_{mem} (n, m) = 3 n + 4 m$

Cmem(n,m)=3n+4m

입니다.

추가 자료

내 다른 답변 의 맨 아래를 참조하십시오 .

답변

정리 증명과 같은 알고리즘 분석은 주로 예술입니다 (예 : 분석 방법을 모르는 간단한 프로그램 (예 : Collatz 문제 )). Raphael이 포괄적 으로 대답 한 것처럼 알고리즘 복잡성 문제를 수학 문제로 변환 할 수 있지만 알려진 함수 측면에서 알고리즘 비용에 대한 경계를 표현하려면 다음을 수행해야합니다.

우리가 이해 하는 반복 또는 계산할 수있는 합 / 통합을 기반으로 범위를 찾는 것과 같이 기존 분석에서 알고있는 기술을 사용하십시오 .
알고리즘을 분석 방법으로 알고있는 것으로 변경하십시오.
완전히 새로운 접근 방식을 생각해보십시오.

답변

Exit mobile version

How IT

언제든지 물어보세요.

태그 보관물: algorithm-analysis

알고리즘 분석의 마법 뒤에 시스템이 있습니까? 많은 질문이

답변

코드를 수학으로 번역

예 : Bubblesort의 비교

예 : Bubblesort에서 스왑

일반적인 방법

점근 적 비용에 대한 메모

추가 자료

답변

실행 횟수

방법

예 : 깊이 우선 검색

추가 자료

답변

답변