Buzen's algorithm: Difference between revisions

Revision as of 11:32, 2 February 2009

Revision as of 06:18, 3 February 2009

Line 17:

==Derivation==

<math>''G''(''N'') = ''g''(''M'', ''N'')</math>

: <math>

{|

\begin{align}

|-

|<math>=g(m, \sum_{j=0}^n) f_m(& j )= \sum_{n_1 + \cdot\cdot\cdot + n_{m-1}n_m = n-j} \prod_{i=1}^{m-1} f_i( n_i )</math> \\

|<math>g(m, n)</math>

|<math>& = \sum_{j=0}^n \sum_{n_1 + \cdot\cdot\cdot + n_mn_{m-1} = n-j, n_m = j} \prod_{i=1}^m f_i( n_i )</math> \\

|<math>& = \sum_{j=0}^n f_m( j ) \sum_{n_1 + \cdot\cdot\cdot + n_{m-1} = n-j, n_m = j} \prod_{i=1}^{m-1} f_i( n_i )</math> \\

|-

|<math>& = \sum_{j=0}^n f_m( j ) g( m-1, n-j )</math>

|

\end{align}

|<math>= \sum_{j=0}^n \sum_{n_1 + \cdot\cdot\cdot + n_{m-1} = n-j, n_m = j} \prod_{i=1}^m f_i( n_i )</math>

</math>

|-

|

|<math>= \sum_{j=0}^n f_m( j ) \sum_{n_1 + \cdot\cdot\cdot + n_{m-1} = n-j} \prod_{i=1}^{m-1} f_i( n_i )</math>

|-

|

|<math>= \sum_{j=0}^n f_m( j ) g( m-1, n-j )</math>

|}

: <math>g(m, 0) = 1\,</math> to avoid affecting the product.

to avoid affecting the product.

<math>g(1, n) = f_1( n )</math>

: <math>g(1, n) = f_1( n )\,</math>

This recursive relationship allows for the calculation of all <math>''G''(''N'')</math> up to any value of ''N'' in [[Big O notation|order]] <math>O(''MN^''<sup>2)</mathsup>) time.

There is a more efficient algorithm for finding <math>G(N)</math> for some network. If it is assumed that <math>f_{i>1}( n ) = c_iy_i^n</math>, then the recursive relationship can be simplified as follows:

: <math>

{|

\begin{align}

|-

|<math>= f_m( 0 ) g( m-1, n ) +& = \sum_{j=10}^n f_m( j ) g( m-1, n-j )</math> \\

|<math>g(m,n)</math>

|<math>& = f_m( 0 ) g( m-1, n ) + \sum_{j=01}^n f_m( j ) g( m-1, n-j )</math> \\

|<math>& = f_m( 0 ) g( m-1, n ) + y_m \sum_{j=1}^{n-1} f_m( j ) g( m-1, n-1-j)</math> \\

|-

|<math>& = f_m( 0 ) g( m-1, n ) + y_m g( m, n-1 )</math>

|

\end{align}

|<math>= f_m( 0 ) g( m-1, n ) + \sum_{j=1}^n f_m( j ) g( m-1, n-j )</math>

</math>

|-

|

|<math>= f_m( 0 ) g( m-1, n ) + y_m \sum_{j=1}^{n-1} f_m( j ) g( m-1, n-1-j)</math>

|-

|

|<math>= f_m( 0 ) g( m-1, n ) + y_m g( m, n-1 )</math>

|}

This simpler recursive relationship allows for the calculation of all <math>''G''(n''N'')</math> up to any value of ''N'' to be found in order <math>O(''MN'')</math> time.

==Implementation==