On définit un algorithme d'apprentissage en précisant sa procédure d'entraînement et
de prédiction pour une nouvelle entrée de test. Étant donné que la procédure
d'entraînement de l'algorithme k-PPV consiste simplement à mettre en mémoire
l'ensemble d'entraînement , voici donc la procédure
de prédiction:
Lorsque est une liste non triée, la procédure de prédiction s'exécute en temps
.
Il est cependant possible d'obtenir un temps d'exécution dans
, en utilisant
une queue de priorité (monceau).