Soru O (log n) tam olarak ne anlama geliyor?


Şu anda Big O Notation çalışma sürelerini ve amortize edilmiş zamanlarını öğreniyorum. Kavramını anlıyorum O (n) Doğrusal zaman, giriş büyüklüğünün algoritmanın orantılı olarak büyümesini etkilediği anlamına gelir ... ve aynı durum, örneğin, ikinci dereceden zaman için geçerlidir. O (n2) permütasyon jeneratörü gibi vs. O (n!) zaman, fakülteler tarafından büyür.

Örneğin, aşağıdaki işlev O (n) Çünkü algoritma girişiyle orantılı olarak büyür n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Benzer şekilde, yuvalanmış bir döngü varsa, zaman O (n) olur2).

Ama tam olarak ne O (log n)? Örneğin, tam bir ikili ağacın yüksekliğinin ne demek olduğunu söylemek ne demektir O (log n)?

Logarithm'in ne anlama geldiğini (belki de detaylı olarak değil) biliyorum: log10 100 = 2, fakat bir fonksiyonu logaritmik zamanla nasıl tanımlayacağımı anlayamıyorum.


1736
2018-02-21 20:05


Menşei


1 düğümlü bir ikili ağacın yüksekliği log2 (1) +1 = 1, 2 düğümlü bir ağacın yüksekliği log2 (2) +1 = 2, bir 4 düğümlü ağacın yüksekliği log2 (4) +1 = 3 ve yakında. Bir n-düğüm ağacının yüksekliği log2 (n) +1'e sahiptir, böylece ağaca düğümler eklemek, ortalama yüksekliğinin logaritmik olarak büyümesine neden olur. - David R Tribble
Çoğu cevapta gördüğüm bir şey, aslında "O (bir şey)" i tanımlamalarıdır. Algoritmanın çalışma süresi "bir şey" ile orantılı olarak büyür. "O (log n)" nin "tam anlamını" istediniz diye, bu doğru değil. Big-Theta gösteriminin sezgisel açıklaması, Big-O değil. O (log n) sezgisel olarak çalışma süresi büyür demektir en fazla "log n" ile orantılı: stackoverflow.com/questions/471199/... - Mehrdad Afshari
Her zaman hatırlıyorum ve O için örnek olarak fethetmek (log n) - RichardOD
Log tabanı 2'yi (temel 10 değil) fark etmek önemlidir. Bunun nedeni, bir algoritmadaki her adımda, kalan seçeneklerin yarısını kaldırır. Bilgisayar bilimlerinde hemen hemen her zaman log tabanı 2 ile uğraşırız çünkü sabitleri görmezden gelebiliriz. Bununla birlikte, bazı istisnalar vardır (örn. Quad Tree çalışma süreleri, log tabanı 4'tür). - Ethan
@ Ehan: Baz dönüşümü sadece sabit bir çarpım olduğundan, hangi tabanda olduğunuzu farketmez, formül, log_b (x) = log_d (x) / log_d (b) şeklindedir. Log_d (b) sadece sabit olacaktır. - mindvirus


Cevaplar:


Bir günlük zamanıyla bir işlevi nasıl tanımlayacağımı anlayamıyorum.

Logaritmik çalışma zamanı işlevinin en yaygın nitelikleri şunlardır:

  • Bir eylemin gerçekleştirileceği sonraki öğenin seçimi birkaç olasılıktan biridir ve
  • sadece bir tanesinin seçilmesi gerekecek.

veya

  • Eylemin gerçekleştirildiği elemanlar n hanesidir

Bu yüzden, örneğin, bir telefon rehberinde insanlara bakmak O (log n) 'dir. Kontrol etmene gerek yok her Doğru olanı bulmak için telefon rehberinde kişi; bunun yerine, isimlerinin alfabetik olarak nerede olduklarına bakarak basitçe bölme ve fethetme yapabilirsiniz ve her bölümde sonunda birisinin telefon numarasını bulmadan önce her bölümün bir alt kümesini keşfetmeniz gerekir.

Tabii ki, daha büyük bir telefon defteri daha uzun bir süre almaya devam edecektir, ancak ek boyuttaki orantılı artış kadar hızlı bir şekilde büyümeyecektir.


