1

アルゴリズムを作成し、その再帰を見つけて解決する必要があります。再発を見つけて困惑しました..

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

解決できなかったので、変数を 1 つだけ使用して再発を解決しようとしました。

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

ここで、n0 は n の初期値です。

基本ケースの複雑さが O(n) であるアルゴリズムからどのように再帰を形成しますか?

4

1 に答える 1

2

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) です。

于 2011-02-06T13:04:56.553 に答える