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

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

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

def get_faster(list):

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

    sleep(how_long)

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

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

是。

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

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

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

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

注意，O（1）與O（6）相同，因?yàn)椤俺?shù)”無關(guān)緊要。這就是為什么我們說O（n）與O（3n）相同。

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

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

還是這樣：

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

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

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