Re: [問題] 程式執行複雜度
看板Prob_Solve (計算數學 Problem Solving)作者suhorng ( )時間13年前 (2011/10/01 21:47)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/3 (看更多)
第三題我看錯題目很嚴重 不好意思
我不會寫算式 所以只是寫個大概想法...(請大家指教)
※ 引述《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
推
10/01 22:03, , 1F
10/01 22:03, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
