Questions marquées «time-complexity»

Normalement, dans les algorithmes, nous ne nous soucions pas de la comparaison, de l'addition ou de la soustraction de nombres - nous supposons qu'ils sont exécutés dans le temps . Par exemple, nous supposons cela lorsque nous disons que le tri basé sur la comparaison est O ( n log n ) , mais...

Je pense avoir une compréhension raisonnable des complexités telles que , et .Θ ( n ) Θ ( n 2 )O(1)O(1)\mathcal{O}(1)Θ(n)Θ(n)\Theta(n)Θ(n2)Θ(n2)\Theta(n^2) En termes de liste, est une recherche constante, donc il ne fait que prendre la tête de la liste. est l'endroit où je parcourrais toute la...

J'ai rencontré de nombreux algorithmes de tri au cours de mes études secondaires. Cependant, je ne sais jamais lequel est le plus rapide (pour un tableau aléatoire d'entiers). Donc mes questions sont: Quel est l'algorithme de tri le plus rapide actuellement connu? Théoriquement, est-il possible...

Pour trouver la médiane d'un tableau non trié, nous pouvons créer un min-tas en fois pour éléments, puis extraire un par un éléments pour obtenir la médiane. Mais cette approche prendrait temps.n n / 2 O ( n log n )O ( n logn )O(nbûche⁡n)O(n\log n)nnnn / 2n/2n/2O ( n logn )O(nbûche⁡n)O(n \log n)...

Je recherche une structure de données qui stocke un ensemble de chaînes sur un jeu de caractères , capable d'effectuer les opérations suivantes. On note en tant que structure de données stockant l'ensemble des chaînes .D ( S ) SΣΣ\SigmaD (S)D(S)\mathcal{D}(S)SSS Add-Prefix-Seton : étant donné un...

Quelle est la complexité temporelle de la recherche du diamètre d'un graphe ?G=(V,E)G=(V,E)G=(V,E) O(|V|2)O(|V|2){O}(|V|^2) O(|V|2+|V|⋅|E|)O(|V|2+|V|⋅|E|){O}(|V|^2+|V| \cdot |E|) O(|V|2⋅|E|)O(|V|2⋅|E|){O}(|V|^2\cdot |E|) O(|V|⋅|E|2)O(|V|⋅|E|2){O}(|V|\cdot |E|^2) Le diamètre d'un graphe est le...

Existe-t-il une structure de données pour gérer une liste ordonnée qui prend en charge les opérations suivantes en temps amorti ?O ( 1 )O(1)O(1) GetElement (k) : retourne le ème élément de la liste.kkk InsertAfter (x, y) : insérez le nouvel élément y dans la liste immédiatement après x. Supprimer...

Compte tenu de tout problème de calcul, la tâche de trouver des limites inférieures pour un tel calcul est-elle vraiment possible? Je suppose que cela se résume à la façon dont une seule étape de calcul est définie et quel modèle nous utilisons pour la preuve, mais étant donné que, prouvons-nous...

J'apprends le C ++ et j'ai remarqué que le temps d'exécution de la fonction push_back pour les vecteurs est constant "amorti". La documentation note en outre que "Si une réallocation se produit, la réallocation est elle-même jusqu'à linéaire dans toute la taille." Cela ne devrait-il pas signifier...

Le titre pose la question. Nous avons en entrée une liste d'éléments que nous pouvons comparer (déterminer lequel est le plus grand ). Aucun élément ne peut être égal. Points clés: La comparaison n'est pas transitive (pensez aux ciseaux de papier de roche): cela peut être vrai: A> B, B> C,...

Je comprends donc l'idée que le problème de décision est défini comme Existe-t-il un chemin P tel que le coût soit inférieur à C? et vous pouvez facilement vérifier que cela est vrai en vérifiant le chemin que vous recevez. Cependant, que se passe-t-il s'il n'y a pas de chemin qui correspond à ces...

Certains algorithmes complexes ( union-find ) ont la fonction Ackermann inverse presque constante qui apparaît dans la complexité temporelle asymptotique, et sont optimales dans le pire des cas si le terme Ackermann inverse presque constant est ignoré. Existe-t-il des exemples d'algorithmes connus...

Je me demande comment trouver la circonférence d'un graphe non orienté clairsemé. Par clairsemés, je veux dire . Par optimal, j'entends la complexité temporelle la plus faible.| E| =O( | V| )|E|=O(|V|)|E|=O(|V|) J'ai pensé à une modification de l'algorithme de Tarjan pour les graphiques non...

J'ai rencontré les doutes suivants sur la complexité des tours de Hanoi , sur lesquelles j'aimerais avoir vos commentaires. Est-ce en NP? Tentative de réponse: supposons que Peggy (prouveur) résout le problème et le soumette à Victor (vérificateur). Victor peut facilement voir que l'état final de...

bbba c Nab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Je me demande dans quels groupes de complexité (par exemple pour les ordinateurs classiques et quantiques) il s'agit, et quelles approches (c'est-à-dire les algorithmes) sont les meilleures pour accomplir cette tâche. Le lien wikipedia ci-dessus ne...

J'ai lu un peu de littérature récemment et j'ai trouvé des structures de données plutôt intéressantes. J'ai recherché différentes méthodes pour réduire le temps de mise à jour au temps de mise à jour du pire cas [1-7].O ( 1 )O(1)\mathcal{O}(1) Récemment, j'ai commencé à chercher des structures de...

Juste par intérêt, j'ai essayé de résoudre un problème de la catégorie "récente" du projet Euler ( séquence de chiffres ). Mais je suis incapable de penser à un moyen de résoudre le problème efficacement. Le problème est le suivant (dans la séquence de questions d'origine, il y en a deux au début,...

Supposons que nous ayons un graphe orienté et deux noeuds et . Je voudrais savoir s'il existe déjà des algorithmes pour calculer le problème de décision suivant:A BG=(V,E)G=(V,E)G=(V,E)AAABBB Y a-t-il au moins deux trajets entre et de même longueur?BAAABBB Et la complexité? Puis-je le résoudre en...

Parfois, il est facile d'identifier la complexité temporelle d'un algorithme en l'examinant attentivement. Les algorithmes avec deux boucles imbriquées de sont évidemment . Les algorithmes qui explorent toutes les combinaisons possibles de groupes de deux valeurs sont évidemment .N 2 N 2...

Je cherche des exemples de problèmes qui ont une borne inférieure de Ω(|x|2Ω(|x|2\Omega(|x|^2 ) pour l'entrée xxx . Le problème doit avoir les propriétés suivantes: Ω(n2)Ω(n2)\Omega(n^2)Preuve d'exécution Ω ( n 2 ) pour tout algorithme - la première priorité est d'avoir un argument de limite...