알고리즘의 반복 관계

Question

void doSomething(int *a, int left, int right){ 
    if (left == right){ 
     for (int j = 0; i < right; ++j) 
     cout << a[j]; 
     cout << endl; 
     return; 
    } 
    for (int i = left; i < right; ++i){ 
     std::swap(a[left], a[i]); 
     doSomething(a, left + 1, right); 
     std::swap(a[left], a[i]); 
    } 
} 

"기본 사건이 T (1) = right라고 가정하고, 스왑 함수가 O에서 두 개의 인수 값을 교환한다고 가정합니다. 1) 시간이고 반복 관계의 경우 T (n), n = right-left + 1이라고합시다. "

위에서 주어진 코드의 반복 관계를 찾도록 요청 받았습니다. 첫 번째 'if'문은 단지 == right가 될 때마다 배열의 내용을 단순히 출력한다는 결론을 내릴 수있었습니다. 맨 아래 부분은 반복적 인 문장이지만 복잡성을 분석하는 방법을 알지 못합니다. 어떤 도움을 주시면 감사하겠습니다!

Answer 1

swap은 부적합합니다. 인쇄 된 내용에 영향을 미치지 만 알고리즘의 실행 시간에는 영향을 미치지 않습니다. 무엇이 발생하는지 살펴 보겠습니다.

doSomething(arr, j, j)은 j을 표시합니다.
doSomething(arr, i, j)으로 전화하면 j-i 번으로 전화가 doSomething(arr, i+1, j)이됩니다.

변수를 조금 재정의하고 f(i)을 doSomething(arr, j-i, j)으로 정의하십시오. 그런 식으로 f(0)은 기본 케이스입니다. 재발 규칙은 다음과 같이 다시 쓸 수 있습니다.

은 f(i-1)으로 전화를 겁니다.

T(n) = O(n! * n) 

말할 필요도없이, 그건 꽤 큰 런타임의 : 말을하는 것입니다

T(n) = n * T(n-1) 
T(1) = O(n) 

: 꽤 명확한 재발 관계를 만드는

!