Dinamik sorunu (algoritmalar) - Dynamic problem (algorithms)

İle karıştırılmamalıdır değil dinamik programlama .

Dinamik problemler de hesaplama karmaşıklığı teorisi değişen veri girişi bakımından belirtilen sorunlardır. Aşağıdaki gibi en genel haliyle bu kategoride bir sorun genellikle belirtilmektedir:

  • giriş objelerinden oluşan bir sınıf göz önüne alındığında, girdi bir dizi ile ilgili belirli bir sorgu cevap vermek için etkin algoritmalar ve veri yapıları bulmak giriş veri yani nesneler eklenen veya silinen, her değiştiğinde nesneleri.

Bu sınıfın Sorunları karmaşıklık şu önlemleri:

  • Uzay  - miktarı bellek alanında veri yapısı depolamak için gereken;
  • Başlangıç zamanı  - veri yapısının ilk yapım için gerekli süre;
  • Ekleme süresi  - bir birden fazla girdi elemanı eklenir veri yapısının güncelleme için gerekli süre;
  • Silme zamanı  - bir giriş elemanı silinir veri yapısının güncelleme için gerekli süre;
  • Zaman sorgula  - bir sorgu cevaplamak için gereken süreyi;
  • Söz konusu probleme özgü Diğer işlemler

Dinamik bir sorun için hesaplamaların genel seti denir dinamik algoritma .

(Denilen sabit veri girişi bakımından belirtilen Birçok algoritmik problemler statik sorunlar bu bağlamda ve çözülmesi statik algoritmalar ) anlamlı dinamik versiyonu var.

Özel durumlar

Artan algoritmaları ya da çevrimiçi algoritmalar , elementlerin tek ilave muhtemelen boş / önemsiz veri girişi başlayarak izin verilen algoritmalar bulunmaktadır.

Azalan algoritmalar elemanlarının sadece silme tam veri yapısının bir başlatma ile başlayarak, izin verilen algoritmalar bulunmaktadır.

Eklemeler ve silmeler hem izin veriliyorsa, algoritma bazen denir tamamen dinamik .

Örnekler

maksimal eleman

Statik sorun 
N sayı kümesinin için maksimal olanı bulmak.

Sorun O (N) zaman içinde çözülebilir.

Dinamik sorun 
Ekleme ve silme izin verildiğinde, N numarasından oluşan bir dizi için, dinamik maksimum bir muhafaza.

Bu soruna yönelik bilinen bir çözüm kullanıyor kendini dengeleyen ikili arama ağacı . Bu, ilk olarak zaman O (N, N log) yapılabilir, boşluk O (N) alır ve O (log N) ekleme, silme ve sorgu süreleri sağlar.

Öncelikli kuyruk bakım sorunu
Biri sadece maksimal eleman silmek için gerektiren bu dinamik sorunun, basitleştirilmiş bir versiyonudur. Bu sürüm daha basit veri yapıları ile yapabilirsiniz.

Grafikler

kenarlarından yerleştirme ve silinmesi izin verildiğinde bir grafiktir göz önüne alındığında, bu gibi bağlantı, maksimum derecede, en kısa yol olarak parametrelerini, muhafaza.

Ayrıca bakınız

Referanslar

  1. ^ D. Eppstein , Z. Galil ve GF Italiano . "Dinamik grafik algoritmaları". In CRC Algoritma Handbook ve Hesaplama Teorisi , Bölüm 22. CRC Press, 1997.