Briser la barrière du temps linéaire : l’essor des algorithmes sous-linéaires
Les algorithmes de temps linéaire ont longtemps été considérés comme la norme en matière de résolution de problèmes. Cependant, avec la prévalence des ensembles de données massifs, les algorithmes sous-linéaires gagnent en importance. Ces algorithmes ne lisent qu’une infime fraction des données d’entrée, ce qui semble impossible. S’il existe des algorithmes sous-linéaires déterministes pour certains problèmes, la plupart nécessitent une randomisation et fournissent des solutions approximatives. Des progrès récents ont été réalisés sur divers problèmes, notamment les problèmes classiques d’optimisation et les tests de propriétés. Des techniques telles que le lemme de régularité de Szemerédi et les approximations matricielles de faible rang se révèlent utiles pour concevoir des algorithmes sous-linéaires, mais il reste encore beaucoup à comprendre sur leur portée et leurs limites.