L'heuristique (du grec heuriskêin, " trouver ") est l'utilisation de règles empiriques :
Les heuristiques sont souvent, à la différence des algorithmes, tirées de l'expérience ou d'analogies, plutôt que d'une analyse scientifique trop complexe car recensant le maximum d'éléments, et donc difficile, voire impossible à mener et exploiter. L'inconvénient c'est qu'une méthode trop simplifiée peut conduire à des biais cognitifs.
L'heuristique peut consister à donner l'idée d'une preuve, c'est un raisonnement 'avec les mains' qui fait appel à l'intuition ou se base sur l'étude de cas favorables ; elle peut être un préalable permettant d'expliquer un raisonnement fondé complexe.
Les heuristiques trouvent cependant leur place dans les algorithmes qui nécessitent l'exploration d'un grand nombre de cas, car elles permettent de réduire leur complexité moyenne en examinant d'abord les cas qui ont le plus de chances de donner la réponse. Le choix d'une telle heuristique suppose de connaître déjà certaines propriétés statistiques sur l'ensemble d'instances du problème que l'on s'apprête à résoudre. Un exemple d'algorithme de ce type est l'Algorithme A*.
Si l'heuristique est bien choisie, la complexité moyenne de l'algorithme sur notre ensemble d'instances probabilisées peut même éventuellement être dans une classe inférieure (par exemple, polynômiale au lieu d'exponentielle) à celle de sa complexité, ou à celle de la complexité moyenne du même algorithme où l'on explorerait les cas dans un ordre inapproprié. Il est aussi parfois possible de prouver que le résultat fourni par l'heuristique ne s'éloigne pas trop de la solution optimale, on parle alors de garantie de performance.