Özyineleme veya yineleme belirli bir program için en iyisi olup olmadığını nasıl kontrol edebilirim?

Question

Üniversitemde Fibonacci serileri için bir JAVA programı yazmam istendi. Bu programı yazmak için özyineleme kullandım.

Ama

, asst öğretim görevlisi benim algo verimli olmadığını söyledi ve analiz etmemi istedi. Sözleşmeye göre, yinelemenin bu programda yinelemeden daha uygun olduğunu ekledi.

nasıl algoritmayı analiz etmek? Hem yineleme hem de tekrarlamada yer ve zaman karmaşıklığı nasıl kontrol edilir? Hemen sonra, bu şeylerin bir PROGRAMIN DÜZELTİLMESİ kadar önemli olduğunu gördüm.

Answer 1

bir thumbrule olarak

:

• Özyineleme insanlar için anlaşılması kolaydır. Ancak yığın tabanlı ve yığın her zaman sınırlı bir kaynaktır.
• Yineleme bir sıralıdır ve aynı zamanda hata ayıklamak daha kolaydır. Ancak zaman zaman özyineleme yoluyla kolayca yapılabilen algoritmaları anlamak zor olabilir.

Bu nedenle, adım sayısı küçük bir yönetilebilir numarayla sınırlı olduğunda, yinelemeye gidebilirsiniz. Güvenebileceğinizden dolayı, yığın asla taşmayacak ve aynı zamanda özyineleme kodu compact and elegant'dur. Bu yardımcı olabilecek daha keşfetmek istiyorsanız

. Recursion vs loops ve Recursion or Iteration?

Düzenleme olarak @MrP tarafından işaret bazı special özyinelemeli bağıntılar, bazı derleyiciler tarafından optimize edilebilir.

Answer 2

Bu algoritmanın karmaşıklığı ile ilgisi yoktur

: çağırmayı bir kullandığınızda - özyineleme sen StackOverflow'daki içine çalışabilir :)

çok derin eğer öyleyse - Her çağrı yığını üzerinde yeni bir çerçeve oluşturur

Yinelemeyi kullanarak - StackOverflow perspektifinden daha hızlı ve daha güvenli olan aynı boşluk üzerinde (potansiyel olarak önceki parametrelerin geçersiz kılınması) bir döngüde (potansiyel olarak) çalışıyorsunuz.

Answer 3

Sana bağlantıyı http://nptel.iitm.ac.in/courses.php?disciplineId=106 takip edip Tasarım ve Algoritma Analizi bazı dersler bulmak için öneririm. Algoritma tasarımı çok temel bir kavram. İyi şanslar.

Answer 4

Fibonacci serisi ile en büyük sorun, basit özyinelemeye kullandığınızda, her şeyi yeniden hesaplama ve çift bir sürü iş yapacağız, algoritmanın zaman karmaşıklığı olduğunu. Eğer fib hesaplamak (n) fib (n-2) ve fib (n-3) hesaplar fib (n-1), hesaplama olacak

int fib(int n) { 
    if (n < 2) { return 1; } 
    return fib(n-1) + fib(n-2) 
} 

kullanılarak olmasıdır. Fakat fib (n) 'yi hesaplamak için, zaten fib'i (n-2) hesaplayacaksınız. Bunu iyileştirmek için geçici sonuçları saklamanız gerekir. Bu, yinelemeyi kullanarak ve i = 0'dan n'ye geçerek genellikle daha kolaydır. Bu sayede son iki sonucu kolayca saklayabilir ve aynı değerleri tekrar tekrar hesaplamaktan kaçabilirsiniz.

bir algoritma verimli olup olmadığını görmek için kolay bir yol denemek ve birkaç giderek daha zor örnekler için bunu çözmek etmektir. Ayrıca daha doğru bir şekilde hesaplayabilirsiniz. Yukarıdaki fibonacci örneğini alın. Fib (n) çağrısı, karmaşıklığı O(fib(n)) = O(fib(n-1)) +O(fib(n-2)) + 1 alır (ek için sadece 1 tane alalım).Şimdi O(fib(0)) = O(fib(1)) = 1 olduğunu varsayalım. Bu O(fib(2)) = 3, O(fib((3)) = 5, O(fib(4)) = 9 anlamına gelir. Gördüğünüz gibi, bu seri fibonacci serisinden daha hızlı olacaktı! Bu, büyük miktarda artan karmaşıklık anlamına gelir. 0 ile n arası bir döngü ile yinelemeli bir algoritma elde edeceğiniz zaman, karmaşıklığınız n'nin sırasına göre ölçeklenir ve bu da daha iyi olur. Daha fazla bilgi için

, büyük-o gösterimini kontrol edin.