En iyi algoritmayı (asimptotik olarak) aramak ve diğer ayrıntıları göz ardı etmek

Bir problem üzerinde kaba kuvvet yaklaşımının, performans açısından yeterince iyi olmayan bir karmaşıklığa sahip olduğu durumlar vardır.

Örneğin örneğin alalım. Teta (n ^ 2).

Yinelemeli bir yaklaşım kullanarak Theta (nlogn) için geliştirilebilir.

Açıktır ki, asimptotik bir büyük ve daha büyük giriş N büyüme için alt yani, daha iyi performans için bu yana yinelemeli bir yaklaşım kullanmak tercih olacaktır.

Sorum şu:

Eğer N asimptotik olarak büyürken (yani böl ve ele geçirme yaklaşımı) daha büyük ve daha büyük hale gelirse, N'nin devasa girişleri üzerinde tekrarladığımızdan, sonunda yığınının tükenebileceği gibi, bunu görmezden gelmek gerçekçi değildir. ?
Büyük girdilerin bir sonucu olarak aslında hiç bir sonuç elde edemeyiz.

Bu ayrıntıları göz ardı edersek, belirli bir problem için en iyi algoritmayı seçeceğimizden nasıl emin olabiliriz?

 2
katma
Görünümler: 6
kaynak
ro ru fr es pt de hi bn ar
ilgili: Daha kötüsü daha iyidir. Bir örnek var mı?
katma yazar jfs, kaynak

2 cevap

Donanım yığınını kullanmadan özyineli algoritmalar uygulamak mümkündür. Yığın taşması olasılığı ciddi bir sorunsa, kendi yığınınızı uygulayabilir veya sadece özyinenin derinliğini sınırlandırabilirsiniz.

However, if the algorithm is dividing a set of data (of size n) recursively, then the number of recursions will be proportional to log n. This means that to exhaust a stack of size s you need data of size on the order of 2^s, which grows extremely quickly with s. People tend to not appreciate how quickly the exponential function is growing. My point is that with this type of algorithm (splitting a set of data in each recursive step) it is quite unlikely that the input data can be large enough to need so many recursions as to exhaust the stack.

EDIT: But then I'm not a professional programmer, so I'm lacking on the practical experience front.

4
katma
kaynak
"Donanım yığını kullanmadan" ne demek istediğinizden emin değil. Devamlı olarak kendini hatırlatmak için yardımcı fonksiyonlar, mevcut fonksiyon çerçevesini saklamak için yığını kullanın. @ Yi_H: Şimdi donanımı hesaba katıyorsunuz.Ama RAM modeli böyle şeyleri yok sayar. ..
katma yazar Cratylus, kaynak
@Szabolcs: Benim tarafımdan bir + 1.But var, diğer tarafta donanımın yanı sıra kullandığınız dil de var. Eğer sığ bir yığını olan Java'yı kullanırsanız, JVM parametreleriyle kurcalamaya başlamadıkça bir stackoverflow elde edersiniz.
katma yazar Cratylus, kaynak
@ user384706 Yani, belirli bir dilde kendisini çağıran bir işlev kullanmadan (matematiksel olarak) aynı algoritmayı uygulayabileceğinizi kastediyorum. Yorumunuzu yi'ye tekrar yazın: pratikte, 64 bit adres alanını tüketmek için yeterli miktarda koya sahip olamazsınız. Pratik düşüncelerimden başka, gelecekteki herhangi bir mimari için (bugün sahip olduğumuz belleğin 1000 katına sahip olacağımızı varsayalım), yığın alanının gerekli olduğunda kullanılabilir bellekle doğrusal olarak büyümesi muhtemeldir. > istif alanı (bu algo için) logaritmik olarak büyütüldü (çok daha yavaş).
katma yazar Szabolcs, kaynak
@ user384706 Tanımladığınız algoritma türü için pratikte yığın alanından asla çıkamayacaksınız. Diğer özyinelemeli algoritmalar için elbette bir yığın taşma olasılığını düşünmek önemlidir ...
katma yazar Szabolcs, kaynak
Örneğin: 64 bit mimaride adreslenebilir alan bunu s = 64 ile sınırlar; bu nedenle, her adım için yığın üzerinde ciddi miktarda bilgi depolamıyorsanız, yığınları tüketmez.
katma yazar Karoly Horvath, kaynak

İşte ilk gördüğüm çabuk bir şakadır:

f(x)
{
  for (;;)
  {
    if (x is trivial)
    {
      return;
    }
    x1 = one half of problem x
    x2 = other half of problem x
    if (x1 is the little half)
    {
      x = x2;
      f(x1);
    }
    else
    {
      x = x1;
      f(x2);
    }
  }
}

Bunun anlamı, her özyinelemeli çağrının problemin küçük bir yarısı olmasıdır - tipik olarak asıl sorunun büyüklüğünün yarısından daha azdır - ve problemin daha büyük yarısı iterasyon yoluyla yapılır. Sorun 2 ^ n boyutundaysa, yığın yalnızca n boyutunda olmalıdır, çok eşitsiz bölünmeler nedeniyle - n log n yerine n ^ 2'ye yakın bir zamana sahip olursanız bile.

"Gerçek maliyet", n log n zaman fakat yığın yığınları kullanan algoritmalara dayanıyorsa, n log n'de çalışan bir algoritmanın n log n'den daha fazla kullanma zamanına sahip olmadığına dikkat edin. bir yığın yığını, aslında, örneğin Bir Java tercümanı, programınızı kaçış özyinesine sahip olduğunuz izlenimi ile çökertir.

0
katma
kaynak
mcdowella: Gönderdiğiniz sözdizim kodunu gerçekten anlamıyorum. Büyük bölümün yinelemeli olduğu yer var mı? Büyük ve küçük parçalar için yineleme yaparsınız. zamanla çalıştırılan bir algoritma n log n zamanı yoktur. n log n belleğinden daha fazla kullan .Zaman ve boşlukları karşılaştırıyorsunuz.Bu ifadenin nasıl geçerli olduğunu göremiyorum. Bir algoritma 1 zaman adımı alırsa, analize göre ne kadar bellek kullanır? ?
katma yazar Cratylus, kaynak
Üzgünüm - hızlı sıralama benzeri programın yapısını çok basitleştirdim. petebecker.com/js/js200101.html - yazdığı yere bakın "Burada da problemden kurtulmak için, kuyruk özlemini ortadan kaldıran kodu sadece biraz daha akıllı hale getirmeliyiz. Eğer iki parçadan daha küçükler için sıralama yaparsak, ve döngü Daha büyükte, yığın kullanımını önemli ölçüde azaltacağız "
katma yazar mcdowella, kaynak
Saat döngülerinde - veya daha iyisi ise - bellek veriyolu döngülerini ölçüyorsanız, bir birim zaman en fazla bir bellek yazabilir. Daha teorik olarak, eğer programınız zaman alırsa n n ama n ^ 2 nolu alanı kullanıyorsa, n/log n bellek ünitelerini her bir birim için yazıyor, n daha büyük ve daha büyük olduğu için mantıklı değil.
katma yazar mcdowella, kaynak