第三题我看错题目很严重 不好意思 我不会写算式 所以只是写个大概想法...(请大家指教) ※ 引述《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