下面這段代碼的漸近運行時間是多少？

下面這段代碼的漸近運行時間是多少？下面這段代碼的漸近運行時間是多少？

if (N % 2 == 0) // N is even 
for (int i = 0; i < N; i = i+1) 
    for (int j = 0; j < N; j = j+1) 
     A[i] = j; 
else // N is odd 
for (int i = 0; i < N; i = i+1) 
    A[i] = i;

如果N是偶數，我們看到的運行時間爲O（n^2），N爲奇數時的運行時間爲O（n）。但我無法確定漸近的運行時間。

可能的答案是：

〜O（N）
〜爲O（n^2）
〜O（N * SQRT（N））
〜爲O（n日誌n）

來源

2016-04-20 TheFermat

**提示：**大O是一個上限。 – interjay

對於什麼是值得的，如果問題沒有指定一個嚴格的界限，你總是可以選擇最大的答案，它在技術上對於大O來說是正確的。 – kevmo314

沒有一個簡單的函數可以用來漸近地嚴格限制運行時。如您所述，運行時在每一步都會在線性和二次方之間振盪。你可以說運行時間是O（n ）和Ω（n），但是沒有定義分段函數，你不能在這裏給出一個Θ的界限。

來源

2016-04-20 16:22:26 templatetypedef

Bump ............ – TheFermat

對不起，你想要碰撞什麼？ – templatetypedef

Theta（n^{3/2 +（（ - 1）^ n）/ 2}） –

下面這段代碼的漸近運行時間是多少？

回答

相關問題