如果我有未分類的數字陣列和一些我在尋找，我相信沒有檢查的方式，如果我的電話號碼是它除了通過每個成員會的算法複雜性並進行比較。檢查是否在數組中存在的元素
現在，在數學和各種理論分支我一直感興趣的，有常，你通常得到你放什麼圖案。我的意思是，通常有每一個意想不到的結果的解釋。以蒙蒂霍爾問題爲例。直到你意識到主機增加了更多的信息，因爲他知道汽車後面是什麼門，這似乎是反直覺的。
既然你迭代，而不是剛開是或否的答案陣列上，你也可以得到元素的確切位置（如果它的存在）。那麼不是說有一個算法不那麼複雜，而只給你一點信息？
我完全脫離基地嗎？
有信息你得到的量和算法的複雜性之間的實際關係？從算法獲得的信息量與其複雜性之間的關係背後的理論是什麼？
當你正在尋找一個數組，索引是一分錢一分貨具有陣列的價格。通過索引訪問元素的能力是數組結構中固有的：換句話說，一旦你說「我要搜索數組」（不是集合，但特別是數組），你已經爲索引支付了費用。在這一點上，沒有辦法擺脫它，並且與搜索數組相關的成本。
但是，這不是唯一的解決方案：如果您同意放棄索引作爲需求的能力，您可以構建一個集合，以更快的速度爲您提供yes/no的答案。例如，如果您使用散列表，則搜索時間將變爲O(1)。當然，哈希表中沒有關聯的索引：無法以任意順序訪問項目是您支付能夠在一段時間內檢查是否存在項目的能力。
對！這完全滑了我的腦海。數據結構的選擇限制了我對複雜性的「細粒度控制」的數量。 – 2014-09-06 19:10:30
是的，你完全大錯特錯，對不起！
算法複雜度是根據解決大小爲N的問題需要多少操作來定義的。如果數組中有N個元素，則無法確定該值是否出現在數組中，而不是檢查所有N個元素。這使得它是線性的，或者O（N）。
事實上，你可以也確定值的位置在O（N）（事實上你可以）並不意味着你可以在更短的時間內解決更簡單的問題。
這太糟糕了。我希望在理論上會有更多。我猜棧溢出不是真正的討論和開放式問題的地方。謝謝你的回答。 – 2014-09-06 19:04:37
@LukaHorvat最後一段涉及到底層理論。問題出現在*硬度的陰影*中：必須花費多少資源來解決問題的實例？這不是一個嚴格的順序：即使一個（如果在任何地方，這個數組中的這個值是什麼），許多問題都是相同的，而且這個問題比另一個更普遍（這個值是否出現在這個數組中？）。這些問題中的每一個都可以被證明具有一些特定的複雜性，而且這兩個問題的證明幾乎完全相同。看到有這樣的證據，你的問題並不是真正的開放性的。 – delnan 2014-09-06 19:11:07
什麼是單點信息？ – thumbmunkeys 2014-09-06 18:59:15
對不起，我不明白這裏有什麼問題。 – gd1 2014-09-06 18:59:24
@thumbmunkeys問題的答案是「這個數組是否在這個數組中？」 – 2014-09-06 19:00:34