开发者

Time Complexity Evaluation?

I have implemented cryptography and Steganography algorithms in a application and would like to make a time complexity evaluation for these algorithms. 开发者_如何学PythonI don't have any idea how these tests should be performed.

Is there any testing framework which I can apply or how to make these tests?


Assuming you're not using recursion, you should look at your loops. It's fairly simple to count by inspection the number of times each loop is iterated based on a certain input. The time complexity is given by multiplication of the number of times nested loops are run. If you have more than one set of nested loops, add them all together and this is the time complexity. As an example:

for (int i=0; i<N; ++i)
{
    // Some constant time operation happens here
    for (int j=0; j<N; ++j)
    {
      // Some constant time operation happens here
    }
    // Some constant time operation happens here
} 

This loop will execute in O(N) + O(N2) = O(N + N2) = O(N2) time since the outer constant time portions of the loop are executed in O(N) time, while the inner portion is performed in O(N)*O(N) = O(N2).

If you're using recursion, things are a bit harder to analyze, but it boils down to the same thing ... counting how many times constant time portions of your code get executed. Recommend you read a book on analysis of algorithms (This one is pretty much the standard on the subject) which will help you understand how best to analyze other algorithms as well.


You are manipulating pixels in a bitmap, pretty hard to come up with an algorithm that isn't going to be O(n^2). You could run timing tests with various sizes of bitmaps, use the Stopwatch class. Bitmap manipulations that are not computationally hard, like this, are fundamentally limited by RAM bus bandwidth. And the size of the cpu cache if you don't address the pixels the smart way (storage order). You'll know you have cache problems when the perf suddenly falls off a cliff as you increase the bitmap size.


You could unit test it. Assuming you have a method with parameters you can time how long it takes with different input sizes n. That way you can work out the time complexity with respect to n. This would be the simplest way. Not sure of any frameworks that could automate this for you.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