기본 케이스가 O (n)이면 반복은 무엇입니까?

Question

우리는 알고리즘을 만들고 그것의 재발을 찾아 내야 만한다. 재발을 발견하면 나를 곤혹스럽게 만들었습니다.

foo(A, C) 
    if (C.Length = 0) 
    Sum(A) 
    else 
    t = C.Pop() 
    A.Push(t) 
    foo(A,C) 
    foo(A,C) 

처음에는 A가 비어 있고 C.Length = n입니다. 그게 허용되지 않기 때문에 나는 진짜 알고리즘을 줄 수 없다.

강사가 2 가지 변수를 사용하려고한다고 이야기했습니다. 이것은 내가 생각 해낸 것입니다 : 나는 그것을 해결할 수

T(n, i) = { n    if i = 0 
      2*T(n, i-1) + C if i != 0 

, 그래서 나는 또 하나 개의 변수로 재발을 해결하기 위해 노력 : N0는 N의 초기 값이다

T(n) = { n0     if n = 0 
     2*T(n-1) + C  if n != 0 

.

기본 케이스의 복잡성이 O (n) 인 알고리즘에서 어떻게 되풀이를 형성합니까?

Answer 1

C가 크기 n 인 경우 f (n)을 복잡도라고 합니다. N을 C의 원래 크기라고합시다.

그러면 f (0) = N 및 f (n) = 2 * f (n - 1) + c입니다.

이것은 f (n) = N * 2^n + (2^n - 1) * c이므로 f (N) = O (N * 2^N)입니다.