mardi 3 mars 2015

Algorithm to efficiently determine the [n][n] element in a matrix



This is a question regarding a piece of coursework so would rather you didn't fully answer the question but rather give tips to improve the run time complexity of my current algorithm.


I have been given the following information:


A function g(n) is given by g(n) = f(n,n) where f may be defined recursively by


enter image description here


I have implemented this algorithm recursively with the following code:



public static double f(int i, int j)
{

if (i == 0 && j == 0) {
return 0;
}
if (i ==0 || j == 0) {
return 1;
}

return ((f(i-1, j)) + (f(i-1, j-1)) + (f(i, j-1)))/3;
}


This algorithm gives the results I am looking for, but it is extremely inefficient and I am now tasked to improve the run time complexity.


I wrote an algorithm to create an n*n matrix and it then computes every element up to the [n][n] element in which it then returns the [n][n] element, for example f(1,1) would return 0.6 recurring. The [n][n] element is 0.6 recurring because it is the result of (1+0+1)/3.


I have also created a spreadsheet of the result from f(0,0) to f(7,7) which can be seen below:


Results


Now although this is much faster than my recursive algorithm, it has a huge overhead of creating a n*n matrix.


Any suggestions to how I can improve this algorithm will be greatly appreciated!


I can now see that is it possible to make the algorithm O(n) complexity, but is it possible to work out the result without creating a [n][n] 2D array?




Aucun commentaire:

Enregistrer un commentaire