指數時間複雜度示例（n^n）

我一直無法找到真正計算需要n^n次計算的算法（編程或現實世界）的例子。我已經看到了旅行推銷員問題，但那真的是！略小於n^n。我也看到了電話簿示例here。這個電話簿問題並不是真正的n^n，因爲每個原始電話簿總共需要n個，並且每個原始書籍都有n個副本。現在它取決於n + n^2。機器人然後需要加載每個額外的副本，也是n^2。把所有這些加起來，你就得到了n + 2n^2。由於我們看最大的指數，它只有x^2。指數時間複雜度示例（n^n）

有人能給我舉一個真正需要n^n的例子嗎？

來源

2016-01-06 OverflowingJava

該電話簿的例子有複雜性n * n沒有n^n ...可能你讀錯了。就像我剛剛做的那樣（是的，我讀錯了你的問題）。 –

http://stackoverflow.com/questions/6156224/are-there-any-real-onn-algorithms - >也許你可以從這個鏈接得到一些幫助。 –

用原始算法計算所有'n'值排列的乘積是指數的。 BTW：TSP不是'O（n！）'，而是它的強力算法。還有其他的TSP算法具有其他複雜性。 –

遞歸爲O（n ^ñ）功能，計數到n ^ň

long long pownn(int n, int depth) { 
    if (! depth) return 1; 
    long long ll = 0; 
    int i = n; 
    while (i--) ll += pownn(n, depth-1); 
    return ll; 
}

稱爲long long result = pownn(n, n);

的例子這種算法是像什麼可以在一些比賽裏被發現理論上每個可搜索的位置給出其自身n其他可搜索的位置，其搜索深度設置爲n。實際上，可以優化遊戲（如國際象棋）（minimax/alpha-beta/memoization-like：存儲的數百萬個位置/位置分析...），並且在消除「無用的」中間位置之後，搜索可能會比深度更深入n。因此分析了「僅」幾百萬個職位。

來源

2016-01-06 08:50:11

你能解釋爲什麼一個未經優化的搜索所有可能的國際象棋棋步是n^n？ – OverflowingJava

這是一個理論上的情況，因爲國際象棋在移動完成之後將具有比常數更多或更少的位置。無論如何，假設一個給定的職位有10個潛在的動作，並且這些動作中的每一個給予對手10個潛在的動作等等。第一級給出10個分支，每個分支給出10個分支等等。在深度10處，要分析的位置是10 x 10 x ... x 10（10次），即10^10。用* n *替換10 ... –

這對我來說確實很有意義。謝謝。 – OverflowingJava

指數時間複雜度示例（n^n）

回答

相關問題