Diğer çalışma türlerini karşılaştırmak için telefon rehberi örneğini genişletebiliriz ve onların çalışma zamanı. Telefon defterimizin olduğunu varsayalım işletmeler benzersiz isimleri olan "Sarı Sayfalar" insanlar Benzersiz isimlere sahip olmayan "Beyaz Sayfalar". En fazla bir kişi veya işletmeye bir telefon numarası atanır. Belirli bir sayfaya çevirmenin sabit zaman aldığını da varsayalım.

Burada, telefon rehberinde yapabileceğimiz bazı işlemlerin en iyi olanından en kötüye doğru olan çalışma saatleri:

  • O (1) (en iyi durum): Bir işletmenin adı ve işletme adı verilen sayfa göz önüne alındığında, telefon numarasını bulun.

  • O (1) (ortalama durum): Bir kişinin isminin ve adının bulunduğu sayfa göz önüne alındığında, telefon numarasını bulun.

  • O (log n): Bir kişinin ismini verdiğinizde, henüz aramadığınız kitabın yaklaşık yarısında rastgele bir nokta seçerek telefon numarasını bulun ve ardından kişinin adının o noktada olup olmadığını kontrol edin. Ardından, kitabın, kişinin adının bulunduğu bölümünün yaklaşık yarısını tekrarlayın. (Bu, bir kişinin adı için ikili bir aramadır.)

  • O (n): Telefon numaraları "5" rakamını içeren tüm kişileri bulun.

  • O (n): Bir telefon numarası verildiğinde, o numaraya sahip kişiyi veya işletmeyi bulun.

  • O (n log n): Yazıcının ofisinde bir karışıklık vardı ve telefon defterimiz tüm sayfalarını rastgele bir sıraya yerleştirdi. Siparişi, her sayfanın ilk adına bakarak ve ardından bu sayfayı yeni, boş bir telefon rehberinde uygun yere yerleştirerek düzeltin.

Aşağıdaki örnekler için, şimdi yazıcının ofisinde bulunuyoruz. Telefon defterleri, her bir konut veya işletmeye postalanmayı bekliyor ve her telefon defterinde nereye postalanacağını belirten bir çıkartma var. Her kişi veya iş bir telefon rehberi alır.

  • O (n log n): Telefon defterini kişiselleştirmek istiyoruz. Bu nedenle, her bir kişiyi veya işletmenin adını belirlenmiş bir kopyasında bulacağız, sonra isimlerini kitapta daire içine alacak ve patronlukları için kısa bir teşekkür notu yazacağız.

  • O (n2): Ofiste bir hata oluştu ve telefon defterlerinin her girişinde telefon numarasının sonunda ekstra bir "0" var. Biraz beyazlaş ve her sıfırı çıkar.

  • O (n · n!): Telefon defterlerini yükleme platformuna yüklemeye hazırız. Maalesef, kitapları yüklemesi gereken robot haywire'ye gitti: kitapları kitaplara rastgele sıraya koymak! Daha da kötüsü, tüm kitapları kamyon üzerine yükler, sonra doğru sırada olup olmadıklarını kontrol eder ve eğer değilse, onları kaldırır ve yeniden başlar. (Bu korkmuş bogo sıralama.)

  • O (nn): Robotu düzeltiyorsunuz, böylece işleri doğru bir şekilde yüklüyor. Ertesi gün, iş arkadaşlarınızdan biri sizin için bir şaka oynar ve yükleme platformu robotunu otomatik baskı sistemlerine bağlar. Robot her zaman orijinal bir kitabı yüklemek için gittiğinde, fabrika yazıcısı tüm telefon defterlerinin bir kopyasını çıkarır! Neyse ki, robotun hata tespit sistemleri, robotun, yükleme için yinelenen bir kitapla karşılaştığında daha fazla kopya yazdırmaya çalışmadığı kadar karmaşıktır, ancak yine de basılan her orijinal ve yinelenen kitabı yüklemesi gerekir.


2182
2018-02-21 20:14



