假設您有兩個大小為 的方陣m1和。該演算法迭代地對它們運行一個操作，同時在每次迭代時將矩陣減半。類似于下面的偽代碼：m2n X nO(n^2)
while m1.width > 0:
u = m1 & m2 # pairwise logical and operation (O(n^2))
m1 = halve(m1)
m2 = halve(m2)
由于回圈重復log(n)多次，O(n^2.log(n))因此是演算法時間復雜度的上限。我正在尋找更嚴格的上限。有任何想法嗎？
O(n^2)基于估計的矩陣大小呈對數收縮的前提，我預計會有一個更嚴格的上限。
uj5u.com熱心網友回復：
對于這樣的回圈，將每次迭代中完成的作業相加而不是將一次迭代完成的作業乘以迭代次數通常是一個好主意。畢竟，每次迭代所做的作業都在變化。
暫時不考慮 O 符號，您的第一次迭代大致完成 n^2 作業，既計算 AND 又將矩陣大小減半。現在，第二次迭代做了多少作業？好吧，因為你的矩陣在每個維度上都是以前的一半，所以對它們做的作業大約是 (n / 2)^2 = n^2 / 4。當你再次將矩陣減半時，下一個 AND 做 (n / 4)^2 = n^2 / 16 個作業。更一般地，第 k 次你通過回圈，你的 AND 操作將做 n^2 / 4^k 的作業。
在回圈的所有迭代中加起來，我們得出的總作業量是
n^2 / 4^0 n^2 / 4^1 n^2 / 4^2 ...
= n^2 · (1 / 4^0 1/4^1 1/4^2 ...)
后一位是幾何級數的總和，加起來是 4/3。所以這讓我們知道完成的總作業是我的 4n^2 / 3，即 O(n^2)。
另一種理解方式：雖然您的代碼是迭代撰寫的，但您可以將其想象為一個遞回演算法，它執行 O(n^2) 作業，然后在大小為 n / 2 的輸入上再次運行。這給出了遞回
T(n) = T(n / 2) O(n^2)。
然后，主定理告訴您（在 a = 1、b = 2、d = 2 和 log_b a < d 的情況下）解決方案是 O(n^2)。
uj5u.com熱心網友回復：
目前尚不清楚“減半”是什么，但假設它將 n 減半（而不是將矩陣中的元素數量減半），此計算顯示 O(n^2)：n^2 (n/2)^2 (n /4)^2 ... = n^2 * (1 1/4 1/16 ...) = 4n^2/3。
如果它將矩陣中的元素數量減半，那么你就有這個計算（也給出 O(n^2)）：n^2 n^2/2 n^2/4 ... = n^ 2(1 1/2 1/4 1/8 ...) = 2n^2。
在計算減半演算法的復雜性時，這里使用的常用技巧是將總和設為無窮大，而不是在 n/2^k 達到 1 時停止。這恰好給出了一個嚴格的上限。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446429.html
下一篇：如何計算有效分支因子？