코드를 수학으로 번역

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

예 : 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

$n$for

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

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

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

$1$

예 : Bubblesort에서 스왑

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

$P_{i,j}$ijCi,j

$C_{i,j}$

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

$P_{6,8}$1

$1$

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

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

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

( i , j ) P 5 , 9A(i,j)

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

$(i,j)$P5,9

$P_{5,9}$

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

$A$n

$n$i

$i$j

$j$C5,9

$C_{5,9}$

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

$P_{5,9}$A

$A$A[j]A[j+1]C5,9

$C_{5,9}$A

$A$

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

$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) + \begin{cases} 1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]} \\ 0 &, \text{else} \end{cases}$ 입니다.

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

1. 최악의 경우

   합계를보고 주목하면 비용에 대한 상한을 찾을 수 있습니다.C5,9(A(i,j))∈{0,1}

   $C_{5,9}(A^{(i,j)})\in \{0,1\}$

   $C_{5,9}(A^{(i,j)}) \in \{0,1\}$

   Cswaps(A)≤∑i=0n−2∑j=0n−i−21=n(n−1)2=(n2)

   ${\displaystyle C_{\text{swaps}}(A)\le \sum _{i=0}^{n-2}\sum _{j=0}^{n-i-2}1=\frac{n(n-1)}{2}=(\genfrac{}{}{0ex}{}{n}{2})}$

   $\qquad\displaystyle C_{\text{swaps}}(A) \leq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \frac{n(n-1)}{2} = \binom{n}{2}$ 입니다.

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

   $A$

   $A$

2. 가장 좋은 경우

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

   Cswaps(A)≥∑i=0n−2∑j=0n−i−20=0

   ${\displaystyle C_{\text{swaps}}(A)\ge \sum _{i=0}^{n-2}\sum _{j=0}^{n-i-2}0=0}$

   $\qquad\displaystyle C_{\text{swaps}}(A) \geq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0 = 0$ .

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

3. 평균 사례

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

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

   E[Cswaps]=1n!∑A∑i=0n−2∑j=0n−i−2C5,9(A(i,j))

   ${\displaystyle \mathbb{E}[C_{\text{swaps}}]=\frac{1}{n!}\sum _A\sum _{i=0}^{n-2}\sum _{j=0}^{n-i-2}{C}_{5,9}(A^{(i,j)})}$

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

   이제 우리는 단순한 합 조작을 넘어서야합니다. 알고리즘을 살펴보면 모든 스왑 이 에서 정확히 하나의 반전 을 제거한다는 것을 알 수 있습니다. 즉, 수행 교환 수있다 정확히 역전의 개수 의 . 따라서 우리는 내부 두 합계를 대체하고 얻을 수 있습니다.A

   $A$

   $A$A

   $A$

   $A$inv(A)

   $\mathrm{inv}(A)$

   $\operatorname{inv}(A)$A

   $A$

   $A$

   E[Cswaps]=1n!∑Ainv(A)

   ${\displaystyle \mathbb{E}[C_{\text{swaps}}]=\frac{1}{n!}\sum _A\mathrm{inv}(A)}$

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$ .

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

   E[Cswaps]=12⋅(n2)

   ${\displaystyle \mathbb{E}[C_{\text{swaps}}]=\frac{1}{2}\cdot (\genfrac{}{}{0ex}{}{n}{2})}$

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

   이것이 우리의 최종 결과입니다. 이 유의 정확히 절반 최악의 경우의 비용입니다.

1. i = n-1아무것도하지 않는 외부 루프를 사용한 “마지막”반복이 실행되지 않도록 알고리즘을 신중하게 구성했습니다 .
2. ” “는 “예상 값”에 대한 수학적 표기법으로 평균입니다.E
   $\mathbb{E}$

   $\mathbb{E}$

3. 우리는 그 길을 따라 배울 수 없는 유일한 이웃 요소를 스왑 알고리즘은 점근 적으로 빠른 (심지어 평균) 거품 정렬보다 수 – 역전의 수는 하한 이러한 모든 알고리즘이다. 이는 예를 들어 삽입 정렬 및 선택 정렬에 적용됩니다 .

일반적인 방법

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

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

$\psi$Pψ

$\psi$ψ/P

$\psi / \mathtt{P}$P

• 개별 진술

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

  $C_S(\psi )$

  $C_S(\psi)$

• 표현

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

  CE(ψ)=c∘+CE1(ψ)+CE2(ψ)

  ${\displaystyle C_E(\psi )=c_{\circ }+C_{E_1}(\psi )+C_{E_2}(\psi )}$

  $\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$ .

  참고

  • 동작 비용 일정하게하지만,의 값에 의존하지 않을 수 및 및c∘
    $c_{\circ }$

    $c_{\circ}$E1

    $E_1$

    $E_1$E2

    $E_2$

    $E_2$

  • 표현의 평가는 많은 언어로 상태를 바꿀 수 있습니다.

  따라서이 규칙을 유연하게 사용해야 할 수도 있습니다.

