Özyinelemeli Yöntemlerin Büyük Sayısı

Question

Basit özyinelemeli yöntemlerin büyük O'nu belirlerken zorluk yaşıyorum. Bir yönteme birden çok kez çağrıldığında ne olacağımı kafamda saramam. Şaşkınlık alanım hakkında daha spesifik olabilirdim, ama şu anda bazı hw sorularına cevap vermeye çalışıyorum ve hile yapmak istememenin yerine, bu gönderiye cevap veren herkesin basit bir özyinelemeli yöntemle geldiğini ve Söz konusu yöntemin büyük O'nun basit bir açıklamasını sağlar. (Tercihen Java'da ... öğrendiğim bir dil).

Teşekkür ederiz.

Answer 1

Siparişi yinelemeli olarak da tanımlayabilirsiniz. Örneğin, diyelim ki bir fonksiyonunuz var f. F (n) 'yi hesaplamak için k adımlarını alır. Şimdi f (n + 1) hesaplamak istiyorsunuz. F (n + 1) f (n) 'yi bir kez çağırır, sonra f (n + 1) k + bazı sabit adımlar alır. Her bir çağrı, bazı sabit adımlar ekstra alacak, bu nedenle bu yöntem O (n).

Şimdi başka bir örneğe bakın. İki önceki sonuçlar ekleyerek safça fibonacci uygulamak Diyelim:

fib(n) = { return fib(n-1) + fib(n-2) } 

Şimdi fib hesaplayabilirsiniz diyelim (n-2) ve fib (n-1) k adımları hakkında hem. Fib (n) yi hesaplamak için k + k = 2 * k adımlarına ihtiyacınız vardır. Şimdi fib'i hesaplamak istediğinizi söyleyelim (n + 1). Yani, fiberin (n-1) için iki kat fazla adım gerekir. Yani bu O (2^N)

gibi görünüyor. Kuşkusuz bu çok resmi değil, ama umarım bu şekilde birazcık hissedebilirsiniz.

Answer 2

Yinelemeli yineleme yöntemlerini bulmak için ana teoremize başvurmak isteyebilirsiniz. İşte wikipedia makalesi: http://en.wikipedia.org/wiki/Master_theorem

Ağaç gibi özyinelemeli bir sorun düşünmek istersiniz. Ardından, ağacın her seviyesini ve gerekli iş miktarını dikkate alın. Problemler genel olarak 3 kategoriye ayrılır, kök ağır (ilk iterasyon >> ağacın geri kalanı), dengeli (her seviyenin eşit miktarda işi vardır), yaprak ağır (son iterasyon >> ağacın geri kalanı). Örnek olarak

alınması birleştirme sıralaması:

define mergeSort(list toSort): 
    if(length of toSort <= 1): 
     return toSort 
    list left = toSort from [0, length of toSort/2) 
    list right = toSort from [length of toSort/2, length of toSort) 
    merge(mergeSort(left), mergeSort(right)) 

Sen sırayla mergesort her çağrı 1/2 orijinal uzunluğunun 2 daha mergeSorts çağırır görüyoruz. Birleştirme prosedürünün, birleştirilen değerlerin sayısına orantılı zaman alacağını biliyoruz. Nüksetme ilişkisi daha sonra T (n) = 2 * T (n/2) + O (n) şeklindedir. İki, 2 çağrıdan gelir ve n/2, her bir çağrıda sadece elemanların yarısına sahip olur. Bununla birlikte, her seviyede, birleştirilmesi gereken aynı sayıda eleman vardır, böylece her seviyede sabit çalışma, O (n) 'dir.

İşin eşit olarak dağıldığını biliyoruz (O (n) her bir derinlik) ve ağaç log_2 (n) derinliğindedir, bu nedenle özyinelemenin büyük O değeri O (n * log (n)) olur.