There are at least two optimizations you could make.
First of all, you are performing r
multiplications and r
divisions for each value of C(k,r)
you compute for r < k/2
.
You should only need at most one multiplication and one division
per value of C(k,r)
that you compute, because at the time you want to
compute C(k,r)
you have already computed and stored the value of C(k, r-1)
.
Use the fact that C(k,r) == C(k, r-1) * (k-r+1) / r
:
$$\begin{align*}
\frac{C(k, r)}{C(k, r - 1)} &= \frac{\frac{k!}{r! (k-r)!}}{\frac{k!}{(r-1)!(k-r+1)!}} = \frac{(r - 1)! (k - r + 1)!}{r! (k - r)!} = \frac{k - r + 1}{r} \\
\\
C(k, r) &= \frac{k - r + 1}{r} C(k, r - 1)
\end{align*}$$
This reduces the number of arithmetic operations required from O(k2) to O(k),
which I think is a pretty good optimization.
The second optimization is due to the fact that C(k, r) == C(k, k - r)
.
You used this formula to reduce the number of operations required to compute
C(k,r)
for r > k/2
, but in fact you shouldn't have to perform any operations
for any of those entries in Pascal's triangle, because you have already
computed and stored the answer. Just copy those results to fill the rest of the vector.
(But of course don't copy C(k, k/2)
when n is even.)
The second optimization reduces the number of operations by nearly half.
A consequence of applying these optimizations is that it no longer makes sense
to implement a function like C(int n, int r)
. But implementation of
that function was not part of your requirements as far as I can see.
O(2k) => O(k)
. Writing the algorithm only using two rows is trivial as you use one for the current row and one for the next row you can then iterate towards the solution. \$\endgroup\$for
loop. \$\endgroup\$