J'espère que quelqu'un connaît une référence à cela, donc je n'ai pas à lire la littérature ... Considérons une séquence de nombres . Considérez la séquence comme intervalles . De toute évidence, la séquence d'origine est bitonique si un point quelconque de la ligne réelle est poignardé à 2...
Dans la récente préimpression https://arxiv.org/abs/1801.00776 , il est affirmé que nombres réels peuvent être triés dans le temps et l'espace linéaire. L'article semble raisonnable, même si je ne suis pas un expert en algorithmes de tri.nnnO(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Si elle est...
C'est une question intéressante que j'ai trouvée sur le Web. Étant donné un tableau contenant n nombres (sans aucune information à leur sujet), nous devrions pré-traiter le tableau en temps linéaire afin de pouvoir retourner les k plus petits éléments en temps O (k), quand on nous donne un nombre 1...
Il est bien connu que le tri des permutations par transposition est dans , car le nombre minimum de transpositions nécessaires pour trier est exactement . Cette notion de "nombre d'inversion" trouve également des applications en combinatoire algébrique, par exemple elle permet de doter d'une...
Nous connaissons donc tous la borne inférieure de l'arbre de de ⌈ log 2 n ! ⌉ sur le nombre le plus défavorable de comparaisons effectuées par un algorithme de tri comparatif (déterministe). Elle ne s'applique pas au tri par comparaison aléatoire (si nous mesurons les comparaisons attendues pour...
Cette question est inspirée d'une question existante sur la possibilité de simuler une pile à l'aide de deux files d'attente en temps amorti par opération de pile. La réponse semble inconnue. Voici une question plus spécifique, correspondant au cas particulier dans lequel toutes les opérations PUSH...
Supposons que l'on nous donne un tableau contenant des entiers non négatifs (pas nécessairement distincts).A[1..n]A[1..n]A[1..n] Soit un trié dans l'ordre non croissant. Nous voulons calculer A m = max i ∈ [ n ] B [ i ] + i .BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. La...
Soit soit un graphe acyclique orienté , et soit λ est une fonction de marquage en correspondance chaque sommet v ∈ V à une étiquette λ ( v ) dans un alphabet fini L . Écriture n : = | V | , une sorte topologique de G est une bijection σ de { 1 , … , n } à V (c'est-à-dire un ordre deG = ( V,...
Existe-t-il un algorithme de tri basé sur la comparaison qui utilise une moyenne de lg(n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) comparaisons? L'existence d'un algorithme de comparaison pire des cas lg(n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n)est un problème ouvert, mais le cas moyen suffit pour un...
Nous savons tous que la complexité minimale d'un algorithme de tri basé sur la comparaison est les comparaisons . J'essaie de faire un tri aveugle , c'est-à-dire étant donné un nombre sortie, un circuit (avec des portes booléennes, arithmétiques et de "comparaison") qui trie une liste de...
Veuillez excuser la justesse du titre, j'ai peut-être sacrifié la clarté sur l'autel de la concision. On peut voir que l'insertion d'éléments d'un tableau dans une arborescence de recherche binaire et leur lecture nécessitent (lors de l'insertion) les mêmes comparaisons que l'exécution de Quicksort...
Je suis confus. Je veux prouver que le problème du tri d'une matrice nnn par nnn c'est-à-dire que les lignes et les colonnes sont en ordre croissant est Ω(n2logn)Ω(n2logn)\Omega(n^2\log n) . Je continue en supposant que cela peut être fait plus rapidement que n2Journalnn2lognn^2\log n et j'essaie...