有隨著n規模增大，所用時間反而減小的演算法么？
無關回答都讓一讓，我來個正經的～
ICML 2008 best paperSVM Optimization: inverse dependence on training set size
講的是訓練集越大，訓練線性SVM所需要的時間越短。
Abstract:
We discuss how the runtime of SVM optimization should decrease as the size of the training data increases. We present theoretical and empirical results demonstrating how a simple sub-gradient descent approach indeed displays such behavior, at least for linear kernels.題主這是在說 Jeff Dean 發明了 O(1/n) 的演算法那個梗么……
感覺大部分答案都在偷換概念抖機靈。。
題主你需要弄明白各種演算法複雜度分析常說到的「 n 」究竟是個什麼東西！ n 默認指的是問題的規模的度量——對於很多問題，往往存在一個特定的 cardinal （數量？基數？）可以很好的反應問題的規模，我們把這個數默認用 n 表示，也就是複雜度里的那些 n 。很多時候，哪個量才是「 n 」是一個過於顯然的問題，我們就直接跳過，默認大家都知道。但是對於題主（以及這個問題下的很多答主），也許你需要思考以下問題中「 n 」是什麼：
1. 隨機輸出 1 ~ x 中的任意整數
2. 隨機從 1 ~ x 中選擇 y 個數統計平均值還有一些不那麼顯然的，最經典的就是動態規劃類。就拿背包問題舉例好了： x 個物品、背包總容量為 y 的 01背包 ，哪個量才是一般意義上的「 n 」？動態規劃解法的時間複雜度是 O(xy) ，是不是一個「多項式複雜度」演算法？——如果是，那01背包不是NP完全？還是說你找到了一個NP完全問題的多項式演算法？——整段話里是不是有什麼問題/坑，把你繞進去了？
然後再看看很多圖論問題，有 card(V) （常用 n 表示）和 card(E) （常用 m 表示）兩個量。根據問題和演算法的性質，有時候需要選擇其一作為規模的量度，或者兩者並用——但是在重邊無意義的問題里， m 可以化歸為n： m = O(n^2) 。
看起來和問題不直接相關。但是，真的要是理解了上面這些，就不會有這個問題了——
1. 如果 n 不是我們常說的問題規模，那這個問題毫無意義，隨便指個什麼量說是「 n 」都行……
2. 如果 n 指的是問題規模，最快的演算法就是和 n 無關，也就是常數複雜度，O(1) 。比 O(1) 還快的演算法……意味著，隨著 n 增大，這個演算法趨向於無需任何計算……再提醒一點，請溫習大O記號的漸進（asymptotically）意義。最後，關於「時間」，的確和「複雜度」是不同的。但由於這題的特定的問法（n規模增大和時間變化的關係）恰恰就是複雜度想要解決的問題（而非n與時間的絕對的關係），討論時不論是「時間」還是「複雜度」結論都差不多。首先，要精確定義此處的"n"和"時間"。n一般來說是指待解決問題的規模，抖機靈的喜歡混淆概念~
現場發明一個
If n &< 10000000 then fib n else n 再發明一個int fuck(int n){for (int i = 0; i &< INT_MAX/ n; ++i)
cout&<&<"fuck off "&<&< endl;}這個總該是O(1/n)了吧並且它是個演算法匈牙利演算法（或者是其多路增廣版）找二分圖最大匹配描述一副二分圖，當圖足夠密後，圖的邊數越多，速度越快。。。
嚴格來說，時間複雜度 定義中的n其實是 輸入數據長度……
比如我只輸入一個十進制整數，那麼這時n嚴格說來應該是「這個數的數字位數」，而非「這個數的值」。（此時這個數值的界是10^n，不是多項式的，所以像 分解質因數 這類演算法，數量級一高就吃不消了）在這種嚴格定義下，O(n)是任何演算法的時間複雜度下界，不能再低了。
補充一下～計算複雜度是從程序初始還沒讀輸入的時候就開始算。如果假定數據早就準備好了，那就可能會有低於線性的情形了（比如二分查找）～此時可能會有很多特殊情形，有時只看單次操作的話倒有可能發生操作範圍較大時反而運算量較少的情形（比如演算法競賽中常出現的 帶區間信息的線段樹），但整個問題的複雜度是不會這樣的～結論：有，但我們需要深入的有意義的討論。
若單純看題主的問題，
「有隨著n規模增大，所用時間反而減小的演算法么？」注意這裡說的是時間，不是運算步數。很簡單就可以構建出一個，比如輸入數據是一個數組，演算法過程首先查看數組長度m，然後命令計算機sleep(m+1/m)。
但是這並沒有什麼卵用，而且這個演算法本身存在邏輯問題：
1、假如我們的計算機是超級計算機，超級到算什麼都是瞬間完成，那麼的確，這個演算法完美做到隨著數據規模增大，所用時間減少。然而其他演算法呢？在超級計算機的條件下，其他所有演算法都是O（0）複雜度，因為算什麼都是瞬間完成。「所用時間」變得沒意義了。
2、假如我們用的是日常計算機，隨著數據規模的增大，當sleep命令要求的sleep時間短於主頻完成一個周期的時間T的時候，sleep的命令要麼被忽略，要麼被轉化為T，所以在這個限度之後，隨著輸入規模的增大，所用時間會成為常數，這個演算法也就不是「隨著n規模增大，所用時間反而減小的演算法」了。
======分割線======
一個演算法可以被看做是如下步驟：輸入信息→處理信息→輸出信息因此在整個信息流過程中，一個演算法實際上是在通過某個方法提取輸入信息中的某些信息。提取的方法不同，從輸入中尋找信息的手段不同，對於這個演算法而言需要檢查的輸入項目也不同，因此，觀察輸入內容的信息量的指標也是不同的。舉例，比如對於一串規模為n的不確定數列，要找到其中最大的數字，演算法複雜度為對於一串長度為n的數串，每一次的「我所觀察的當前數字是否比我已有的數字大」，都是相互獨立事件，結果要麼是「是」，要麼是「否」，所以對於用該方法檢視的這串數串所蘊含的總熵（平均信息量）為n。而我們提煉出的結果，作為這串隨機數串中最大的數字，每一個數字都有這個可能，要麼是「是」，要麼是「不是」，因此從結果看，這串數組的熵（平均信息量）也是n。
======下方施工中======
下面的推倒還需要更加詳細的敘述和證明。我有空慢慢寫，或者有大神的話可以幫我寫。考慮一個圖靈機
解數獨算不算...
列印N到10000000的所有整數
EDIT: （首先，這個問題的回答只能是用來娛樂的吧，呵呵）
如果說 N 一定要是問題規模，不知道如何定義問題規模，下面的問題算 N 是問題規模么：「輸入 N 個 100000000 以內的自然數，輸出 100000000 以內不包含這些自然數的所有數的全排列」
另外，Sleep 1/N 秒的演算法算么？給出N個[0, 99]之間的整數，判斷是否有重複元素
當N &<= 100的時候，需要用hash來做當N &> 100的時候，直接return true沒有
往飛鏢盤上扔坐標取真隨機數。
談演算法，我們談論的是時間複雜度，不是時間，時間複雜度有asymptotic的概念在裡面。。。。。
微信朋友圈，隨著用戶規模n的增大，所用(微信）的時間就越少…
確實有隨著n規模增大，所用時間不增加甚至減少的演算法。
但是和數據有關。
這是一種非著名的排序演算法，睡眠演算法。java版：
public class Sort {public static void main(String[] args){int[] ints = {10,4,5,3,2,8,9,7,6,1,0};Thread[] sortThreads = new Thread[ints.length];for(int i=0;i&
}
}}class SortThread implements Runnable{int num;public SortThread(int num){this.num = num;}public void run() {try {Thread.sleep(num * 10);} catch (InterruptedException e) {e.printStackTrace();}System.out.println(num);}}對於一些問題n越大，計算複雜度越低。比如：收斂的求和數列。n足夠大時可以用他的極限近似；分子動力學模擬。分子數n足夠大時，可以用宏觀方程計算。
推薦閱讀：