@cletus: Coincidental, korkarım. Onu aldım çünkü telefon defterlerinin büyük bir N'si var, insanlar ne olduklarını ve ne yaptıklarını anlıyorlar ve bir örnek olarak çok yönlü olduğu için. Ayrıca açıklamalarımda robotları kullanmalıyım! Her tarafta bir galibiyet. (Ayrıca, yanıtınız StackOverflow'da bile üye olmadan önce yapılmış gibi görünüyor!) - John Feminella
"Ofiste bir hata oluştu ve telefon defterlerinin her birindeki her giriş telefon numarasının sonuna ek bir" 0 "ekledi. Biraz beyazlaşıp her sıfırı kaldır." <- Bu sipariş N karesi değil. N, girişin boyutu olarak tanımlanır. Girişin boyutu telefon numarasıdır, yani kitap başına düşen sayı, kitap sayısıdır. Bu hala doğrusal bir zaman operasyonu. - Billy ONeal
@Billy: Bu örnekte, N Tek bir kitaptaki insan sayısıdır. Çünkü telefon defterindeki her kişi de kitabın kendi kopyasını alıyor, N  özdeş her biri N içindeki insanlar, O (N ^ 2). - John Feminella
O (1), garip bir şekilde vurgulandığı gibi en kötü durum yerine değil mi? - Svip
Sonunda mantıklı olan bir O (log n) tanımını bulmak için O (long⅝n! N-55/2) zamanımı aldı. +1 - iAteABug_And_iLiked_it


Bu soruya çok iyi cevaplar gönderildi, ama gerçekten önemli olanın bir örneğini - yani resimli cevabı - kaçırdığımızı düşünüyorum.

Tam bir ikili ağacın yüksekliğinin O (log n) olduğunu söylemek ne demektir?

Aşağıdaki çizimde ikili bir ağaç betimlenmiştir. Her seviyenin yukarıdaki seviyeye kıyasla düğüm sayısını iki katına çıkardığına dikkat edin (dolayısıyla ikili):

Binary tree

İkili arama karmaşıklığı ile bir örnektir O(log n). Şekil 1'deki ağacın alt seviyesindeki düğümlerin bazı ayrılmış koleksiyonlardaki öğeleri temsil ettiğini varsayalım. İkili arama, bir böl ve yönet algoritmasıdır ve çizim, bu 16 öğe veri kümesinde aradığımız kaydı bulmak için 4 karşılaştırmaya ne kadar ihtiyacımız olacağını gösterir.

Bunun yerine 32 elemanlı bir veri kümesine sahip olduğumuzu varsayın. Aradığımızı bulmak için artık 5 karşılaştırmaya ihtiyacımız olduğunu bulmak için yukarıdaki çizime devam edin; çünkü ağaç, veri miktarını çarptığımızda sadece bir seviye daha derine inmiştir. Sonuç olarak, algoritmanın karmaşıklığı logaritmik bir sıra olarak tanımlanabilir.

çizdirme log(n) Düz bir kağıt parçası üzerinde, eğrinin yükselişinin yavaşladığı bir grafikle sonuçlanır. n artışlar:

O(log n)


510
2018-02-21 22:22



"Her bir seviyenin yukarıdaki seviyeye kıyasla çift düğüm sayısını nasıl içerdiğine dikkat edin (bu nedenle ikili)" Bu yanlıştır. Ne anlattığın bir dengeli ikili ağaç. Bir ikili ağaç sadece her bir düğümün en fazla iki çocuğa sahip olduğu anlamına gelir. - Oenotria
Aslında, tam bir ikili ağaç olarak adlandırılan çok özel bir dengeli ikili ağaç. Cevabı düzenledim ama onaylayacak birine ihtiyacım var. - user21820
Tam bir ikili ağacın tamamen doldurulacak son seviyeye sahip olması gerekmez. Diyorum ki, 'tam ikili ağaç' daha uygun. - Mr. AJ
Cevabınız OP'nin asıl sorununa daha somut bir şekilde cevap vermeye çalışır, bu yüzden mevcut kabul edilen cevaptan (IMO) daha iyidir, ama yine de çok eksiktir: sadece bir yarım örnek ve 2 resim verin ... - nbro
Bu ağacın içinde 31 madde var, 16 değil. Neden 16 öğe veri seti deniyor? Üzerinde bulunan her düğüm bir sayıyı temsil eder, aksi takdirde verimsiz bir ikili ağaç olur: P - Perry Monschau


O(log N) temelde zaman doğrusal olarak zaman artar anlamına gelir n üstel olarak yükselir. Eğer alırsa 1 hesaplamak için ikinci 10 elemanlar, alacak 2 hesaplamak için saniye 100 elementler, 3 hesaplamak için saniye 1000 elemanlar vb.

O O(log n) bölüştürdüğümüzde ve algoritma türlerini feshettiğimizde ikili arama. Başka bir örnek, diziyi her bölüme ayırdığımız her zaman ve her seferinde hızlı sıralamadır. O(N) pivot eleman bulma zamanı. Bu yüzden N O(log N) 


