真的有O(1/n)的演算法嗎？

01-02

好吧我知道了
這應該就只是一個吹Jeef Dean的玩笑（逃）

如果真的有 $O(frac{1}{n})$ 的演算法，這也就意味著，演算法的運行時間可以任意小，只要輸入的規模 $n$ 足夠大。

一個真實的運算過程真的可以任意小么？至少跑一條指令的時間就算再短也總是有限的？

什麼都沒做我不認為是一個有效的演算法。

lim((1/n)/1),n-&>∞=0，所以O(1/n)比O(1)還快么，不可能嘛，即便不考慮物理環境，至少你的演算法也需要至少一個指令的initialization啊

所以問題出在哪呢，你看：O(n^3+n^2+n+1)=O(n^3)，為啥呢，因為「取最高階」，所以，就算你寫出了一個時間看上去是K/n（K為常數）的一個演算法（例如sleep(1000000000/n)，假設這裡n就是輸入規模的話，實際上並不一定是），那算上初始化的時間，整個時間的式子也應該是：C+K/n，C和K是常數

那麼，O(C+K/n)=O(Cn^0+Kn^-1)，取最高階，是0次方，所以最後結果是O(C)=O(1)

所以你看，O(1/n)？不存在的！

================

修改補充：如果你算上讀取輸入，那肯定至少是O(n)，所以一般討論問題不看讀取時間，但initialization省不掉，當然，如果你認為可以把initialization省略掉不考慮，只考慮「實際開始運行」的時間，那好像是可能有極限為0的「演算法」的，不過好像已經不應該稱這個過程為「演算法」了，演算法步驟是離散的

@姬明超的回答提到大O是上界，所以耗時為0的演算法可以認為是O(1/n)，具體嚴謹的例子可以用一個初始狀態就是結束狀態的圖靈機來表示，不過我猜題主問的意思應該是Θ，上面的回答是站在Θ的角度

sleep(10000/n) 這種算嗎？

大O記號只規定了上界，所以從數學角度上來說一個什麼都不做的演算法（即 $f(n) = 0$ )就是一個O(1/n)的演算法。

簡單證明：

令 $c = 1, n_{0} = 1$ , 則對所有 $n geq n_{0}$ 都有 $frac{c}{n} gt 0$ 。因此當 $f(n) = 0$ 時， $0 leq f(n) leq frac{c}{n}$ 成立。

嚴格來說是不存在的

根據定義 T(n)=O(f(n))

T(n)是基礎操作執行的次數至少應該是1

如果複雜度是O(1/n) 只要n足夠大顯然T(n)會小於1

就算真的有類似輸入越大算的越快這種演算法 T(n)=1/n+c c是輸入輸出+初始化之類的常數這樣取最高階後複雜度是O(1)並不是O(1/n)

順便一提某匿名用戶的回答非要說排序複雜度下界是O(nlogn) 還說什麼n很大的時候桶排序複雜度變成O(nlogn)之類奇怪的話.....我提出了錯誤不但不改反而把回答匿名了……

正確的應該是「基於比較的排序複雜度下界是O(nlogn)」而桶排序不是基於比較的排序並且它的平均複雜度是O(n)的

希望不要被他誤導...

時間重置是個什麼概念？

數字12為什麼如此特殊？

C++數組有一個致命缺陷，為什麼一直沒有人發現？

熱力學第二定律破產了嗎？

20攝氏度為什麼不是10攝氏度的兩倍？

。。。。。。

@知乎小管家有沒有什麼方法禁止這些玩意出現在我的時間線上面哎

有啊，你面對問題時解決問題的決心演算法。

這個解決問題的決心是你的大腦經過一套演算法之後得出的；

問題越複雜內容越多（n越大），你評估問題的期望就越小，當問題趨於無窮複雜的時候，你解決問題的決心變為了0。

如果你1是固定的數據總量，n是計算機的數目的話。一個任務分到n個計算機上並行運行，那麼時間複雜度就是O(1/n)。

我只是想說分析複雜度的時候，n不一定都是數據的規模。

