大家好: 想請問大家一個問題? 就是執行次數如何用數學方式表示?    K=n; while(K>=2) {  k/=2  x=x-1; } 我知道這一題的答案是log n,但是用數學要如何算出來.    還有另一題我連答案都不知道, i=1;j=n;   while(i

一般用O(x)来表示一个算法的复杂程度.    范例1的复杂度是O(log n).    范例2, 如果你没有写错的话, 是个无限循环, 即死循环, 因为i总是增大的.    复杂度并不是与執行次數直接对应的, 而是表示執行次數随n增大而增大的快慢程度. 如果你知道算法A的复杂度是O(n), 算法B的复杂度是O(n^^2), 那么不用看具体的算法过程, 你就可以判断A比B的效率要高.    算法A: 

  for (i = 0; i < n; i   )
    for (j = 0; j < 100; j   )
      x = x  1;

執行次數: 100n 复杂度: O(n) 算法B:

  for (i = 0; i < n; i   )
    for (j = 0; j < n; j   )
      x = x  1;

執行次數: n^^2 复杂度: O(n^^2) 当n <= 100时, B比A快, 当n > 100时, 比如n=10000, A比B快得多. 大家往往更关心n较大时算法的表现. _________________________ Programming is a passion

引言: 一般用O(x)来表示一个算法的复杂程度. 范例1的复杂度是O(log n). 范例2, 如果你没有写错的话, 是个无限循环, 即死循环, 因为i总是增大的. 复杂度并不是与執行次數直接对应的, 而是表示執行次數随n增大而增大的快慢程度. 如果你知道算法A的复杂度是O(n), 算法B的复杂度是O(n^^2), 那么不用看具体的算法过程, 你就可以判断A比B的效率要高. 算法A:

  for (i = 0; i < n; i   )
    for (j = 0; j < 100; j   )
      x = x  1;

執行次數: 100n 复杂度: O(n) 算法B:

  for (i = 0; i < n; i   )
    for (j = 0; j < n; j   )
      x = x  1;

執行次數: n^^2 复杂度: O(n^^2) 当n <= 100时, B比A快, 当n > 100时, 比如n=10000, A比B快得多. 大家往往更关心n较大时算法的表现. _________________________ Programming is a passion

您好: 謝謝您的指教,但我們老師就是要我們用數學方式算出執行次數. 還有範列二應該不是個無窮迴圏吧,因為i會愈來愈大,而j會愈來愈小,好像是這樣吧. 如果大哥知道這數學方式如何計算,請不吝告知,謝謝.

假设執行次數为N.    范例1: 当第N次进入while循环时, k/=2在前面的循环中被执行了N-1次, k的值为:

   k = n/(2^^(N-1))

由于第N次循环的存在, 表明该值满足while的条件, 即

   n/(2^^(N-1)) >= 2

推演上式可得

   n >= 2 * (2^^(N-1)) = 2^^N       即: N <= log n (条件是 n >= 1)

范例2: 类似范例1, 当第N次进入while循环时, "i =2;"在前面的循环中被执行了N-1次, i的值为: 2(N-1) 1 (1是初始值) "j--;"在前面的循环中被执行了N-1次, j的值为: n-(N-1) (n是初始值) 根据while的条件, 有

   2(N-1) 1 < n-(N-1)
   
   即: N < (n 2)/3 (条件是 n >= 1)

_________________________ Programming is a passion