464
2018-02-21 20:18



Diğer tüm kompozisyon cevaplarını döven üç bilgelik çizgisi ... :) Birisi eksikse, programlama bağlamında, kütüğün tabanı 2'dir (10 değil), yani O (log n) 10 saniye için 1 sn gibi ölçeklendirir. elemanlar, 20 için 2 sn, 40 vb. - nawfal
Anlaşılan, özlü ve açık, OP'den gelen son soru, logaritmik bir işlevi nasıl tanımlayacak olsa da, tam olarak ne değil? - Adam
evet, logaritmik fonksiyon üstel fonksiyona terstir. ((log x) tabanı a) (x gücü) tersidir. Bu fonksiyonların grafiklerle nicel analizi daha sezgisel olacaktır. - overexchange
Bu yanlış olmadığını farketmek için 3 okumaları bana götürdü. Zaman doğrusal olarak yükselir eleman sayısı üstel. Bunun anlamı daha az zamanda daha fazla eleman. Bu görselleştirenler için zihinsel olarak vergi logBir grafikte bilinen log eğrisi olarak. - Qix
İkili aramanın bir bölme ve fethetme algoritması olduğunu iddia ettiği bölüm haricinde, bunun çok iyi bir cevap olduğunu düşünüyorum. Öyle değil. - code_dredd


Aşağıdaki açıklama tam vakayı kullanmaktadır dengeli logaritmik zaman karmaşıklığını nasıl elde ettiğimizi anlamanıza yardımcı olacak ikili ağaç.

İkili ağaç, n büyüklüğündeki bir problemin, 1 nolu bir probleme ulaşana kadar n / 2 nolu alt-problemin alt-problemine bölündüğü bir durumdur:

height of a binary tree

Ve işte bu şekilde O (log n) elde edersiniz ki bu da bir çözüm elde etmek için yukarıdaki ağaçta yapılması gereken iş miktarıdır.

O (log n) zaman karmaşıklığı ile ortak bir algoritma, özdeş ilişki T (n / 2) + O (1) olan, yani ağacın sonraki her seviyesinde, problemi yarıya böldüğünüz ve sabit bir miktarda ek iş yaptığınız İkili Aradır.


198
2017-10-26 19:33



Burada acemi. Ağaç boyunun n = 1 boyutuna ulaşmak için özyineleme oranı olduğunu söyleyebilir miydiniz? - Cody


Aşağıdakileri yapan bir işleviniz varsa:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Sonra günlüğü alır2(n) zaman. Büyük o notasyonugevşek konuşma, ilişkinin sadece büyük n için doğru olması gerektiği anlamına gelir ve bu sabit faktörler ve daha küçük terimler göz ardı edilebilir.


121
2018-02-21 20:11



log2 (n) o (log n) ile aynı mı? - Sven van den Boogaart
Evet, burada başka bir cevap için nawfal yorumuna bakın: (kopyalama-yapıştırma) - programlama bağlamında, kütüğün temeli 2'dir (10 değil), bu yüzden O (log n) 10 eleman için 1 saniye gibi ölçekler, 20 saniye için 2 sn , 40 için 3 - Andrejs


genel bakış

Diğerleri, ağaç diyagramları gibi iyi bir diyagram örneği vermiştir. Basit bir kod örneği görmedim. Bu nedenle, açıklamaya ek olarak, farklı algoritma kategorilerinin karmaşıklığını göstermek için basit baskı ifadeleriyle bazı algoritmalar sağlayacağım.

Öncelikle, alabileceğiniz Logaritma hakkında genel bir fikre sahip olmak istersiniz. https://en.wikipedia.org/wiki/Logarithm . Doğal bilim kullanımı e ve doğal günlüğü. Mühendislik öğrencileri, log_10 (log tabanı 10) kullanacak ve bilgisayar bilimleri, bilgisayarlar ikili tabanlı olduğundan log_2 (log base 2) çok kullanacaktır. Bazen doğal günlüğün kısaltmasını görürsünüz. ln()Mühendisler normalde _10'u bırakır ve sadece log() ve log_2 kısaltılır lg(). Tüm logaritma türleri benzer bir şekilde büyür, bu yüzden aynı kategoriyi paylaşırlar. log(n).

