有沒有可能讓大O比O（1）少？

可能重複：
are there any O(1/n) algorithms?有沒有可能讓大O比O（1）少？

有沒有可能對你的代碼是大O小於O（1）？

2009-08-17 Ben Lakey

請參閱：http://stackoverflow.com/questions/905551/ -there-any-o1-n-algorithms – 2009-08-17 06:09:25

當你，尼克，你打敗了我。：P – GManNickG 2009-08-17 06:11:12

O（1）簡單地表示恆定的時間操作。那個時間可能是1納秒或100萬年，這個記號不是絕對時間的量度。除非你正在爲時間機器操作OS，否則你的DoTimeTravel（）函數可能會具有O（-1）的複雜性:-)

2009-08-17 06:13:22

時間旅行的概念很酷:) +1 – xyz 2014-07-10 09:48:48

不是。 O(1)是恆定時間。無論您將其表述爲O(1)或O(2)或O(.5)，就純粹大O符號而言，確實沒有什麼區別。

正如在this question中指出的那樣，在技術上可能有O(1/n)，但是沒有現實世界中有用的算法能夠滿足這個要求（儘管算法的一部分確實具有算法複雜度的一部分）。

2009-08-17 06:09:05

像「DROP TABLE」和「DELETE FROM TABLE」這樣的sql語句顯示O（1/N）beheaviour。 – 2009-08-17 06:21:51

你如何看待？ 'n'是表的數量，而不是表中的記錄數，因爲*表*是輸入，通常所有這些操作都需要刪除對錶的引用。 – 2009-08-17 06:26:29

'DELETE FROM TABLE'可能具有O（1/N）特性，這取決於實現，但我懷疑這是否會出現，除非您試圖刪除超過一半的表。 – 2009-08-17 06:31:50

唯一會花費少於O（1）（恆定時間）的操作是完全沒有任何操作，因此花費了零時間。但即使是NOP通常也需要固定的週期數...

2009-08-17 06:11:28 Peter

固定週期數？讀取指令需要多少個週期，什麼都不做？我不希望NOP花費超過1個週期... – 2009-08-17 06:13:06

當然，這取決於體系結構。 – GManNickG 2009-08-17 06:14:05

所以這將是O（0）？ – Ray 2009-08-17 06:20:10

回答