最壞的情況會是什麼時間複雜度？

for(int i = 1 ; i < n ; i* = 2) 
for(int j = 1 ; j < i ; j* = 2)

任何人都可以解釋我嗎？我認爲它是log(n)*log(i)。那是否正確？最壞的情況會是什麼時間複雜度？

2012-10-02 sanjay

這些循環是嵌套的嗎？ –

我認爲nlog（i）;因爲我們看到它運行1到n次，所以它會是n，因爲它取決於n，不確定，但可能會記錄（i）;所以它會是n * log（i）;讓我知道你說什麼。 – Mudasar

@Mudasar雖然從1運行到n，但總是增加2倍，所以我認爲它不能是n * log（i）。 –

假設

for (i = 1; i < n; i *= 2) 
    for (j = 1; j < i; j *= 2) 
     ...stuff...

「東西」將運行1 + 2 + 3 + ... +的log（n）-1次。由於整數1到N之和是N *（N + 1）/ 2，所以最壞情況下的運行時間是O（log（n）^ 2）。

2012-10-02 04:42:00

我同意推理。我也憑經驗對其進行了檢查，並且它成立。 –

回答