所以我想弄清楚以下演算法的運行時間（偽代碼）：
Algorithm(N):
int i = n;
int j;
new Array sum[(n 1) / 2];
while i > 1 do
j = i;
while j < n do
for k = 0; k < n; k = k 2 do
sum[k / 2] = sum[(k / 2) - 1] k;
end
j = j * 2;
end
i = i / 2;
end
return sum
uj5u.com熱心網友回復：
外回圈，可以使?登錄2 ?? ?迭代。
中間的回圈，可以使0次迭代的第一次運行，然后1，然后2，然后3，...直到?登錄2 ?? ?。這是一個三角形數，因此中間回圈的總執行次數等于：
?日志2 ?? ?（?登錄2 ?? ? 1）/ 2
內部回圈將始終為中間回圈的每次迭代進行相同數量的迭代，因為它與 ?? 或 ?? 的值無關：它是 ?? / 2。因此總共將具有以下迭代次數：
?? ?日志2 ?? ?（?登錄2 ?? ? 1）/ 4
關于算術計算，有兩種計算時間復雜度的方法：
在第一種方法中，我們假設所有涉及的算術計算都是在恒定時間內執行的（如加法、減量、除以 2 和乘以 2），因此我們可以得出以下漸近順序：
O（?? ?登錄2 ?? ?（?登錄2 ?? ? 1）/ 4）= O（??log2??）
更純粹的方法不假設算術計算是在恒定時間內執行的，考慮到整數不是存盤在有限的字（如 64 位）中，而是可以是任意長的。這意味著上述算術計算的時間復雜度為 O(log??)。那么我們必須添加該因素，因為這些用于內部回圈的主體：
O(??log3??)
分配應指定使用兩種方法中的哪一種。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350521.html