j = n;
while (j>=1) {
i = j;
while (i <= n) { cout<<"Printed"; i*= 2; }
j /= 2;
}
我的目標是找到 T(n)（給出演算法執行次數的函式），其順序預計為 n.log(n) 但我需要確切的函式，該函式至少對于 n=1 到 n=10 資料可以正常作業
我試圖預測函式，最后我以 * T(n) = floor((n-1) log(n)) n 結束
這僅適用于 n=1 和 n=2。
我應該提到，通過將原始代碼轉換為 for 回圈，我發現了不準確的函式，如下所示：
for ( j = 1 ; j <= n ; j*= 2) {
for ( i = j ; i<= n ; i*=2 ) {
cout << "Printed";
}
}
最后，感謝您幫助提前找到確切的 T(n)。??
uj5u.com熱心網友回復：
usinglog(x)是基于 log 的 2 的地板
1.) 內回圈執行1 log(N)-log(j)外回圈執行次數1 log(N)j=1,2,4...N 次，整體復雜度為T(N)=log(N)log(N) 2*log(N) 1-(log(1) log(2) log(4)... log(N))= log(N)^2-(0 1 2 ... log(N)) 2*log(N) 1= log(N)^2-log(N)(log(N)-1)/2 1= log(N)^2/2 3*log(N)/2 1
2.) 相同，只是順序相反。
我知道這不是證據，但也許比數學更容易理解：godbolt玩 n。它總是回傳 0；
uj5u.com熱心網友回復：
外回圈和內回圈都是 O(log? N).
所以總時間是
O(log?? N * log? N) == O(2 * log? N)
這只是減少到 O(lg N)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/325440.html