Cette question s'est posée de la discussion dans les commentaires de Cette réponse .
Premièrement, disons qu'il est assez difficile de définir ce qui est hors de commande. Prenant l'exemple de Pavel Shoped a donné, dans la liste [1,5, 10,2,3,4,5,6,7,8,9,9,10,11], nous pouvons "clairement" voir les 5 et 10 (indices 1 et 2) sont hors de l'ordre. Mais un algorithme naïf qui vérifie simplement une sorte de liste de liste de tri invariante ne signalerait pas ceux-ci.
Vérification vérifier Ma question est la suivante: pouvez-vous penser à un algorithme pour résoudre ce problème qui donne la "réponse correcte" (I.e. Indices 1 et 2)? Si tel est le cas, pendant quelle heure et quelle complexité de mémoire fonctionnerait-il? A [I-1] <= A [i] pour tous 0 donnerait l'élément à l'index 3 (qui est 2);
a [j] <= a [i] pour tous 0 <= i <= i <= n et 0 <= j <= i donnerait tous les éléments des indices 3 à 12 ;
3 Réponses :
Probablement la meilleure approche de ce serait de trouver d'abord le Plus longue de la recherche-conséquence puis envisager Tous les éléments ne font pas partie de cette séquence pour être hors de l'ordre. L'algorithme fourni sur la page liée fonctionne dans Une telle approche donnerait définitivement la réponse correcte de votre exemple, car la recherche croissante la plus longue serait la séquence 1 à 11 n'incluant pas les 5 et 10 supplémentaires. O (n log n) heure et utilise O (n) espace (en plus de celui de la liste elle-même).
Cela fonctionne dans mon premier exemple mais regardez celui-ci: [1, 10, 2, 3, 4, 6, 5]. 10 et 6 sont hors de l'ordre, mais 1 et 5 pas ... plus j'y pense, plus ma question semble être un point de théâtre, car je ne peux pas définir tout à fait ce qui est hors de l'ordre, car Botz3000 souligne. .
Oh, attendez! Je n'ai pas vérifié le lien parce que je pensais que je savais que vouloir la plus longue de la recherche préalence! Ensuite, j'ai lu ceci "Cette sous-séquence n'est pas nécessairement contiguë". Maintenant, je pense que cela peut être la solution.
Notez qu'avec [1, 2, 3, 4, 6, 5], ce que signifie «hors de l'ordre» est ambigu - le 6 pourrait être hors de l'ordre, ou les 5 pourraient être considérés en dehors de l'ordre, puisqu'il déplaçant l'un ou l'autre un seul La place à gauche ou à droite mettrait cette partie de la liste "dans l'ordre". En d'autres termes, vous pourriez dire que "le 5 est trop loin" ou "le 6 est à gauche trop loin" et les deux seraient essentiellement équivalents en termes de "degré de désordre".
@DAV, vous êtes correct. Comme indiqué dans la liaison Wikipedia fournie, la recherche croissante la plus longue (appelons-le à court terme) n'est pas unique. Mais le but original de cet algorithme (voir le lien dans la question) pointant l'un d'entre eux suffit.
Il convient de noter que cela peut être fait dans O (n log K) où k est le nombre d'éléments "hors de commande"
Je prends ceci comme la réponse acceptée car il semble de définir (et de résoudre) ma définition floue et "humanisée" de l'ordre de l'ordre supérieur au mieux que possible.
Comment l'algorithme devrait-il savoir quels éléments vous jugez en panne?
si la règle est "la liste [i + 1] doit toujours être la liste [I] + 1", alors il serait facile, bien sûr, il suffit de mémoriser qu'après 1, l'élément suivant devrait être 2, sélectionnez-les dans entre et ainsi de suite. Mais vous avez besoin d'une règle précise pour que l'algorithme puisse déterminer quels éléments doivent être considérés comme «hors de commande».
Comme Dav a dit, La plus longue de la recherche-conséquence croissante est probablement la meilleure que vous puissiez faire.
Ceci est hors top de ma tête, donc il peut (lire probablement pas: p) correct: La limite inférieure évidente de ce problème est O (n) puisque vous devez au moins lire chaque numéro une fois. Mais supposons qu'il y ait un algorithme qui a couru dans O (n) temps. Ensuite, vous pouvez simplement insérer les éléments hors de commande dans l'ordre de l'ordre linéaire, mais le meilleur algorithme de tri de comparaison a une limite inférieure de O (Nlogn), donc c'est une contradiction. (Sinon, il existe des méthodes de tri sans comparaison tels que le godet ou le tri radix qui utilisent beaucoup de mémoire ou exploiter la taille des chiffres en cours de tri ...)
Correct. Le facteur de n est nécessaire pour traiter chaque élément de la liste (une nécessité) et le facteur de journal n est nécessaire pour déterminer où cet élément appartient. Ainsi, tout algorithme qui garantit un résultat trié aura une limite inférieure de O (n log n).
+1 pour prendre cette question intéressante de la question initiale que vous avez indiquée dans une nouvelle question