所有的蠻力算法都是指數型的嗎？

我所見過的蠻力算法的每個例子都有指數運行時間。所有的蠻力算法都是指數型的嗎？

這是一個嚴格的規則，即全部蠻力算法運行時指數？

2013-12-10 LanneR

不，當然不是。考慮一種線性搜索算法來搜索排序後的數組。你可以做得更好，但是線性搜索可以被認爲是「蠻力」。

參見https://en.wikipedia.org/wiki/Brute-force_search作爲進一步的例子和解釋。從網頁A相關報價：

雖然強力搜索實現起來很簡單，而且總是會找到一個解決方案，如果它存在，它的成本是成正比的候選解決方案的數量 - 這在許多實際問題隨着問題規模的擴大，這種趨勢會迅速增長。

2013-12-10 23:41:31

Greg，謝謝。 Catalin Pol在CS中對「指數」往往是「非多項式」的同義詞做了評論。那麼，說所有的蠻力算法都是非多項式算法仍然是錯誤的？我猜測是因爲你舉了一個線性蠻力算法的例子。但我只想確認... – LanneR

@StellaJ：是的，我的線性搜索反例表明一般的「所有蠻力算法都是非多項式」是錯誤的。 –

沒有。你也可以做得更糟。

例如，使用蠻力尋找最短旅程（旅行推銷員）是Omega（n！），它不是指數型的。

2013-12-11 00:12:51

實際上，術語「指數」在CS中經常用作「非多項式」的同義詞。所以，即使O（n！）比任何O（n^k）都差，你仍然可以在CS書中找到它作爲'指數'算法 –

那麼，是否真的可以說所有的蠻力算法是非多項式的？我猜不是因爲格雷格的回答。但你同意嗎？謝謝！ – LanneR

@Catalin Pol說：「在CS指數中是非多項式的同義詞」。對不起，這是完全錯誤的。存在非多項式的子指數算法（例如，獨特的遊戲！）。沒有值得他們的鹽的計算機科學家會交換這兩者。史黛拉：格雷格的回答很好。 Catalin是錯誤的。 – 2013-12-11 20:32:57

回答