SORU
25 Mayıs 2009, PAZARTESİ


Herhangi bir O(1/n) algoritma var mı?

Herhangi bir O(1/n) algoritma var mı?

Veya O(1) ' den az olan başka bir şey var mı?

CEVAP
25 Mayıs 2009, PAZARTESİ


Bu soru göründüğü kadar aptal değildir. En azından teorik olarak, bir şey gibiÇ(1/nBig O notation matematiksel tanımını alırsak ) tamamen mantıklı

enter image description here

Şimdi kolayca yerine kullanabilirsinizg(x) 1/ içinx... yukarıdaki tanımı hala bazı için de geçerli olduğu açıktırf.

Tahmin asimptotik amacı, çalıştırma büyüme için, bu daha uygun ... anlamlı algoritması bir giriş büyüdükçe daha hızlı olsun. Tabii, rasgele bir algoritma, örneğin şu: bu karşılamak için inşa edebilirsiniz

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

Açıkça, bu işlev için daha az zaman harcıyor olarak giriş boyutu büyüyor ... en azından biraz sınırı, zorunlu tarafından donanım (hassas sayıları, minimum zaman sleep bekleyebilir, zaman süreci değişkenleri vb.): bu sınır daha sonra sabit bir alt sınır olur aslında yukarıdaki fonksiyonuhalaçalışma zamanı vardırÇ(1).

Ama yokaslında gerçek dünya zamanı Giriş boyutu artar (en azından kısmen) düşürebilir nerede algoritmaları. Bu algoritmalar unutmayındeğilsergi zamanı aşağıda davranışÇ(1), rağmen. Hala, ilginç. Örneğin, Horspool çok basit metin arama algoritması. Burada, beklenen zamanı, arama deseni artar (ama Samanlık artan uzunluğu bir kez daha zamanı artacak) uzunluğu olarak azalacaktır.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • CHISTOSITOJAJA

    CHISTOSITOJA

    27 HAZİRAN 2010
  • kourtneyannmakeup

    kourtneyannm

    19 ŞUBAT 2012
  • SketchBookPro

    SketchBookPr

    6 Mayıs 2009