I suggest you use Steering Behaviors to simulate these types of behaviour. See this page for an example of evasive behaviour implemented in this way.
The basic idea is you only consider simple properties like the position and velocity vectors of your prey and predators to compute the desired change in these properties in linear time. This results in responsive yet realistic behaviour.
However, this comes at the cost of not taking other factors in consideration, like more high-level goals (the position of power-ups for example) or the position of static obstacles, as you would in pathfinding. These can be taken into account by combining the Steering Behaviors approach with, for example, potential fields (see Using Potential Fields in a Real-time Strategy Game Scenario (Tutorial)) or pathfinding (e.g. Corridor Map Method). In the case of the latter you want to decrease the update frequency (and trust the Steering Behaviors to compensate for any errors that might occur because of this) or do partial replanning, possibly combined with a more hierarchical approach (e.g. Near-Optimal Hierarchical Pathfinding (HPA*).
If you want a more specific answer, improve your question with more details about your problem. For example, consider describing what your game is about and the number of NPCs we're talking about.