是否有任何算法不依賴於n（輸入大小）？

我只是好奇，但谷歌無法幫助我這麼做。是否存在不依賴於輸入大小的算法？像，其時間複雜性不會取決於n？是否有任何算法不依賴於n（輸入大小）？

2014-01-24 B_G

查找給定數組的第一個元素的值。 – Matt

是的，不使用任何輸入的算法不取決於輸入的大小。 –

返回前兩個元素中較小的一個。 –

任何常量時間算法（散列，數組查找以及添加到列表前面或從列表前移除都是示例）不取決於輸入的大小。

2014-01-24 20:45:19

我們總是說「恆定的時間」，但如果有人想真正迂腐，他們可以爭辯說，它可能取決於正在使用的數據結構中的位數。在一次操作中只能處理如此多的位，但隨着數據變大，操作更像是位數中的O（n）。超級迂腐，也許不完全正確，我知道。這個問題非常廣泛。 – AndyG

某些算法不會處理整個數據結構，但只能查找內存中的一個位置並對其執行操作。這些都是真正的恆定時間。您的評論不完全正確。 –

我收集我會得到一些flak它:)同意，*一些*算法做到這一點（就像一個算法翻轉1位）。儘管這裏列出的許多「常量」時間算法並不一定如此。 – AndyG

有很多，甚至在實踐的基礎：

假設你需要從數據集中返回的最小元素。你知道你的列表已經排序，所以你返回第一個元素。

2014-01-24 20:44:59

回答