Iyi durumda ve bir programa (algoritma) en kötü durumda belirlemek nasıl?

3 Cevap php

Ben bu programı olduğunu varsayalım, ben 2 giriş listeleri karşılaştırmak istiyorum. Nasıl iyi durumda ve fonksiyon kötü durumda belirliyorsunuz dizi A ve dizi B. varsayalım?

Burada [php] benim kodu:

foreach($array_1 as $k){
    if(!in_array($k, $array_2)){
        array_push($array_2, $k);
    }
}

Döngüsü için en iyi durum ve en kötü durum nedir? Bazı explaination eklemeyi unutmayın, teşekkür ederim :)

GÜNCELLEME:

Amacım listelerde 1 ortak öğesi var 2 listeleri karşılaştırmak olduğu için. Ben yukarıdaki kodu yanlış olduğunu düşünüyorum. İşte benim kod güncellenir

foreach($array_1 as $k){
    if(in_array($k, $array_2)){
        array_push($array_3, $k);
    }
}

Ve ben bunun olacağını tahmin:

En iyi durum: O (n)

En kötü durumda: O (N * M)

3 Cevap

O zaman hızlı bir analiz yapalım:

foreach($array_1 as $k)

operasyon içinde dizinin her elemanı için tekrarlanır olacağı anlamına gelir. N ile dizinin boyutunu gösterelim.

Operasyon kapsamında:

if (!in_array($k, $array_2)) {
  array_push($array_2, $k);
}

2 işlemler var burada:

  • in_array
  • array_push

array_push, sabit olması muhtemeldir böylece O(1), in_array array_2 alacak işlemi 1 ya da daha fazla olası doğrusal ara iken array_2 işlemlerin uzunluğu kadar (birinci eleman olarak bulundu).

in_array burada tek değişkeni temsil ettiğini unutmayın:

  • En iyi durum: in_array ilk karşılaştırma sırasında döner -> array_1 tüm unsurları aynıdır, ve array_2 boş ya da ilk eşit ya öğesi. Karmaşıklığı O(N) biz N elemanları beri array_1
  • kötü durum: biz array_2 her elemanını incelemek her zaman -> tüm elemanları array_1 farklıdır ve onlar array_2 önceki unsurları farklıdır. M uzunluğu ise, o zaman girişinin yapılıp array_2, o karmaşıklık O(N * (N+M) ), (N+M)/2 ortalama olmanın hat boyunca o M+N elemanları ve sabiti M adlı büyüyor gibi array_2 içinde arama yapmak için zaman 2 {[(11) içinde atılmadan ]} notasyonu

Umarım bu yardımcı olur.

Büyük O notasyonu tüm yaklaşımları hakkında. Bu kolay algoritmaları karşılaştırmak için yapar.

Eğer elemanların diziyi hayal, bir arama (istediğiniz öğeyi bulmak için her öğenin bakmak gerekir) sipariş N olabilir, bu bir sipariş koleksiyona sahip olursa ya da sipariş 1 olabilir sipariş Log (N) olabilir toplama türüne bağlı.

Burada önemli şey algoritması bakmak ve anahtar işlemler tekrarlanır ki ne belirlemektir.

Foreach tanımı ile sizin listedeki her öğe üzerinde çalışması gereken, açıkça bir düzen N işlemdir. O (N)

Sonraki aşağıdadır inarray 2. eğer. Bu düzen N (doğrusal arama) olacağını çok büyük olasılıkla sırasız olacak bir dizi üzerinde yapılan aramada, gibi geliyor. Yani karmaşıklığı şimdi O (N * M) olacaktır. (Dizideki 1 her n elemanlar için, dizinin üzerinde 2 için N karmaşık bir arama gerçekleştirmek).

Son olarak bir dizi itme var. Ben ortamı bilmiyorum ama dizi büyümek için tahsis ve kopyalanması gerekiyorsa bu siparişin 1 veya sipariş N olabilir. Basit tutmak için düzen 1. varsayalım. Bu nedenle Big O sizin karmaşıklığı O (N * M) 'dir.

Yani şimdi iyi durumda O olacağını, her eleman bu ilk denemede meslektaşı bulmak ve dizi zorlaması gerçekleştirmek için (N * 1 * 1) = O (N).

En kötü durumda, her elemanı dizideki 2 tüm unsurların tam arama zorlayarak ikinci listede bulunamıyor olmasıdır. Dolayısıyla karmaşıklığı O (N * M) 'dir.

Öğretmenleriniz yüzden onlara yapılan varsayımlar göstermek düşünme anlamak istiyorum. Ben çok size burada verilen varsayımlara dayanarak önce, size tam ceza ve her durumda kullanılan algoritmalar söylerdim dil / platform söylendi olabilir verilmiş kesin soru ve bilgi okumanızı öneririz. Umarım ki olur :)

Genellikle bu tür bir sorun ile ben sadece Dr Evil algoritması bakmak ve soruyorum, "Nasıl bu mümkün most zaman alabilir yapabilir?"

etiketler