Aşağıdaki kod örneklerine baktığınızda, O (1), sonra O (n), sonra O (n ^ 2) 'ye bakmanızı öneririm. Onlarla iyi olduktan sonra, diğerlerine bakın. Çok ince değişikliklerin aynı kategorileştirmeyle nasıl sonuçlanabileceğini göstermek için temiz örneklerin yanı sıra varyasyonları da ekledim.

O (1), O (n), O (logn), vb. Sınıflar veya büyüme kategorileri olarak düşünebilirsiniz. Bazı kategoriler diğerlerinden daha fazla zaman alacaktır. Bu kategoriler, algoritma performansının sipariş edilmesinde bize yardımcı olur. Bazıları n girdikçe büyüdükçe daha hızlı büyürler. Aşağıdaki tablo, bahsedilen büyümeyi sayısal olarak göstermektedir. Aşağıdaki tabloda log (n) log_2 tavanı olarak düşünün.

enter image description here

Çeşitli Büyük O Kategorilerinin Basit Kod Örnekleri:

O (1) - Sabit Zaman Örnekleri:

  • Algoritma 1:

Algoritma 1 bir kez merhaba yazdırır ve n'ye bağlı değildir, bu yüzden her zaman sabit zamanda çalışır, yani O(1).

print "hello";
  • Algoritma 2:

Algoritma 2, 3 kez merhaba yazdırır, ancak bir giriş boyutuna bağlı değildir. N büyürse bile, bu algoritma her zaman sadece 3 kez baskı yapar. Bu söylenen 3, bir sabit, bu yüzden bu algoritma da O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Logaritmik Örnekler:

  • Algoritma 3 - Bu "log_2" gibi davranır

Algoritma 3, log_2 (n) 'de çalışan bir algoritmayı gösterir. For loop katsayılarının ikincisini 2'ye kadarki geçerli değerine dikkat edin. i 1 ila 2 ila 4 ila 8 ila 16 ila 32 arasında ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Algoritma 4 - Bu "log_3" gibi davranır

Algoritma 4, log_3'ü gösterir. ihbar i 1'den 3'e 9'dan 27'ye gider ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Algoritma 5 - Bu "log_1.02" gibi davranır

Algoritma 5 önemlidir, çünkü sayı 1'den büyük olduğu ve sonucun tekrar tekrar kendisiyle çarpıldığı sürece, logaritmik bir algoritmaya baktığınızı gösterir.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Doğrusal Zaman Örnekleri:

  • Algoritma 6

Bu algoritma, merhaba n kere yazdırır.

for(int i = 0; i < n; i++)
  print "hello";
  • Algoritma 7

Bu algoritma, merhaba n / 2 kez yazdırılacağı bir varyasyon gösterir. n / 2 = 1/2 * n. 1/2 sabitini yok sayıyoruz ve bu algoritmanın O (n) olduğunu görüyoruz.

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Örnekler:

  • Algoritma 8

Bunu bir kombinasyon olarak düşünün O(log(n)) ve O(n). Döngülerin yuvalanması, O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Algoritma 9

Algoritma 9, algoritma 8 gibidir, ancak döngülerden her biri, varyasyonlara izin vermiştir; O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n karesi Örnekler:

  • Algoritma 10

O(n^2) döngüler için standart yerleştirerek kolayca elde edilir.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Algoritma 11

Algoritma 10 gibi, ama bazı varyasyonlarla.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n küplü Örnekler:

  • Algoritma 12

Bu algoritma 10 gibidir, ancak 2 yerine 3 döngülüdür.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Algoritma 13

12 algoritması gibi, ama yine de bazı varyasyonlarla O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

özet

Yukarıdakiler birkaç basit örnek ve analizleri gerçekten değiştirmeyen ince değişikliklerin nasıl yapılabileceğini göstermeye yardımcı olacak çeşitlemeler sunmaktadır. Umarım yeterince bilgi verir.


108
2018-04-26 22:50



Muhteşem. Gördüğüm en iyi açıklama. Eğer daha iyi olurdu O(n^2) bir kombinasyonu olarak not edilir O(n) ve O(n), yani O(n) * O(n) = O(n * n) = O(n^2). Bu denklem olmadan biraz zıplamak gibi bir şey. Bu, önceki açıklamanın tekrarıdır, ancak bu tekrarlamanın, okuyuculara anlama için daha fazla güven sağlayabileceğini düşünüyorum. - Eonil
Şaşırtıcı cevaplar için teşekkürler - Asthme
Bu sadece en iyi açıklamadır. - Edgar Kiljak


