複雜性類

Question

假設方法m1和m2是靜態的無效的，並通過處理Object []類型的參數來計算相同的結果。經驗上我們發現m1→T（N）= 100N和m2→T（N）= 10Nlog2N，其中時間以微秒爲單位。對於什麼尺寸的輸入，最好使用m1和m2？ 所以我會用大數字m1，而我會用小數字m2？只是檢查答案。

Answer 1

您正在尋找N > 0的值，因此100N > 10N log2 N，所以這只是一個代數問題。將雙方除以10N，即得到10 > log2 N，即N < 2**10，即N < 1024。並不難 - ！）

Answer 2

嗯，登錄 N的會打10的時候，N是1024，所以要根據您提供給我們的公式，你會用N <= 1024第二個和第一個爲N >= 1024。 （你在邊界上做什麼並不重要 - 它們將是平等的。）

但是，從實際的角度來看，你應該很可能選擇一個並保持那一個。你是否期望非常大的輸入或許多小輸入？這絕對是你的代碼中的瓶頸？哪一種更簡單的算法？

還有很多事情要決定哪個算法是最好的而不僅僅是給定輸入中哪個算法最快。我寧願保持一個簡單的算法，它運行的速度比一個快速但卻非常複雜的算法慢。

Answer 3

看看這個：http://www.wolframalpha.com/input/?i=plot+100*n+and+plot+10*n*log2(n)

我還沒有想出如何修改，雖然規模。無論如何，以備將來參考。