Hands-On High Performance Programming with Qt 5

Optimizing with algorithms

The basic rule for optimizing your algorithm could be stated as, "Don't repeat yourself," or rather, "Don't repeat computations." You can do it in several ways, for example by:

• Omitting work using knowledge about the structure of the problem: For example, divide a task into subtasks and combine the results.

When you are doing that, you are trying to write your own algorithm. As we have already said, we are aiming at linear algorithms. So, if you have a double loop (and thus O(n²) complexity) somewhere, it had better not crop up in the critical path! With big inputs, even an O(n) algorithm can get rather slow, so sometimes logarithmic complexity is the safest one. Recursively dividing up work into smaller chunks ...