점근적인 최악의 실행 시간입니다. 몇 가지 설명이 필요함

Question

아래의 mystery(n) 함수에 대한 의사 코드는 최악의 경우 실행 시간 f(n)에서 엄격한 상한과 하한을 찾아야합니다. 즉, g(n)은 f(n) ∈ Θ (g(n))입니다. (N/2) 뉴저지 (이것에 확실하지)

측면에 시간 태그 내가 지금까지 알아 낸 무엇 :

Mystery (n){     
c ←1       | (constant) 
for i ←1 to n     | n 
    do for j ←i to n   | j 
    do for k ← n down to n/2 | n/2 
     do c ← c + 1   | (constant) 
print c      | (constant) 
} 

총 시간 (즉, N 가정은 양의 정수). 최악의 경우와 최악의 경우의 실행 시간에는 차이가 없다는 것이이 문제의 또한,이 방법에 대해 엄격한 상한 및 하한을 어떻게 찾을 수 있습니까? 어떤 충고라도 잘 될 것입니다. 또는 저의 교과서로서 독서를 할 수있는 자료는 주제에 대해 매우 모호합니다.

Answer 1

j은 j이 이기 때문에 공식에 포함되지 않아야합니다.

외부 루프 변수에 의존하는 루프가있을 때마다 나는 합계 공식을보고 복잡성을 찾는 것이 가장 쉽다는 것을 알게되었습니다.

그래서 바깥 쪽 루프는 확실히 n 번 실행되며 가장 안쪽 루프는 확실히 n/2 번 실행되지만 일반적으로 n/2 ∈ O(n)입니다.

중간 루프를 살펴 보겠습니다.

중간 루프는 첫 번째 반복시에 (n-1) 번 실행되고 두 번째 반복시에는 (n-2) 번, 두 번째 반복에서는 (n-n)까지 0 번과 동일하게 실행됩니다. 이 용어를 단순히 0에서 n의 합계로 재 배열 할 수 있습니다. 이 합계는 n(n+1)/2과 같습니다.

이 수식은 바깥 쪽 루프와 중간 루프의 조합을 나타내므로 가장 안쪽 루프를 곱하면 최종 수식은 n(n+1)n/(2*2) == n^2(n+1)/4이됩니다.

실현해야 할 개념적 사실 중 하나는 c은 단순히 카운터이며 매 반복마다 증가하므로 c은이 알고리즘의 런타임 복잡성을 직접 나타내는 것으로 생각할 수 있습니다.

c을 계산하여이 결과를 확인할 수 있습니다. 여기

#include <stdio.h> 
#include <stdlib.h> 

int main(int argc, char *argv[]) { 
    int c = 0; 
    int n = 10; 
    if (argc > 1) { 
    n = atoi(argv[1]); 
    } 
    for (int i = 1; i <= n; ++i) { 
    for (int j = i; j <= n; ++j) { 
     /* Note that I've changed k to run from 0 to n/2 instead of n 
     down to n/2, but this doesn't change the result. */ 
     for (int k = 0; k < n/2; ++k) { 
     ++c; 
     } 
    } 
    } 
    printf("c == %d; n^2(n+1)/4 == %d\n", c, n*n*(n+1)/4); 
} 

상기 입력 2, 4, 8, 32에 대한 상기 프로그램의 출력 및 64있어 :

c == 3; n^2(n+1)/4 == 3 
c == 20; n^2(n+1)/4 == 20 
c == 144; n^2(n+1)/4 == 144 
c == 8448; n^2(n+1)/4 == 8448 
c == 66560; n^2(n+1)/4 == 66560 

Answer 2

Mystery (n){     
c ←1       | (constant) 
for i ←1 to n     | n 
    do for j ←i to n   | j 
    do for k ← n down to n/2 | n/2 
     do c ← c + 1   | (constant) 
print c      | (constant) 
} 

여기서 알고리즘을 설명하기 C에 기록 된 예시적인 프로그램의 너는 n 시간을 실행하는 외부 루프에 대해 정확합니다. 그러나 다음 루프는 i = 1, n-1 번 i = 2, ..., 2 번, i = n-1 번, i = n 번씩 실행됩니다. 평균적으로 j 루프는 n/2 번 실행되므로이 ​​중간 루프도 O (n) 루프로 간주됩니다. 이렇게하면 세 개의 중첩 된 루프를 모두 결합 할 때 O (n^3)의 전체 런타임 복잡성이 발생합니다.