Soru Birleştirme neden en kötü durum çalışma zamanı O (n log n)?


Birisi bana basit İngilizce ya da açıklamak için kolay bir yolla açıklayabilir mi?


44
2017-10-18 02:43


Menşei


sıralama algoritmalarını izlemek her zaman eğlenceli: sorting-algorithms.com - Cliff


Cevaplar:


"Geleneksel" birleştirme türünde, verilerden her biri, sıralanmış alt bölümlerin boyutunu iki katına çıkarır. İlk geçişten sonra, dosya iki uzunluk bölümlerine ayrılacaktır. İkinci geçişten sonra, dördüncü. Ardından dosyanın boyutuna kadar sekiz, onaltı, vb.

Tüm dosyayı içeren bir bölüm bulunana kadar sıralanmış bölümlerin boyutunu ikiye katlamak gerekir. Dosya boyutuna ulaşmak için bölüm boyutunun lg (N) iki katına çıkar ve verilerin her geçişi kayıtların sayısıyla orantılı olacaktır.


27
2017-10-18 02:47



Bu iyi bir cevap, ama anlayabilmem için birkaç kez okumam gerekiyordu. Bir örnek yardımcı olabilir ... ör. Diyelim ki 8 sayının bir listesi var. Bunları uzunluğun alt listelerine bölüyorsunuz, 1. 8 üye uzunluğunda bir liste almak için 3 kat veya lg (8) alacak. Word vaka senaryosunda, her alt listenin her üyesini bir kez kontrol etmeniz gerekir, bu da üç katın her biri için, tüm 8 değeri kontrol etmeniz gerekir. - Goodword
Sadece böyle bir örnek ekledim; Bundan daha iyisini severmisin? - supercat


Sırala Birleştir kullan Bölmek ve fethetmek sıralama problemini çözme yaklaşımı. İlk olarak, girişi özyineli olarak ikiye böler. Bölünmesinden sonra, yarıları sıralar ve bunları bir sıralı çıktıya birleştirir. Şekle bakın

MergeSort recursion tree

Bu, probleminizin yarısını önce sıralamak ve basit bir birleştirme alt yordamı yapmak daha iyi demektir. Bu nedenle, birleştirme alt yordamının karmaşıklığını ve yinelemede kaç kez çağrılacağını bilmek önemlidir.

İçin sözde kod birleştirme sıralama gerçekten çok basit.

# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
    if A[i] < B[j]
        C[k] = A[i]
        i++
    else
        C[k] = B[j]
        j++

Her döngüde 4 işleminiz olacağını görmek kolaydır: k ++, i ++ veya j ++, if deyimi ve ilişkilendirme C = A | B. Böylece, 4N + 2 operasyonuna daha az veya eşit bir şekilde sahip olacaksınız. O (N) karmaşıklık. İspat için 4N + 2 6N olarak kabul edilecektir, çünkü N = 1 için doğrudur (4N +2 <= 6N).

Yani, bir girişiniz olduğunu varsayalım N- elementler ve varsayalım N- 2'nin gücüdür. Her seviyede, önceki girişten yarım elemanlı bir girişe sahip iki kat daha fazla alt probleminiz vardır. Bu, bu seviyede olduğu anlamına gelir j = 0, 1, 2, ..., orada olacak 2 ^ j uzunluğa sahip alt problemler N / 2 ^ j. Her seviyede operasyon sayısı j daha az veya eşit olacak

2 ^ j * 6 (N / 2 ^ j) = 6N

Her zaman daha az veya eşit 6N işlemlere sahip olacağınız seviyenin önemli olmadığını gözlemleyin.

LgN + 1 seviyeleri bulunduğundan, karmaşıklık

O (6N * (lgN + 1)) = O (6N * lgN + 6N) = O (n lgN)

Referanslar:


60
2017-07-02 21:49



Neden ilk n küçük harf ama ikinci N büyük harfe? Bunun bir önemi var mı? - Pacerier
Belki ben kötüyüm ama 2^j * 6(N / 2^j) = 6N 2 operasyon daha var. iyi, önemli değil, ama bu durumda şöyle görünmelidir: 2^j * 6(N / 2^j) + 2 = 6N  ve dediğiniz gibi, daha az veya eşit 6N operasyonları olacak - Jorman Bustos
Mükemmel bir açıklama! - Giri


Bunun sebebi, en kötü durum veya ortalama durum mu olsun, birleştirme dizisi, diziyi her aşamada iki yarıya böler; bu, lg (n) bileşenini verir ve diğer N bileşeni, her aşamada yapılan karşılaştırmalardan gelir. Böylece birleştirmek neredeyse O olur (nlg n). Ortalama durum ya da en kötü durum olursa olsun, lg (n) faktörü daima mevcuttur. Rest N faktörü, her iki durumda yapılan karşılaştırmalardan elde edilen karşılaştırmaya bağlıdır. Şimdi en kötü durum, her aşamada bir N girdisi için N karşılaştırmanın gerçekleştiği durumdur. Böylece bir O (nlg n) olur.


20
2017-10-18 18:36





