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

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

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ı

Ş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.