這個問題并不像看起來那樣愚蠢。至少從理論上講，當(dāng)我們采用Big O符號的數(shù)學(xué)定義時，諸如O（1 / n）之類的東西是完全明智的：

現(xiàn)在您可以輕松地將g（x）替換為1 / x …顯然上述定義對于f仍然成立。

為了估計漸近運(yùn)行時的增長，這種方法不太可行……有意義的算法無法隨著輸入的增長而更快。當(dāng)然，您可以構(gòu)造一個任意算法來實現(xiàn)這一目標(biāo)，例如以下算法：

def get_faster(list):

    how_long = (1 / len(list)) * 100000

    sleep(how_long)

顯然，隨著輸入大小的增加，此函數(shù)花費的時間更少……至少要達(dá)到一定的限制（由硬件強(qiáng)制執(zhí)行）（數(shù)字的精度，sleep可以等待的最短時間，處理參數(shù)的時間等）：然后，此限制為恒定下界所以其實上述功能仍然具有運(yùn)行時?（1）。

但是實際上，在現(xiàn)實世界中，當(dāng)輸入大小增加時，運(yùn)行時間會減少（至少部分減少）。注意，這些算法不會在O（1）以下表現(xiàn)出運(yùn)行時行為。仍然，它們很有趣。例如，采用Horspool的非常簡單的文本搜索算法。在這里，預(yù)期的運(yùn)行時間將隨著搜索模式長度的增加而減少（但是，增加干草堆的長度將再次增加運(yùn)行時間）。

是。

恰好有一種運(yùn)行時為O（1 / n）的算法，即“空”算法。

對于O（1 / n）算法，意味著它比由單個指令組成的算法以更少的步長漸近執(zhí)行。如果所有n> n0的執(zhí)行步數(shù)少于一個步驟，則對于所有n，它必須完全不包含任何指令。由于檢查“如果n> n0”花費至少1條指令，因此對于所有n，它必須不包含任何指令。

總結(jié)：唯一的算法為O（1 / n）是空算法，不包含任何指令。

根據(jù)我以前對大O表示法的了解，即使您需要1個步驟（例如檢查變量，執(zhí)行賦值），也就是O（1）。

注意，O（1）與O（6）相同，因為“常數(shù)”無關(guān)緊要。這就是為什么我們說O（n）與O（3n）相同。

因此，即使您只需要1步，也就是O（1）...，并且由于您的程序至少需要1步，因此算法可以執(zhí)行的最小值為O（1）。除非我們不這樣做，否則我認(rèn)為它是O（0）？如果我們什么都不做，那就是O（1），這是它可以經(jīng)過的最小值。

（如果我們選擇不這樣做，那么它可能會成為Zen或Tao問題……在編程領(lǐng)域，O（1）仍然是最小值）。

還是這樣：

程序員：老板，我找到了一種在O（1）時間內(nèi)做到的方法！

老板：沒必要這樣做，我們今天早上破產(chǎn)了。

程序員：哦，那變成O（0）。