[問題] 程式執行複雜度

[mqazz1 (無法顯示)]

1. for(a=1; a<=n; a++)
       for(b=1; b<=a; b*=2)
          c++;

2. for(a=1; a<=n; a*=2)
       for(b=1; b<=a; b*=2)
          c++;

3. k=0;
   for(i=0; i<n; i++)
       for(j=0; j<i*i; j++)
          for(z=0; z<j; z++)
                k++;

4. k=0;
   for(i=1; i<n; i++)
       for(j=1; j<i*i; j++)
          if(j%i==0)
                for(z=0; z<j; z++)
                    k++;


請問這四題的時間複雜度要怎麼分析?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.26.214
→ firejox:for(j%i==0) = =+
推 chchwy:這是某年的交大考題嗎
1和2是台科的 3和4是交大的
→ suhorng:猜: O(nlogn) O((log n)^2) O(n^2), and k恆等於0 ?
某補習班x逸的答案是 1.O(nlogn)   2.O((logn)^2)   3.O(n^5)   4. O(n^4)
可以請問這些要怎麼解嗎?
→ suhorng:第四個我是把for當成if來猜...
→ firejox:你不覺得"for(j%i == 0)" 這個很奇怪嗎....
我打錯了 已改..
※ 編輯: mqazz1          來自: 61.228.26.214        (10/01 21:49)