第三題我看錯題目很嚴重 不好意思 我不會寫算式 所以只是寫個大概想法...(請大家指教) ※ 引述《mqazz1 (無法顯示)》之銘言： : 1. for(a=1; a<=n; a++) : for(b=1; b<=a; b*=2) : c++; n n Σ[lg k] = Θ(Σlog k) = Θ(n log n) k=1 k=1 最後一步: http://www.brpreiss.com/books/opus4/html/page514.html 最下面的不等式. 上界類似. : 2. for(a=1; a<=n; a*=2) : for(b=1; b<=a; b*=2) : c++; 上界 O( (log n)^2 ) 是容易的: 外層迴圈跑 O(log n) 次 內層迴圈每次也跑不超過 O(log n) 次 下界不會>< : 3. k=0; : for(i=0; i<n; i++) : for(j=0; j<i*i; j++) : for(z=0; z<j; z++) : k++; i^2 先看內兩層: O(Σj) = O(i^4) j=1 n 然後O(Σi^4) = O(n^5) i=1 : 4. k=0; : for(i=1; i<n; i++) : for(j=1; j<i*i; j++) : for(j%i==0) 我把它當成if : for(z=0; z<j; z++) : k++; z那層: i+(2i)+(3i)+(4i)+...+(i-1)i = O(i^3) //因為跑z的時候j是i的倍數 最後 O(Σi^3) = O(n^4) : 請問這四題的時間複雜度要怎麼分析? : 謝謝 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.32.43