速度更快的計算機上的複雜性類

Question

如果算法具有複雜度類O（LogN）並且在一臺舊機器上在1秒內解決了N = 10^6的問題。我怎樣才能在新機器上同時計算N個可解決問題？

我想也許我可以計算常數，這將是1/log10^6然後用這個去休息，但我不認爲這是正確的。任何人都可以指導我解決這個問題的步驟？

謝謝

Answer 1

讓我們假設 「日誌」 是指日誌基地2。在這種情況下，「LogN」是20.這意味着舊機器能夠在1秒內完成20次操作。

新機器可以執行兩倍的操作，因此在1秒內完成40個操作。這意味着N = 2^40是新機器可以在1秒內處理的值N。

Answer 2

舊機器：在時間T，我們有O（log N）cpu週期。

新機器爲2x速度更快，所以我們必須在同一時間T.

O（2個log N）= 0 0（2 log n）的CPU週期（日誌N^2）

所以我們可以同時有效處理N^2個數據。