Diziyi tek bir öğeye sahip olduğunuz sahneye böldükten sonra, bunları alt listeler olarak adlandırın.

  • Her aşamada, her alt listenin elemanlarını bitişik alt listesiyle karşılaştırırız. Örneğin, [Davi’nin resmini yeniden kullanma ]

    enter image description here

    1. Aşama-1'de her eleman, bitişik bir, yani n / 2 karşılaştırmaları ile karşılaştırılır.
    2. Aşama-2'de, alt listenin her elemanı bitişik alt listesiyle karşılaştırılır, çünkü her alt liste sıralanır, bu iki alt liste arasında yapılan maksimum karşılaştırmanın sayısıdır. <= Alt listenin uzunluğu yani 2 (Aşama 2'de) ve Alt listeler ikiye katlanmaya devam ettiğinden, Aşama-3 ve Aşama-4'teki 4 karşılaştırmalar. Yani her aşamadaki maksimum karşılaştırma sayısı = (alt liste uzunluğu * (alt sayıların sayısı / 2)) ==> n / 2
    3. Gördüğünüz gibi toplam aşama sayısı log(n) base 2 Böylece toplam karmaşıklık == (her aşamada maksimum karşılaştırma sayısı * aşama sayısı) == O ((n / 2) * log (n)) ==> O (nlog (n))

15
2017-08-05 18:47





MergeSort algoritması üç adımı alır:

  1. bölmek adım alt dizinin orta konumunu hesaplar ve sabit zaman alır O (1).
  2. Fethetmek  adım, her biri yaklaşık n / 2 öğesinin iki alt dizisini yinelemeli olarak sıralar.
  3. birleştirmek  adım, her geçişte en fazla n karşılaştırması gerektiren toplam n öğesini birleştirir, böylece O (n) alır.

Algoritma, n elemanlarının bir dizisini sıralamak için yaklaşık logn geçişler gerektirir ve böylece toplam zaman karmaşıklığı nlogn olur.


2
2018-02-05 15:16





Diğer cevapların çoğu harika, ama hiç bahsetmedim yükseklik ve derinlik "birleştirme ağacı" örnekleri ile ilgili. İşte bu soruya ağacın üzerinde yoğunlaşmak için başka bir yol var. Açıklamaya yardımcı olacak başka bir resim: enter image description here

Sadece bir özet: diğer cevapların işaret ettiği gibi, dizinin iki sıralı dilimini birleştirmenin işinin doğrusal zamanda (ana sıralama fonksiyonundan aradığımız birleştirme yardımcı fonksiyonu) çalıştığını biliyoruz.
Şimdi, bu ağacın bakışı, her bir kökten (kökten başka), ayıklama işlevine tekrarlayıcı bir çağrı olarak düşünebileceğimiz yere bakalım, her bir düğüm üzerinde ne kadar zaman harcadığımızı değerlendirelim. Dizi ve birleştirme (her ikisi birlikte) doğrusal zaman alır, herhangi bir düğümün çalışma süresi, o düğümdeki dizinin uzunluğuna göre doğrusaldır.

Burada ağaç derinliği gelir. Burada n, orijinal dizinin toplam boyutuysa, herhangi bir düğümdeki dizinin boyutu n / 2'dir.ben, ben derinlik olduğum yer. Bu, yukarıdaki resimde gösterilmektedir. Bunu her bir dilim için doğrusal iş miktarı ile bir araya getirdiğimizde, bir O (n / 2) çalışma süresine sahibiz.ben) Ağaçtaki her düğüm için. Şimdi bunu sadece n düğümleri için toplamalıyız. Bunu yapmanın bir yolu, 2 tane olduğunu fark etmektir.ben Ağacın her derinlik seviyesinde düğümler. Yani herhangi bir seviye için, O (2) varben * n / 2ben), yani O (n) çünkü 2'yi iptal edebilirizbens! Eğer her derinlik O (n) ise, bunu sadece yükseklikBu ikili ağacın, günlüğe kaydeder. Cevap: O (nlogn)

referans: Python'da Veri Yapıları ve Algoritmalar


2
2017-12-29 03:24



Güzel açıklama! Teşekkürler. - everlasto


Algoritma birleştirme-sıralama, O (n log n) içinde boyut n'nin bir dizisini S sıralar. Zaman, S'nin iki elemanının O (1) zamanda karşılaştırılabileceğini varsayar.enter image description here


1
2018-06-18 23:19





Özyineli ağaç derinliği olacak log(N)ve o ağacın her seviyesinde kombine yapacaksınız N iki sıralı dizileri birleştirmek için çalışın.

Sıralı dizileri birleştirmek

İki sıralı diziyi birleştirmek için A[1,5] ve B[3,4] Sadece başlangıçtan başlayarak, iki dizinin arasındaki en düşük öğeyi seçerek ve bu dizinin işaretçisini artırarak yineleyin. Her iki işaretçi de ilgili dizilerin sonuna ulaştığında işiniz bitti.

[1,5] [3,4]  --> []
 ^     ^

[1,5] [3,4]  --> [1]
   ^   ^

[1,5] [3,4]  --> [1,3]
   ^     ^

[1,5] [3,4]  --> [1,3,4]
   ^      x

[1,5] [3,4]  --> [1,3,4,5]
    x     x

Runtime = O(A + B)

Sıralama resmini birleştir

Yinelemeli çağrı yığınınız böyle görünecektir. İş, alt yaprak düğümlerinde başlar ve kabarcıklar.

beginning with [1,5,3,4], N = 4, depth k = log(4) = 2

  [1,5]    [3,4]     depth = k-1 (2^1 nodes) * (N/2^1 values to merge per node) == N
[1]  [5]  [3]  [4]   depth = k   (2^2 nodes) * (N/2^2 values to merge per node) == N

Böylece yaparsın N her birinde çalışmak k ağaçtaki seviyeleri, nerede k = log(N)

N * k = N * log(N)


0
2018-03-26 02:09