Bilmek istediğin her şeye ulaş

Rekürsif (özyinelemeli) fonksiyon içeren bir algoritmanın zaman karmaşıklığını nasıl bulabiliriz?

Örnek olarak basit bir program kod parçası: def foo(n): if n return 0 return foo (n-1) + nDüzenle
Öncelikle Merhabalar. Recurrence (özyineli) problemlerin çözümü için MASTER THEOREM* kullanılmaktadır. Master Theorem'in temel formülü şu şekilde ifade edilir:

T(n) = aT(n/b)+f(n)

Burada bilinmesi gereken en önemli nokta bu denklemi Faktoriyel ve ya fibonacci fonksiyonları için kullanamayacağınızdır. Peki neden faktoriyel ve ya fibonacci fonksiyonları için master theorem kullanamayız diye sorabilirsiniz doğaldır. Bunun sebebi aslında her iki fonksiyon çeşidinin de Master theoremin temel denklemi olan T(n) = aT(n/b)+f(n) 'a çevrilememesidir. Peki bu benim ne işime yarayacak? Sorumun cevabı nerede diyorsanız şöyle yardımcı olayım öncelikle kodunuzu ya da algoritmanızı T(n) = aT(n/b)+f(n) formatına çevirmeniz gerekmekte daha sonra Master theoremin diğer özelliklerini uygulayıp sonucu elde edebilirsiniz. Master theoremi uzun uzun anlatmak isterdim fakat ne yazık ki o kadar vaktim yok ancak size yol göstermesi açısından şu linkleri paylaşabilirim:

1.Nebraska University Department of Computer Science (Christopher M. Bourke,: Berthe Y. Choueiry):cse.unl.edu/~choueiry/s06-235/files/mastertheorem.pdf

2.Dartmouth College Departmen of Math: math.dartmouth.edu/archive/m19w03/public_html/section5-2.pdf

3.Saylor'dan bir kaynak:
saylor.org/site/wp-content/uploads/2011/06/master-theorem.pd...

4. faculty.ycp.edu/~dbabcock/pastcourses/cs360/lecture/lecture0...

5.Delaware University: eecis.udel.edu/~saunders/courses/621/11s/notes/notes/master-...

6. Ontario: csd.uwo.ca/~moreno//cs424/ressources/master.pdf (BOL ÖRNEKLİ)

Son olarak konu ile ilgili video:



Tam olarak sorunuzu çözmedim fakat görünürde cevabı

T(n) = Θ(nlg 2)

Fakat siz yine de linklerden araştırıp adım adım çözerseniz daha yararlı olur :)
  • Paylaş
BigO hesabı yapmak için fonksiyonun ne kadar çalıştığını bulmak gerekiyor. Bu durumda "n" den başlayarak fonksiyonun her execution'unda n=n-1 olarak 0'a gidiyor. Yani fonksiyon n kere çalışacak. Dolayısı ile Big(0)=n yani linear execution time sahibidir.
  • Paylaş
Merhaba; Hangi dilde soruyorsunuz sorduğunuz dil Python mu? Ve zaman karmaşasından kastınız nedir? Biraz daha açıklayıcı olabilir misiniz?
  • Paylaş
Örnekte tek satır halinde verilen kod Python kod parçası. Bloglar halinde yazmadığım için anlaşılmamış şimdi farkettim :) yürtme zamanı (running time) ve big-O notasyonu ile iligli sorum. verilen programda yürütme zamanını nasıl hesaplayabilirim ?
  • Paylaş
7

Patron, Sorduğun soruya cevap vermek isterdim ancak Python - Running time using Big Θ notasyonunun kullanımını bilmiyorum. Yani Python dili ve metodları hakkında bilgim yok. Eminim bilgisi olan bir arkadaş en kısa zamanda yardım edecektir. Ancak şu vereğim arama sonuçlarından isterseniz bir bakın derim işe yarar bir kaç şey çıkabilir ;

"python running time notation execution time"
"python running time notation yürütme zamanı" ben inceledim. istersen sende bak.

İsmet Acar, running time's programlama dillerinden bağımsız olduğunu sanıyordum. yanılıyor muyum? c ile yazılmış aynı algoritmanın yürütme zamanı da aynı olacaktır. PYthon ile ilgili eksiklerden kaynaklandığını sanmıyorum. Ama yanılıyor da olabilirim. araştıracağım teşekkürler

Patron, Demek istediğim bu . C# da kodun çalışma süresini hesaplamak için kullandığım nesne Python dilinde de kullanabiliyorsan yardımcı olayım. Bağımsız derken doğru diyorsun bağımsız ancak kaynak bakımından farklı.

İsmet Acar, C# bilgim çok iyi değil ama kullandığınız nesne nedir? Sizin kullandığınız nesnenin Py deki karşılığının ne olduğunu araştırabilirim. ek olarak sorumun cevaplanması için şu şekilde bir düzeltme yapayım:
yazılan herhangi bir rekürsif fonksiyon içeren kod'un yütüme zamanı matematiksel olarak nasıl ifade edilebilir.

Patron, Veri yapısını matematiksel olarak ifade biçimi örneğini, iş çıkışı size proje biçiminde göndereceğim. O zaman daha yararlı olacaktır. Sizde inceler ona göre pyde bulursunuz.

Vudu Cayld, @ByMFB burada sorulan konunun dil ile alakası yok. Burada istenilen şey bu kodun kaç saniyede çalışacağı değil, -muhtemel- veri büyüklüğünün çalışma zamanına nasıl bir etkisi olacağını görmektir.

İsmet Acar, @ByMFB ilgilendiğiniz için teşekkürler. @vudu nun söylediği tam olarak sormak istediğim soruydu. bunu bir örnek üzerinden (py ve py de yazılan bir fonksiyon) anlatmaya çalıştım.

Sonraki Soru
HESAP OLUŞTUR

İstatistikler

2082 Görüntülenme6 Takipçi4 Yanıt