-1
Mes questions est spécifique au problème posé ici: Interview puzzle: Jump GamePuzzle jeu jump complexité
La réponse supérieure prétend qu'il fonctionne dans O(n) temps. Il dit qu'il peut faire
parce que chaque élément doit être considéré comme une seule fois (éléments qui seraient considérés comme une deuxième fois peut être sautée)
Cependant, juste vérifier si nous avons déjà considéré comme un élément prend un temps constant par élément, donc il devrait prendre O(n^2), non? O(n) pour prendre en compte chaque nouvel élément, et O(n) pour exclure les éléments que nous avons déjà considérés. Pourquoi n'est-ce pas le cas?
Vous n'avez pas besoin de vérifier si vous avez déjà considéré un élément particulier, vous avez juste besoin de garder trace de l'index que vous avez déjà vérifié, et le plus haut v (sauf celui que vous venez de sauter) de la matrice jusqu'à ce point. Ensuite, vous pouvez continuer à vérifier à partir de là, en comparant chaque nouvel élément au max précédent. – azurefrog
@azurefrog vous devriez faire une réponse pour que cette question puisse être résolue: D –