Ceci est un problème de devoirs. Soit A [] un tableau de nombres entiers et de taille de fenêtre K entière. Générer un tableau M de minimums vu dans une fenêtre comme il glisse sur A. J'ai trouvé an article avec une solution pour ce problème, mais ne comprenait pas pourquoi il a O (n) la complexité. Quelqu'un peut-il m'expliquer?Algorithme minimum de fenêtre coulissante
Cela a tendance à attraper les gens. On pourrait penser qu'il faudrait O(N^2) temps puisque vous avez raison d'ajouter prend O(N) fois et vous avez O(N) éléments. Cependant, réaliser que chaque élément ne peut être ajouté qu'une fois et supprimé une fois. Donc, au total, il faut O(N) pour glisser sur l'ensemble du tableau A.
Cela donne un rendement amorti de O(1) chaque fois que vous déplacez la fenêtre coulissante d'un élément. En d'autres termes, le temps moyen nécessaire pour déplacer la fenêtre glissante d'un élément est O(1).
@Andre: ["la balise de devoirs, comme les autres balises" meta ", est maintenant déconseillée."] (Http://meta.stackexchange.com/q/10812) –
Oh, je ne savais pas cette. Vu qu'il a demandé sur http://stackoverflow.com/questions/4114917/sql-query-for-vendors-who-have-item-more-than-once. Peut-être qu'il devrait y avoir une note dans la description du tag? – AndreKR