KSum如何最小運行時間爲O（N^k-1）？

-1

在KSum問題中，例如在3Sum問題中，有一種方法是首先對數組進行排序，然後選擇第一個數字。接下來是爲陣列的其餘部分做2Sum，從而產生O（N^2）的總運行時間。我覺得很難理解。由於我們必須做2Sum大約N-2次，總運行時間仍然應該是O（N^3）。請賜教。KSum如何最小運行時間爲O（N^k-1）？

來源

2017-08-12 J.Tang

那麼，你做2-總和較小的芳射線每次選擇另一個數字並且2-sum被優化，因爲它已經被排序，所以它比O（n）小一些。 – apokryfos

在5總和的問題，根據你的方法你選擇一個數字，然後執行4sum，這將選擇一個數字，並執行3sum，等等 – marvel308

@apokryfos我看到。我對2Sun很困惑，這就是爲什麼。謝謝！ –

假設T（N，K）表示來計算Ksum問題爲排序陣列大小爲n的所需的時間複雜度。基的情況下是

T(n, 1) = n 
T(n, 2) = n

現在每隔ķ我們就必須循環一次通過陣列，並檢查第k-1之和可能從其它元素以便

T(n, 3) = n*T(n, 2) 
T(n, 4) = n*T(n, 3) 
.... 
T(n, k) = n*T(n, k-1)

所以對於k > 2的時間複雜度將是

爲O（n ^（K-1））

來源

2017-08-12 06:20:07 marvel308

謝謝！我知道了。 –

@ J.Tang如果答案已解決您的問題，請將其標記爲已接受。 – meowgoesthedog

KSum如何最小運行時間爲O（N^k-1）？

回答

相關問題