最壞情況複雜度與輸入大小成反比的算法？

Question

可能重複：
Are there any O(1/n) algorithms?

任何算法的複雜性，其在輸入尺寸的增加而降低？

我在說最壞的情況下的表現。

一般來說，我們知道數值圖的大小隨着輸入大小而減少，但是我們有沒有與這些圖匹配的任何有意義的算法？

Answer 1

這個怎麼樣？

Mystery(array[1..n]) 
1. x := fn(0) 
2. for i = 1 to floor(1,000,000/n) do 
3. x = fn(x) 
4. return x 

由於顯而易見的原因，所有這些算法都是恆定的，漸近地說。

編輯：

其實，這是漸近O（log n）的，如果整數除法是對數，我相信它是。 http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations因此，我的答案是沒有任何O（1/n）算法。 O（1）是最小的複雜度類別，除非有一種方法可以使算法在不計算它的情況下知道其輸入大小的倒數！

EDIT2：

我只是想，也許通過1,000,000/n向功能輸入......但這是不是一個真正的真正的解決方案，因爲該算法就沒有辦法判斷該條件被侵犯，而且調用者無論如何都需要計算它。請注意，如果您將算術運算設爲恆定時間，那麼很多討論並不是特別相關，因爲我非常確定它們是在具有固定大小的內部類型和指令集的計算機上運行在定義的寄存器大小上。

Answer 2

喜歡的東西

f(Collection c, query q): 
    if q in c: 
    do something fast! 
    else: 
    compute Ackermann function! 

f*(Array a, int i): 
    if a[i] == i: //Or some other condition that takes constant time to verify, 
       //assume i is within bounds 
    do something fast! 
    else: 
    compute Ackermann function! 

嗯，當然，這種性能依賴於概率A [1] ==我。我沒有做過任何徹底的分析，但我想，爲了計算這個概率，你需要對數組性質以及f *如何被調用的某種形式的假設。

思考很有趣，但我無法想象我會遇到這種情況。

編輯：原來的答案是f，但改爲f *，以試圖容納哈羅德的評論。在f *之後，我休息我的情況，並且只是潛伏。