分析函數運行時複雜度

我已經寫了一個函數append()在Java中，我需要通過O（N）和Θ（N）來分析它的運行時複雜度。分析函數運行時複雜度

這是原題：

假設append()的運行時間複雜度爲t = O(N)，這意味着t也可以通過t = C*N表示。（因爲C是一個常數）

因此(t/N) = C。

如果，例如，t = O(N^2)，然後(t/N^2) = C等等。

使用此方法找到append()運行時coplexity。

於是我就append() N次3個不同N S：1,000，5,000，10,000。

long start = System.currentTimeMillis(); 
for(i = 0; i < N; ++i) { 
    append(); 
} 
long end = long start = System.currentTimeMillis(); 

System.out.println(end - start);

和我寫下end-start這是以毫秒爲單位的運行時間。

現在，我怎樣才能使用這個信息，以獲得append()時間coplexity？

在此先感謝！

來源

2013-11-01 Billie

你已經有了時間複雜性，這是O（N）的事情。你問的是不變的，這是一個模糊的計算複雜性**最好的** - 你爲什麼這樣做？如果您想比較真實世界的性能，可以跳過該部分並直接比較測量的時間。這就是所謂的基準。 – delnan

您誤解了方法。 N被認爲是該字符串的長度，而不是函數調用的次數應該

String str(n); // Or whatever how you create a string with n elements 

long start = System.currentTimeMillis(); 
append(); 
long end = long start = System.currentTimeMillis(); 

System.out.println(end - start);

然後你跑了好NS，並試圖找出它是時間coplexity。嘗試劃分t/N，然後t/N^2，直到你找到一個恆定的答案。

來源

2013-11-01 10:44:03 LeeNeverGup

只有一個數據點，您無法確定函數的時間複雜度。以經驗方式確定時間複雜度的一個好方法是對多個不同大小的輸入進行操作，並查看操作運行時的相對增長率。例如，如果隨着輸入大小加倍，運行時大致加倍，則時間複雜度爲O（n）。如果隨着輸入大小加倍，運行時間大約增加四倍，則時間複雜度爲O（n ）。

Tje您需要幾個數據點的原因類似於爲什麼您需要幾個點來確定一條線。只給出一點，你不能說出斜率或截距是什麼。在衡量時間兼容性時，您不能篩選競爭項和增長項的相對貢獻。

希望這會有所幫助！

來源

2013-11-01 15:39:52 templatetypedef

分析函數運行時複雜度

回答

相關問題