vendredi 19 avril 2013

An interview question

I had an job interview, and the interviewer had a cool technical and language agnostic question.... He just put the focus on algorithms and their complexity.

The problem was: What is the original complexity of the following function, how to optimize it and what is the resulting complexity.

The function was a common box filter where each output pixel is the sum of the each input pixel around him in a KxK area. And just add some 'noise' in the reflexion he said that the 2-dimensional image was a WxH plane.

So let use some math notation to express that:

P '( x , y ) = i = k 2 k 2 j = k 2 k 2 P ( x + i , y + j )

Looking at that formula, the complexity is clearly O( k 2 ).

Now let express P' iteratively:
P '( x + 1 , y ) = i = k 2 k 2 j = k 2 k 2 P ( x + i , y + j ) + j = k 2 k 2 P ( x + 1 + k 2 , y + j ) j = k 2 k 2 P ( x k 2 , y + j )   
or ....
P '( x + 1 , y )   =   P '( x , y ) + j = k 2 k 2 P ( x + 1 + k 2 , y + j ) j = k 2 k 2 P ( x k 2 , y + j )   

So now the complexity is O(2k)! and if you use a k-vector store the sum of each column, and use that sliding window process, a correct implementation will be in O(k+1)




Aucun commentaire :

Enregistrer un commentaire