Informatique

Une structure de données de pile utilise un accès dernier entré, premier sorti pour offrir des opérations de push et pop en O(1). Remplacer un tableau horizontal par une architecture à double pile réduit la complexité temporelle de O(n²) à O(n), ce qui fait la différence entre un verdict de limite de temps dépassée et un score parfait dans des concours comme le CCC.

Le problème des villages de Voronoi vous demande de trouver la plus petite région de Voronoi sur une droite numérique. Commencez par trier les coordonnées, sautez les deux points extrêmes car ils s’étendent à l’infini, puis appliquez une formule : (voisin de droite − voisin de gauche) ÷ 2. La complexité temporelle globale est O(N log N).