Yinelemeli işlevler yinelenen çalışma

Bazı özyinelemeli çağrılarda yinelenen çalışmalar var. Örneğin, aşağıdaki durumda, çalışan

T(n) = (sum from i to zero to (n-1) T(i) ) + n  

T (0) = 1 ile .here, her boyutta 0'dan n’ye bir (doğrudan) tekrarlamalı çağrıdır, artı O (n) ek çalışma.

T (n) için çözme, katlanarak büyüdüğünü görüyoruz.

Yinelemeli çağrının üzerinde ne tür bir ağaç ortaya çıkarsa, Divide ve ağacın fethi ile aynı mıdır?

Teşekkürler!

1
Bu bir yineleme ilişkisi, herhangi bir çağrı oluşturmuyor ...
katma yazar Karoly Horvath, kaynak
yepp, DP veya memoizasyon
katma yazar Karoly Horvath, kaynak
Ne sorduğuna emin değilim. Yukarıdaki işlev, matematiksel işlevlerin bir türü olan bir yineleme ilişkisidir. Matematikte "özyinelemeli bir çağrı" diye bir şey yoktur. Bu işlevi naif bir şekilde uygulamaya çalıştığınızda (daha iyi yollar olabilir), özyinelemeli çağrılar alırsınız. Ayrıca yinelenen çalışmalardan bahsediyorsunuz. Evet, naif uygulamada, bu fonksiyonu (ör. Dinamik programlama) hesaplamak için özyineleme kullanılmadığında kolayca ortadan kaldırılabilen, tekrarlayan bir çalışma vardır.
katma yazar LiKao, kaynak

1 cevap

Buna biraz yanıt vermeye çalışacağım ... ifadeler zayıf, ama belki bunu alabilir ve anlamını düzeltmek için benim anlayışımı kullanabilirsin.

Tekrarlı olarak uygulanan T (n) 'yi hesaplamak için bir fonksiyon sorduğunuzu varsayalım.

  T(n)
  1. r := 0
  2. for i := 0 to n-1 do
  3.    r := r + T(i)
  4. r := r + n
  5. return r

Bu özyineleme için bir ağaç böyle görünecekti ...

      _______________________T(n)_____________________
    /     /        /           \                \
  T(0)    T(1)       T(2)            T(3)      ...    T(n-1)
           |        /\         /  |   \              |
          T(0)    T(0) T(1)     T(0) T(1) T(2) ...      ...
                       ...           ...  ....

Ağaç, Fibonacci dizisinin değerlendirilmesi için elde ettiğimiz yineleme ağacına oldukça benzer; Aslında, toplamı [0, n-1] yerine [n-2, n-1] arasında olacak şekilde sınırlarsanız aynı ağacı alırsınız. Bunun çalışma zamanını bulmak için, fonksiyonun yinelemeli olmayan kısmı O (1) olduğundan, sadece kaç tane özyinelemeli çağrının yapıldığını saymalıyız.

T (n), n tekrarlayıcı çağrılar yapacak, T (0), T (1), ..., T (n-1). T (n) 'nin bir sonucu olarak, T (n-1) sadece bir kez çağrılacaktır; T (n-2) iki kez çağrılacaktır (bir kez T (n) nin bir sonucu olarak, yine T (n-1)). T (n-3) T (n) 'nin bir kez T (n-1) sonucu bir kez, iki kez T (n-2) çağrısının bir sonucu olarak çağrılır. Toplam 4 çağrı. Şimdi görebildiğimiz gibi, T (nk), T (n) 'nin sonucu olarak 2 ^ (k-1) çarpı olarak adlandırılır; l ve n arasındaki her k için çağrı sayısını toplarsak, 2 ^ n - 1 ... değil mi? Bu yüzden O (2 ^ n) 'nin bu fonksiyonu için bir zaman karmaşıklığı elde ediyoruz ... tıpkı saf Fibonacci gibi.

Fonksiyon tarafından döndürülen değerin büyüme oranını elde etmek için, başka bir kod parçasının nüksetme ilişkisi olarak fonksiyonun kendisine bakabiliriz. Bu durumda, birkaç terim listelemeye başlayabiliriz ...

  T(0) = c
  T(1) = c + 1
  T(2) = c + (c +1) + 2 = 2c + 1+2
  T(3) = c + (c + 1) + (2c + 1+2) + 3 = (4c +1+1+2+3)
  T(4) = c + (c + 1) + (2c + 1+2) + (4c + 1+1+2+3) + 4 = 8c +1+1+1+1+2+2+3+4
  ...
  T(n) = c*2^(n-1) + 1*2^(n-2) + 2*2^(n-3) + 3*2^(n-4) + ... + (n-1)*2^0 + n
       = c*2^(n-1) + sum(i*2^(n-i-1) for i := 1 to n-1) + n

Bu toplamayı biraz basitleştirebiliriz ...

  T(n) = c*2^(n-1) * 2^(n-1)*sum(i*2^(-i) for i := 1 to n-1) + n

Dolayısıyla, işlevin büyüme düzenine yönelik kapalı-formlu bir çözüm alma problemi, i * 2 ^ (- i) toplamının büyüme düzenini bulmaya indirgenir. Param, büyüme düzeninden daha iyisini yapabileceğinizi söylüyor ... bunun için kapalı bir form var mı? Her neyse, bu sorunun tam bir cevabı olmasa, yardım etmek için yeterli olacaktır.

1
katma