我覺得你想問是否有沒有比 O(n) 好的演算法。

O(lgn) 和 O(lglgn) 都是有的

有，有請Jeff Dean

我什麼也不算，這是墜好的

noip2017D1T2所謂的「時間複雜度」

O這個記號就要求漸進非負，參加算導

有啊，騙分演算法

當數據少的時候可以直接輸出騙分。

數據多了直接GG，分都不騙

參考noip2017 D1T2

抄答案大法?

不存在的吧，輸入起碼o1了...

樓上的答案有一點說得非常好， $O(cdot)$ 只確定了上界， $Theta(cdot)$ 才是緊界。

演算法必須有輸出，輸出語句就要 $O(1)$ 的時間，因此時間複雜度為 $O(frac{1}{n})$ 的演算法是不存在的。

如果對這個解答不滿意，還有另一種證明方法。

考慮計算機可能執行的所有指令組成集合 $S$ （包括賦值、比較、判斷、輸出，甚至是申請內存空間，這裡的 $S$ 往往是個有限集合），所需耗費時間 $T:S o Bbb R$ ,根據實際問題顯然 $T$ 有下界0，故其有下確界 $au=inf_{s in S}{T(s)}$ ，只要滿足 $au >0$ ,那麼任意演算法執行所耗費的時間必然至少為 $au$ （否則該演算法什麼都沒做）。

其實到這裡已經可以說明問題了，但是如果一定要補充完整這個證明，可以看看 $O(cdot)$ 的定義。

按照定義，集合 $O(f(n)) = {p(n): exists N in Bbb N, c >0 (forall n > N, 0<P> ，因此 <img src=$ 。

顯然，對於任何一個滿足我們之前假設的時間函數 $p(n)$ ，當 $n > sup frac{c}{p(n)}$ 時（不妨取 $n = frac{c}{ au} + 1$ ）， $p(n) > frac{c}{n}$ ，不能成為集合 $O(frac{1}{n})$ 的元素。

因此不存在時間複雜度為 $O(frac{1}{n})$ 的演算法，至少在承認『任何演算法都需要執行語句（步驟）』以及『任何步驟都需要耗費不少於 $au >0$ 的時間』的前提下，這個結論是成立的。

首先，你讀取這些數據的內容的首地址，就至少是一個O(1)的內容

一個演算法的第一步是O(1), 演算法複雜度不可能比O(1)小

而且很多問題是有複雜度下限的，比如排序。如果你「開天眼」，天生就知道哪個是最小的把最小的放到第一位，其次再排第二個，這樣複雜度也至少是O(n)，當然理論證明其複雜度不可能小於O(n log n).

還有，有限問題不存在複雜度這種東西，複雜度的意思是n很大的時候，計算時間對n的函數。你別搞說，n比較小的時候，用桶排序，說複雜度。當n很大的時候退化成歸併排序還是nlogn.

至於糾結n還是2n的問題，建議回去學高數。

補充:有人質疑桶排序。桶排序有三步，把每個元素扔進桶，排桶內元素，連接桶。第一步複雜度就是等待排序元素的個數n，第三步就是桶的個數m，第二步我暫時沒算，是m個和為n的整數，f(x)=x ln x的和的期望。等我回去算一下。

看m是一個確定量還是一個和n有關的量。第三步複雜度低第二步複雜度就高，第二步複雜度高第二步複雜度就低，總和不低於nlogn.

如果你開闢m=n個桶，每個桶平均一個元素，但是並不是這樣的。

=======================================

覺得我錯就舉報去吧，可能我們理解的複雜度不是一個概念。把複雜度定義出來吧。

把一個演算法確定了，才談複雜度。扔桶過程是不能對n變大有改變的，不然這裡還會出現影響複雜度的因子。不能n變大了之後，改了另一個扔桶操作。

我的理解是沒必要去找，原因是：

$1/n < N, (N是大於1的常數， n是大於1的整數)$

對於程序來說O(N)已經是很好的情況了，而O(1/n)還優於O(N)。所以我認為沒必要找這樣的演算法了。