考慮到時間複雜性，如何計算給定n的運行時間？

我給了一個算法，並估計時間複雜度T（n）爲3 * n！ 2. +考慮到時間複雜性，如何計算給定n的運行時間？

我知道該算法所需的時間來運行，當n = 10是1秒，並且我希望計算的運行時間對於n = 20

我在有些迷惑如何解決這個問題。我假設從n = 10開始，我就把它插入到T（n）中，它給出3 *（10！）+ 2，這顯然不是1（秒）。

任何人都可以提供一些關於如何正確處理這個問題的提示嗎？謝謝！

來源

2015-05-28 chisquared

'（3 * 10！+2）/ k = 1'。 '（3 * 20！+2）/ k = x'。解決'x'。然後意識到這只是一個估計，唯一可以確定的方法就是衡量。 –

@MarkRansom感謝您的回覆。我假設我應該在第一個方程中求解k，然後將其插入到方程2中並解出x？ – chisquared

如果時間複雜度爲O（3 * n！），那麼對於n = 20，需要幾年時間才能完成。 –

由於@MarkRansom在評論中寫道，你將不得不解方程

Runtime(m)/T(m) = Runtime(n)/T(n)

爲Runtime(m)。在這種特殊情況下，結果就是那個大（見@ shapiro.yaacov的評論），如果這個值是正確的，那麼它沒關係。

比方說，你的複雜性是T(n) = 2n²你衡量n = 1000到

Runtime(2000) = T(2000) ⋅ 1s/T(1000) = 4s

1秒這導致我們但是，這並不意味着，你的算法在準確4秒運行。如果你的輸入比特定類型的內存更大，它可能會更糟糕。例如。也許n = 1000的輸入適合緩存。如果n = 2000的輸入不存在，它必須存儲在RAM中，所以你的運行時間將會縮短50倍（只需要輸入一個數字，我不知道與L3緩存相比RAM的速度更慢）。如果你有一個巨大的輸入不適合RAM並且必須存儲在硬盤上，情況會變得更糟。

來源

2015-05-28 17:02:49 AbcAeffchen

考慮到時間複雜性，如何計算給定n的運行時間？

回答

相關問題