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:
Looking at that formula, the complexity is clearly O().
Now let express P' iteratively:
or ....
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