Logaritmik çalışma süresi (O(log n)) esasen çalışma süresinin orantılı olarak büyüdüğü anlamına gelir. logaritma giriş büyüklüğünün bir örneği - örnek olarak, eğer 10 öğe en fazla zaman alırsa xve en fazla 100 ürün alır, 2xve 10.000 öğe en fazla 4xo zaman O(log n) zaman karmaşıklığı.


84
2018-02-21 20:10



log2 veya log10 ilgisizdir. Sadece aynı mertebeden, yani hala aynı oranda büyüdükleri bir ölçek faktörü ile farklılık gösterirler. - Noldorin
Logaritmalarla ilgili eğlenceli şey, göreli yükseklikleri karşılaştırırken kullandığınız temelin önemli olmadığıdır. log 10,000 / log 100 Kullandığınız tablonun ne olduğuna bakılmaksızın 2'dir. - Anon.
Nitpicky olmak için, O (lg n) çalışma zamanının anlamı en fazla lg ile orantılı Tanımladığınız şey Theta (lg n).
@rgrig: Bu doğru. Büyük-O'nun üst-bağlı doğasını göstermek için birkaç "en fazla" düzenledim. - Anon.
@rgrig o O ve theta tarif eder: Theta (lg n), O (lg n) anlamına gelir. - klochner


Logaritma

Tamam, bir logaritmanın gerçekte ne olduğunu tam olarak anlamaya çalışalım.

Bir ipimiz olduğunu ve onu bir atla bağladığımızı hayal edin. Eğer ip doğrudan atlara bağlıysa, atın atması gereken güç (bir adamdan) doğrudan doğruya 1 olacaktır.

Şimdi ipin bir direğin etrafında döndüğünü hayal edin. Kaçmak için at şimdi çok daha fazla zor çekmek zorunda kalacak. Zaman miktarı, ipin pürüzlülüğüne ve kutbun büyüklüğüne bağlı olacaktır, ancak bir kişinin gücünü 10 ile çarpacağını varsayalım (ip tam bir dönüş yaptığında).

Şimdi ip bir kez ilmekli ise, at 10 kat daha zor çekilmelidir. Eğer insan at için onu gerçekten zorlaştırmaya karar verirse, ipi tekrar bir kutbun etrafına doyabilir ve 10 kat daha fazla güç kazanabilir. Üçüncü bir döngü, tekrar 10 kez daha gücü arttırır.

enter image description here

Her bir döngü için, değerin 10 arttığını görebiliriz. Herhangi bir sayı elde etmek için gereken dönüş sayısı, numaranın logaritması olarak adlandırılır, yani gücünüzü 1000 katına kadar 3 gönderiye ihtiyaç duyarız. 1,000,000.

3, 1000'in logaritmasıdır ve 6, 1.000.000 (taban 10) logaritmasıdır.

Öyleyse O (log n) aslında ne anlama geliyor? 

Yukarıdaki örneğimizde, 'büyüme oranımız' O (log n). Her ek döngü için ipimizin tutabileceği güç 10 kat daha fazladır:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Şimdi yukarıdaki örnek 10 tabanını kullanmıştı, ama neyse ki büyük o notasyondan bahsederken logun temeli önemsizdir.

Şimdi 1-100 arası bir sayı tahmin etmeye çalıştığınızı hayal edelim.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Şimdi bu hakkı elde etmek için 7 tahmin aldı. Ama buradaki ilişki nedir? Her ek tahminden tahmin edebileceğiniz en fazla öğe hangisidir?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Grafiği kullanarak, 1-100 arası bir sayıyı tahmin etmek için bir ikili arama kullanırsak bizi ele geçireceğimizi görebiliriz. en fazla 7 girişim. Eğer 128 rakamımız olsaydı, biz de 7 tane kesişme noktasını tahmin edebilirdik, ama 129 rakam bizi alır. en fazla 8 denemede (logaritmalarla ilişkilerde, 128 değer aralığında 7 tahmin, 1024 değer aralığı için 10 tahmin gerekir. 7, 128 logaritma, 1024 (taban 2) logaritmasıdır).

