Büyük O Logaritmik ne zaman bilinir?

Sorumu, "Plain English Explanation of Big O" numaralı gönderiden kaynaklanmaktadır. Logaritmik karmaşıklığın tam anlamını bilmiyorum. Zaman ve işlem sayısı arasında bir regresyon yapabileceğimi ve X karesi değerini hesaplayabileceğimi ve karmaşıklığı belirleyebileceğimi biliyorum. Ancak, kağıda hızlı bir şekilde karar vermek için bir yöntem bilmek istiyorum.Büyük O Logaritmik ne zaman bilinir?

Logaritmik karmaşıklığı nasıl belirlersiniz? Bazı iyi kriterler var mı? Genelde,

kaynak

2009-04-15 Léo Léopold Hertz 준영

Bunun ne anlama geldiğinden emin değilsiniz, ancak ... logaritmik karmaşıklık genellikle, kökte 1 düğüm içeren ve 2 çocuk içeren dengeli bir ikili ağaç gibi yayılmış veri yapısıyla çalışırken ortaya çıkar. 4 torun, 8 torun, vb. Temel olarak her seviyede düğüm sayısı bir faktör (2) ile çarpılır ama yine de bunlardan sadece bir tanesi iterasyonda yer alır. Veya başka bir örnek olarak, bir döngü içinde endeks her adımda iki katına: Böyle

for (int i = 1; i < N; i *= 2) { ... }

şeyler logaritmik karmaşıklık imzaları bulunmaktadır.

kaynak

2009-04-15 00:28:06

+1 çok ilginç. Örneklerinize benzer bir şey arıyorum. Algoritma logartihmic olarak: (int i = BIG_number; i> N; i * = 1/2) {...} –

1/2, tamsayı bölmesinde sıfırdır, ancak bunun yerine "i/= 2" kullanırsanız , Evet öyle. (Eğer merak ettiğiniz belirli bir algoritma ise, bu soruya dahil etmek iyi bir fikir olabilir.) –

Master theorem genellikle çalışır.

kaynak

2009-04-15 00:15:12

Bunu düşünmek biraz zor ama ustalaştıktan sonra çok iyi. – samoz

Kesin değil, ancak her iterasyonda yapılması gereken işi esasen bölen bir algoritmaya sahipsiniz, o zaman logaritmik karmaşıklığa sahipsiniz. Klasik örnek ikili aramadır.

kaynak

2009-04-15 00:18:56

zorunlu olarak değil. Neyi ima etmeye çalıştığınızı anlıyorum ama sadece işi yarıya böldüğünüz için logaritmik bir karmaşıklık aldığınız anlamına gelmiyor, hatta bu konu için üstel zamana sahip olabilirsiniz. Çözümlerin nasıl yeniden birleştirildiğini ve bölünmüş sorunların nasıl çözüldüğünü de not etmelisiniz. Rekombinasyon aşamasının baskın olduğu birçok durum vardır. Master Teorem'e bakın veya teoremi olmadan nüksetmeyi daha iyi çözün. Basit bir nüksün altında birçok sürpriz var. – unj2

@unjaan: Sanırım beni yanlış anladın. İşi yarıya bölmedim demedim, "Her iterasyonda yarıya kadar yapılması gereken iş" dedim. Demek istediğim, eğer her adımda, bir önceki adıma göre yapılması gereken işin yarısı ise, o zaman logaritmik karmaşıklığınız vardır (iş için, hesaplamaları oku). –

Sadece logaritmik Big Oh hakkında bilgi sahibi olmak istiyorsanız, verilerinizin her yinelemenin yarısında kesildiği zaman uyanık olun.

Bunun nedeni, daha önceki adım kadar büyük olan verileri işliyorsanız, sonsuz bir dizidir.

kaynak

2009-04-15 00:19:02 samoz

Mutlaka 1/2 değil.C/s sabit olduğu sürece 1/c çalışır. –

ama 1/2 daha 'intibaative' –

Genellikle Big O hakkında konuşurken, günlüğü log tabanı 2 demektir. – samoz

İşte bunu söylemenin başka bir yolu.

Algoritmanızın, sorunun boyutundaki basamak sayısına doğrusal olduğunu varsayalım. Bu nedenle, büyük bir sayıyı katmak için yeni bir algoritmaya sahipsiniz, rakamların sayısında lineer olduğunu gösterebilirsiniz. 20 basamaklı bir sayı, algoritmanızı kullanarak 10 basamaklı bir sayı olarak iki kat daha uzun sürmektedir. Bu günlük karmaşıklığı olurdu. (Ve mucit için bir şeye değecektir.)

Bileğin aynı davranışı vardır. Aralık uzunluğunu 1024 = 2^10 katsayısıyla kesmek için yaklaşık 10 adet biseksiyon adımı gerekir, ancak sadece 20 adım aralığı 2^20'lik bir faktörle keser.

Günlük karmaşıklığı, her zaman tüm sorunlarda bir algoritmanın hızlı olduğu anlamına gelmez. O'nun (log (n)) önündeki lineer faktör büyük olabilir. Yani algoritmanız küçük problemler için korkunç olabilir, problem boyutu büyük ölçüde diğer algoritmaların üstel (veya polinom) ölümle sonuçlanana kadar faydalı olmayacaktır.

kaynak

2009-04-15 12:20:10

Büyük sorun büyüklüğü ile açıkladı. –

Büyük O Logaritmik ne zaman bilinir?

cevap

İlgili konular