for(i = 1; i < n; i  )
      for(j = 1; j < i; j   )
          if(j % i == 0)
              for(k=0; k < j; k  )
                  sum   ;     

引言: 1. 有個 recursive function C(n,k) = C(n-1,k-1) C(n-1,k), 請問他的終止條件為什麼是 (k=0) 和 (n=k) 時 C(n,k)= 1 2. 如何算出 Big-O notation.

   for(i = 1; i < n; i  )
      for(j = 1; j < i; j   )
          if(j % i == 0)
              for(k=0; k < j; k  )
                  sum   ;     

此題答案為 O(n^3)...為什麼勒..有點搞不懂.. 謝謝回覆.. 發表人 - yakingkuo 於 2004/11/04 00:29:28

yakingkuo你好： 題一： 沒記錯的話，你那>= class="code"> int C(int n,int k) { if (n 也就是這個function會將你要求的C(n,k)一直拆解，拆到n=k or k=0才停止!停止後最後解也求出了! 題二： 不曉得這行有沒有抄錯：

 if(j % i == 0)      如果沒有的話，那這一段
                       for(k=0; k < j; k  )
                           sum   ;    就永遠不會執行到，因為 j%i 永遠不等於0    也就是不管i等於多少，會執行到的程式碼只有這一行： if(j % i == 0)         現在假設 i=n  where n tends to unfinite!    當 i=1 時 上面那一行程式要被執行
     0 次    當 i=2 時 上面那一行程式要被執行
     1 次    當 i=3 時 上面那一行程式要被執行
     2 次       .
   .
   .    當 i=n 時 上面那一行程式要被執行
     n-1 次        所以總共被執行 1 2 3 ... n-1=1/2(n*n-n)    so O(1/2(n*n-n)) ==>  O(n^2)    如果題目沒抄錯，似乎是這樣吧？？    

研究研究! 發表人 -

引言: 1. 有個 recursive function C(n,k) = C(n-1,k-1) C(n-1,k), 請問他的終止條件為什麼是 (k=0) 和 (n=k) 時 C(n,k)= 1 2. 如何算出 Big-O notation.

   for(i = 1; i < n; i  )
      for(j = 1; j < i; j   )
          if(j % i == 0)
              for(k=0; k < j; k  )
                  sum   ;     

此題答案為 O(n^3)...為什麼勒..有點搞不懂.. 謝謝回覆.. 發表人 - yakingkuo 於 2004/11/04 00:29:28

 
  for(j = 1; j < i*i ; j   )