Büyük-O benim bilgim sınırlıdır, ve günlük terimleri denklem geldiğinde beni daha da bozuyor.

Birisi belki de O(log n) algoritma nedir basit bir dille bana açıklayabilir mi? Nerede logaritma nereden geliyor?

Bu özellikle bu ara pratik soru çözmeye çalışıyordum ne zaman geldi:

İzin X(1..n) ve Y(1..n) tamsayı, Her sipariş nondecreasing sıralanmış iki liste yer. O(log n) zaman medyan (veya n'inci en küçük tamsayı) 2n birlikte tüm öğeleri bulmak için bir algoritma verin. Eski, X = (4, 5, 7, 8, 9) ve Y = (3, 5, 8, 9, 10), sonra 7 medyan kombine listesi (3, 4, 5, 5, 7, 8, 8, 9, 9, 10). [İpucu: ikili arama kavramları kullanın]

Çok garip(log n) O bir algoritma gördüğün ilk defa katılıyorum... nereden bu logaritma nereden geliyor? Ancak, günlük bir dönem büyük-O gösterimi göstermek için birkaç farklı yolu vardır çıkıyor. İşte birkaçı:

Sürekli bir sabit bölme

N herhangi bir sayı atın;, 16 söylüyorlar. Kaç kere bir sayı daha az veya eşit olsun önce iki n dönemeyiz? 16, bizler için var

16 / 2 = 8
 8 / 2 = 4
 4 / 2 = 2
 2 / 2 = 1

Bu dört adımları tamamlamak için alarak biter dikkat edin. İlginçtir, biz de günlük var216 = 4. Hmmm... ne 128?

128 / 2 = 64
 64 / 2 = 32
 32 / 2 = 16
 16 / 2 = 8
  8 / 2 = 4
  4 / 2 = 2
  2 / 2 = 1

Bu yedi adım aldı, ve günlük2128 = 7. Bu bir tesadüf mü? Hayır! Bunun için iyi bir nedeni var. Ben 2 kat numarası n bölüyoruz varsayalım. Sayı / 2 n elde ederiz^ben. Bu değer, en fazla Biz 1, nerede değeri için çözmek istiyorsak

n / 2^ben≤ 1

&; 2 n le^ben

günlük2n ≤ ben

Eğer ben &ge gibi bir tamsayı ben alırsak diğer bir deyişle; günlük2n, daha sonra dalış sonra2 nben 1 kere en fazla bir değere sahip. Bu garanti en küçük ben günlük kabaca2eğer numarasını yeterince küçük olana kadar 2'ye bölen bir algoritma var yani n, o(günlük n) adımda sona erdirir söyleyebiliriz.

Önemli bir detay sabit (birden fazla olduğu sürece) n bölüyorsun ne olduğu önemli değil; eğer sürekli k tarafından bölmek, günlükkn 1 ulaşmak için gerekli adımları. Böylece art arda bazı farkla girdi boyutuna ayıran herhangi bir algoritma(günlük n) yineleme sona erdirmek gerekir. Bu yineleme zaman ve çok net çalışma zamanı, bir sürü O(log n) olması gerekmez sürebilir, ama adım sayısını logaritmik olacak.

Nerede bu nereden buldu? Bir klasik bir örneğidirbinary searchbir değer için sıralanmış bir dizi arama için hızlı bir algoritma. Algoritma şu şekilde çalışır:

• Eğer dizi boş ise, bu eleman dizide var olmayan bir dönüş.
• Aksi takdirde:
  • Dizinin orta elemanı bak.
  • Eğer aradığımız elemanın eşit olursa, başarı döndürür.
  • Eğer bu eleman daha büyük olsaydı arıyoruz:
    • Dizinin ikinci yarısını atın.
    • Tekrar ediyorum
  • Eğer bu eleman daha az olduğu sürece arıyoruz:
    • Dizinin ilk yarısını atın.
    • Tekrar ediyorum

Dizideki örneğin, 5 aramak için

1   3   5   7   9   11   13

İlk orta eleman bakardık:

1   3   5   7   9   11   13
            ^

7 ^ beri . 5 ve dizi sıralanmış olduğundan, 5 numara sadece iptal edebiliriz yani dizinin arka yarısı olamaz, biliyoruz. Bu yapraklar

1   3   5

Şimdi orta eleman buraya bakmak:

1   3   5
    ^

3 < 5, 5 ilk yarısı diziyi bırakmak atarız yani dizinin ilk yarısında görünür, gitmeyeceğini biliyoruz

        5

Yine bu dizinin orta bakmak:

        5
        ^

Bu tam olarak aradığımız sayı olduğu için 5 gerçekten dizideki olduğunu söyleyebiliriz.

Ne kadar verimli? Peki, her yineleme üzerinde kalan dizi elemanlarının en az yarısını heba ediyoruz. Algoritma dizi boş olarak durur ya da istediğimiz değer buluyoruz. En kötü durumda, bir öğe elemanları bitene kadar dizinin boyutunu yarıya devam edelim orada değil. Bu ne kadar sürer? Madem devam ediyoruz kesim dizideki yarısı tekrar tekrar, yapılacak en çok O(log n) yineleme beri kesemez dizideki yarısından fazlasını O(log n) kez önce tükendi dizi elemanları.

Genel ve teknik takip algoritmalarıdivide-and-conquer(kesme sorunu parçalara, çözümü bu parçaları koyarak, daha sonra sorun tekrar birlikte) eğilimi var logaritmik açısından onlar için bu aynı sebepten - tutamazsın kesme bazı nesne yarısından fazlasını O(log n) kez. Bakmak isteyebilirsinizmerge sortbu mükemmel bir örnek olarak.

İşleme seferinde bir basamak değerleri

Kaç basamak base-10 numarası n? Eğer bir sayı k basamaklı ise orada o zaman en büyük rakam 10 biraz fazla olurdu^k. K basamaklı en büyük sayı 999...9, k kez, ve bu 10 eşittir^{k 1}- 1. Eğer n k basamak olduğunu biliyorsak, bu nedenle, o zaman n değeri 10 en fazla olduğunu biliyoruz^{k 1}- 1. Eğer n bakımından k için çözmek istersek, onu alırız

&; 10 n le^{k 1}- 1

n 1 ≤ 10^{k 1}

günlük10(n 1) ≤ k 1

(log10(n 1)) - 1 ≤ k

Hangi k n 10 tabanındaki logaritma yaklaşık ediyoruz. Diğer bir deyişle, n basamak sayısı(log n) olur.

Örneğin, diyelim ki makine bir kelime sığacak kadar büyük olan iki büyük sayılar ekleme karmaşıklığını düşünün. Bu sayıları 10 tabanına ve sayılar m ve n ararız temsil alalım. Bir şekilde ilkokul yöntemi ile onları eklenti numaralarını yazmak için bir defada bir rakam, soldan sağa çalışma o zaman. Örneğin, 1337 eklemek ve 2065, gibi sayılar yazarak başlarız

    1  3  3  7
    2  0  6  5
==============

Son rakamı ekliyoruz ve 1 carry:

          1
    1  3  3  7
    2  0  6  5
==============
             2

Sonra ikinci-to-son ekliyoruz ("") sondan bir önceki ve 1 digit carry:

       1  1
    1  3  3  7
    2  0  6  5
==============
          0  2

Sonraki, üçüncü-son ekliyoruz ("") antepenultimate rakam:

       1  1
    1  3  3  7
    2  0  6  5
==============
       4  0  2

Son olarak, dördüncü-son ekliyoruz (""...İngilizce seviyorum) preantepenultimate rakam:

       1  1
    1  3  3  7
    2  0  6  5
==============
    3  4  0  2

Şimdi, ne kadar zahmetli bir iş mi yaptık? Yaptığımız toplam O(1) iş başına rakam (yani, sürekli bir işin tutarı), ve O(max{n günlük, günlük m}) basamak gereken işlenmiş. Bu iki sayı içinde her basamak için ziyaret etmemiz gerekiyor, çünkü O toplam(max{n günlük, günlük m}) karmaşıklığı verir.

Birçok algoritma bazı temel bir basamak üstünde(log n) O bir terim. Klasik bir örnektirradix sortbir seferinde bir basamak tamsayı olan., Taban sıralama birçok çeşidi vardır, ama genellikle U sıralanmış olan mümkün olan en büyük tamsayı olduğu zaman O(n log U) çalıştırın. Bu nedenle bu her pass gerektirir O(n) zaman, ve orada toplam O(log U) yineleme işlemi için gerekli her Ey(log U) basamaklı en büyük sayı olmak sıralanmış. Birçok gelişmiş algoritmalar Gabow's shortest-paths algorithm Ford-Fulkerson max-flow algorithm Ölçekleme versiyonu gibi bir defada bir rakam çalıştıkları için kendi karmaşıklığı içinde günlük bir dönem var.

Bu sorunu çözmek hakkında ikinci sorunuza gelince, daha gelişmiş bir uygulama araştırıyor this related question bakmak isteyebilirsiniz. Verilen genel yapı problemleri vardır tarif burada, şimdi yapabilirsiniz daha mantıklı nasıl düşünmek sorunları ne zaman senin bir günlük vadede sonuç çok isterdim tavsiyelerde karşı bakıyor cevap verene kadar verdiniz biraz düşündüm.

Bu yardımcı olur umarım!