En fazla 'kalın' olduğumu fark ettim. Büyük o notasyon her zaman en kötü durum anlamına gelir. Şansınız varsa, sayıyı bir girişimde tahmin edebilirsiniz ve en iyi durum O (1), ama bu başka bir hikaye.

Her tahmin için veri setimizin daraldığını görüyoruz. Bir algoritmanın logaritma zamanının olup olmadığını belirlemek için iyi bir kuraldır.   Veri kümesinin her yineleme sonrasında belirli bir sıraya göre küçülüp küçülmediğini görmek için

Peki ya o (n log n)?

Sonunda bir lineraritmik zamanla karşılaşacaksınız O (n log (n) algoritması. Yukarıdaki başparmak kuralı tekrar uygulanır, ancak bu sefer logaritmik fonksiyonun n kere çalıştırılması gerekir, örn. bir listenin boyutunu küçültmek n kereBir mergesort gibi algoritmalarda oluşur.

Algoritmik zamanın n log n olup olmadığını kolayca belirleyebilirsiniz. Bir listeden (O (n)) yinelenen bir dış döngü olup olmadığına bakın. Sonra bir iç döngü olup olmadığına bakın. İç döngü ise kesme / indirgeme her iterasyonda ayarlanan veri, bu döngü (O (log n), ve böylece genel algoritma = O (n log n).

Feragatname: İp-logaritma örneği mükemmelden yakalandı W.Sawyer tarafından Mathematician'ın Delight kitabı. 


55
2017-10-08 14:27





O'nun (log N) sezgisel olarak, zamanın N'deki basamak sayısıyla orantılı olduğunu söyleyerek düşünebilirsiniz.

Bir işlem, her bir basamakta veya bir girişin bitinde sabit zaman çalışması gerçekleştirirse, tüm işlem, girdinin büyüklüğü değil, girdideki basamak veya bit sayısıyla orantılı zaman alacaktır; Böylece O (N) yerine O (log N).

Eğer bir işlem, her biri (3, 4, 5 .. katsayısı ile düşürülür) her biri yarıya indirgenmiş bir dizi sabit zaman kararını verirse, dikkate alınacak olan girdinin büyüklüğünü, kütük 2'ye (baz 3) orantılı zaman alır. O (N) yerine, girdinin N büyüklüğüne ait taban 4, baz 4 ...).

Ve bunun gibi.


54
2018-02-21 20:13



Çoğu açıklamadan yeterince doğru ve daha kolay kavranır, düşünüyorum. - T .
bir açıklaması log<sub>10</sub> N, bu mu? - LiuYan 刘研
@LiuYan 刘 研, hanelerin sayısının hangi bazda olduğunu söylemediler. Her halükarda, log₂ (n) = log₁₀ (n) / log₁₀ (2) ve 1 / log₁₀ (2) sabit bir çarpan olur. tüm diğer üslere uygulanan aynı prensip ile. Bu iki şeyi gösterir. Birincisi, üssü ne olursa olsun, taban (daha düşük taban, tahminde daha az "jag") ve O (log n) O (log n) olursa olsun, bu sonuca götüren hesaplama ne olursa olsun geçerlidir. . - Jon Hanna


O (log n) 'de çalışan bir algoritmayı zihinsel olarak görselleştirmenin en iyi yolu şu şekildedir:

Eğer problem büyüklüğünü çarpımsal bir miktarla artırırsanız (yani, boyutunu 10 ile çarpın), iş sadece bir katkı miktarı ile artırılır.

Bunu, ikili ağaç sorunuza uygulamak için iyi bir uygulamaya sahip olursunuz: ikili bir ağaçtaki düğüm sayısını ikiye katlarsanız, yükseklik yalnızca 1 artar (ek bir miktar). Tekrar ikiye katlarsanız, hala sadece 1 artar. (Tabii ki bunun dengeli ve böyle kaldığını varsayardım). Bu şekilde, problem boyutu çarpıldığında işinizi ikiye katlamak yerine, sadece çok daha fazla iş yapıyorsunuz demektir. Bu yüzden O (log n) algoritmaları harika.


48
2018-02-22 19:51





Ne günlüğüb(N)?

Boy l'in bir bölümüne ulaşmadan önce, n uzunluğundaki bir günlüğü tekrar tekrar b eşit parçalarına böldüğünüz sayıdır.


33
2018-03-19 19:28



Mükemmel Yorum! Özlü ve tam olarak sonra olduğum cevap. - DennisL
iyi açıklama - mAc