• 순서

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

  CP(ψ)=CQ(ψ)+CR(ψ/Q)

  ${\displaystyle C_P(\psi )=C_Q(\psi )+C_R(\psi /\mathtt{Q})}$

  $\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$ .

• 조건부

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

  CP(ψ)=CA(ψ)+{CQ(ψ/A)CR(ψ/A),A evaluates to true under ψ,else

  ${\displaystyle C_P(\psi )=C_A(\psi )+\{\begin{array}{ll}{C}_Q(\psi /\mathtt{A})& ,\mathtt{A}\text{ evaluates to true under }\psi \\ C_R(\psi /\mathtt{A})& ,\text{else}\end{array}}$

  $\qquad\displaystyle C_P(\psi) = C_A(\psi) + \begin{cases} C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\ C_R(\psi/\mathtt{A}) &, \text{else} \end{cases}$

  일반적으로 평가 A하면 상태가 매우 잘 변할 수 있으므로 개별 지점의 비용이 업데이트됩니다.

• 루프

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

  CP(ψ)=cinit_for+∑i=1kcstep_for+CQ(ψi∘{x:=xi})

  ${\displaystyle C_P(\psi )=c_{\text{init\_for}}+\sum _{i=1}^k{c}_{\text{step\_for}}+C_Q({\psi }_i\circ \{\mathtt{x}\mathtt{:=}\mathtt{x}\mathtt{i}\})}$

  $\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

  여기서 는 value 를 처리하기 전 , 즉 반복이 , …, 로 설정된 후의 상태 입니다.ψi

  ${\psi }_i$

  $\psi_i$Qxixx1xi-1

  루프 유지 보수를위한 추가 상수에 유의하십시오. 루프 변수를 작성하고 ( ) 값을 지정해야합니다 ( ). 이후로 관련이 있습니다cinit_for

  $c_{\text{init\_for}}$

  $c_{\text{init_for}}$cstep_for

  $c_{\text{step\_for}}$

  $c_{\text{step_for}}$

  • 다음 계산은 xi비용이 많이 들고
  • for빈 본문이 있는 -loop (예 : 특정 비용으로 최상의 경우 설정을 단순화 한 후)는 반복을 수행하는 경우 비용이 없습니다.

• 동안 루프

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

  CP(ψ) =CA(ψ)+{0CQ(ψ/A)+CP(ψ/A;Q),A evaluates to false under ψ, else

  $$\begin{gathered} {\displaystyle C_P(\psi )} \\ =C_A(\psi )+\{\begin{array}{ll}0& ,\mathtt{A}\text{ evaluates to false under }\psi \\ C_Q(\psi /\mathtt{A})+C_P(\psi /\mathtt{A}\mathtt{;}\mathtt{Q})& ,\text{ else}\end{array} \end{gathered}$$

  $\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) + \begin{cases} 0 &, \mathtt{A} \text{ evaluates to false under } \psi \\ C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else} \end{cases}$

  알고리즘을 검사함으로써,이 반복은 종종 for-loops와 유사한 합계로 멋지게 표현 될 수 있습니다.

  예 : 이 짧은 알고리즘을 고려하십시오.

  while x > 0 do    1
    i += 1          2
    x = x/2         3
  end               4
  

  규칙을 적용하면

  C1,4({i:=i0;x:=x0}) =c<+{0c+=+c/+C1,4({i:=i0+1;x:=⌊x0/2⌋}),x0≤0, else

  $$\begin{gathered} {\displaystyle C_{1,4}(\{i:=i_0;x:=x_0\})} \\ =c_{<}+\{\begin{array}{ll}0& ,x_0\le 0\\ c_{+=}+c_{/}+C_{1,4}(\{i:=i_0+1;x:=\lfloor x_0/2\rfloor \})& ,\text{ else}\end{array} \end{gathered}$$

  $\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< + \begin{cases} 0 &#038;, x_0 \leq 0 \\ c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &#038;, \text{ else} \end{cases}$

  개별 명세서에 대해 일정한 비용 로 우리는 이러한 않음을 암시 적으로 가정 하지 (의 값 상태에 의존 하고 ); 이것은 "실제"에서 사실 일 수도 있고 아닐 수도 있습니다 : 오버플로를 생각하십시오!c…

  $c_{\dots }$

  $c_{\dots}$ix

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

  $C_{1,4}$

  $C_{1,4}$i

  C1,4(x)={c>c>+c+=+c/+C1,4(⌊x/2⌋),x≤0, else

  ${\displaystyle C_{1,4}(x)=\{\begin{array}{ll}{c}_{>}& ,x\le 0\\ c_{>}+c_{+=}+c_{/}+C_{1,4}(\lfloor x/2\rfloor )& ,\text{ else}\end{array}}$

  $\qquad\displaystyle C_{1,4}(x) = \begin{cases} c_> &, x \leq 0 \\ c_> + c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else} \end{cases}$

  이것은 기본 수단 으로 해결 합니다.

  C1,4(ψ)=⌈log2ψ(x)⌉⋅(c>+c+=+c/)+c>

  ${\displaystyle C_{1,4}(\psi )=\lceil {\log }_2\psi (x)\rceil \cdot (c_{>}+c_{+=}+c_{/})+c_{>}}$

  $\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> + c_{+=} + c_/) + c_>$ ,

  전체 상태를 상징적으로 다시 소개; 만약 다음 .ψ={…,x:=5,…}

  $\psi =\{\dots ,x:=5,\dots \}$

  $\psi = \{ \dots, x := 5, \dots\}$ψ(x)=5

  $\psi (x)=5$

  $\psi(x) = 5$

• 절차 호출

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

  CP(ψ)=ccall+CM(ψglob∘{p:=x})

  ${\displaystyle C_P(\psi )=c_{\text{call}}+C_M({\psi }_{\text{glob}}\circ \{p:=x\})}$

  $\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$ .

  여분의 상수 (실제로 ! 에 의존 할 수 있음 )에주의하십시오. 프로 시저 호출은 실제 머신에서 구현되는 방식으로 인해 비싸고 때로는 런타임을 지배하기도합니다 (예 : 피보나치 수의 순진한 평가).ccall

  $c_{\text{call}}$

  $c_{\text{call}}$ψ

  $\psi$

  $\psi$

  나는 당신이 여기 상태에있을 수있는 의미 론적 문제에 대해 광택을냅니다. 전역 상태와 이러한 로컬 대 프로 시저 호출을 구별하려고합니다. 여기서 전역 상태 만 전달 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
  

  규칙에 따라 다음을 얻습니다.

  Cfac({n:=n0})=C1,5({n:=n0})=c≤+{C2({n:=n0})C4({n:=n0}),n0≤1, else=c≤+{creturncreturn+c∗+ccall+Cfac({n:=n0−1}),n0≤1, else

  ${\displaystyle \begin{array}{rl}{C}_{\text{fac}}(\{n:=n_0\})& =C_{1,5}(\{n:=n_0\})\\ & =c_{\le }+\{\begin{array}{ll}{C}_2(\{n:=n_0\})& ,n_0\le 1\\ C_4(\{n:=n_0\})& ,\text{ else}\end{array}\\ & =c_{\le }+\{\begin{array}{ll}{c}_{\text{return}}& ,n_0\le 1\\ c_{\text{return}}+c_{\ast }+c_{\text{call}}+C_{\text{fac}}(\{n:=n_0-1\})& ,\text{ else}\end{array}\end{array}}$

  $\qquad\displaystyle\begin{align*} C_{\text{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 \}) &, \text{ else} \end{cases} \\ &= c_{\leq} + \begin{cases} c_{\text{return}} &, n_0 \leq 1 \\ c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\}) &, \text{ else} \end{cases} \end{align*}$

  우리는 fac명확하게 액세스 할 수 없으므로 글로벌 상태를 무시 합니다. 이 특정 재발은 해결하기 쉽습니다.

  Cfac(ψ)=ψ(n)⋅(c≤+creturn)+(ψ(n)−1)⋅(c∗+ccall)

  ${\displaystyle C_{\text{fac}}(\psi )=\psi (n)\cdot (c_{\le }+c_{\text{return}})+(\psi (n)-1)\cdot (c_{\ast }+c_{\text{call}})}$

  $\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}}) + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

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

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

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

점근 적 비용에 대한 메모

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

$n$

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

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

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

   또는 기본 연산에 대한 모든 상수를 최대 (위에서)로 제한합니다. 최소값 (아래에서)과 일반적인 분석을 수행합니다.

2. 이 작업의 실행 횟수를 비용으로 사용하여 분석을 수행하십시오.
3. 단순화 할 때 추정을 허용하십시오. 목표가 상한 ( ) 인 경우 위에서 만 추정을 허용하도록주의하십시오 . 하한을 원하면 아래에서 ( ).O
   $O$

   $O$Ω

   $\mathrm{\Omega }$

   $\Omega$

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

$O$

추가 자료

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

• 알고리즘 런타임을 생각해내는 방법?
  알고리즘을 설명하고 입증하고 분석하는 방법?
• 두 알고리즘을 비교하기 위해 런타임 대신 비교를 사용하는 이유는 무엇입니까?
  숫자에 대한 기본 연산에 일정한 시간이 걸린다고 어떻게 가정 할 수 있습니까?
  런타임 분석에서 한 시간 단위는 무엇입니까?
• 일련의 숫자에 대한 되풀이 관계를 풀거나 근사화
• 할부 상환 분석의 기초

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

답변

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