Questions sur les méthodes d'estimation de l'augmentation du temps d'exécution d'un algorithme à mesure que la taille d'entrée augmente.
Il y a beaucoup de questions sur la façon d'analyser le temps d' exécution des algorithmes (voir, par exemple, l' exécution d'analyse et d'analyse de l' algorithme ). Beaucoup sont similaires, par exemple ceux qui demandent une analyse des coûts des boucles imbriquées ou des algorithmes de division...
On dit souvent que la recherche de table de hachage fonctionne à temps constant: vous calculez la valeur de hachage, ce qui vous donne un index pour une recherche de tableau. Pourtant, cela ignore les collisions; dans le pire des cas, chaque élément arrive dans le même compartiment et le temps de...
La recherche dans un tableau de éléments à l'aide de la recherche binaire prend, dans le pire des cas, le log 2 N itérations car, à chaque étape, nous coupons la moitié de notre espace de recherche. Si, au lieu de cela, nous utilisions la "recherche ternaire", nous réduirions les deux tiers de...
La complexité de l'algorithme est conçue pour être indépendante des détails de niveau inférieur, mais elle est basée sur un modèle impératif, par exemple, l'accès au tableau et la modification d'un nœud dans une arborescence prennent un temps O (1). Ce n'est pas le cas dans les langages...
Je suis novice dans la compréhension des algorithmes informatiques. Je comprends le processus de recherche binaire, mais j'ai un léger malentendu avec son efficacité. Dans une taille de éléments, il faudrait en moyenne étapes pour trouver un élément particulier. En prenant le logarithme en base 2...
Je ne suis même pas un étudiant CS, donc cela pourrait être une question stupide, mais veuillez me supporter ... À l'ère pré-informatique, nous ne pouvons implémenter une structure de données de tableau qu'avec quelque chose comme un tableau de tiroirs. Puisqu'il faut localiser le tiroir avec...
Il est écrit sur Wikipedia que "... le tri par sélection surpasse presque toujours le tri par bulles et le tri par gnomes." Quelqu'un peut-il m'expliquer pourquoi le tri par sélection est considéré plus rapide que le tri par bulles, même si les deux ont: Pire complexité du temps : O (...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
Avant de lire L'Art de la programmation informatique (TAOCP) , je n'ai pas approfondi ces questions. J'utiliserais un pseudo-code pour décrire des algorithmes, les comprendre et estimer le temps d'exécution uniquement sur les ordres de croissance. Le TAOCP change complètement d'avis. TAOCP utilise...
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 remarque que dans quelques articles de recherche CS, pour comparer l'efficacité de deux algorithmes, le nombre total de comparaison clé dans les algorithmes est utilisé plutôt que les temps de calcul réels eux-mêmes. Pourquoi ne pouvons-nous pas comparer lequel est le meilleur en exécutant les...
J'ai le code Python suivant. def collatz(n): if n <= 1: return True elif (n%2==0): return collatz(n/2) else: return collatz(3*n+1) Quel est le temps d'exécution de cet algorithme? Essayer: Si désigne le temps d'exécution de la fonction . Alors je pense que j'ai { T ( n ) = 1 pour n ≤ 1 T ( n )...
Des réponses à (Quand) la recherche de table de hachage O (1)? , Je suppose que les tables de hachage ont un comportement pire des cas, au moins amorti, lorsque les données remplissent certaines conditions statistiques, et il existe des techniques pour aider à élargir ces conditions.O(1)O(1)O(1)...
Le tri rapide aléatoire est une extension du tri rapide dans lequel l'élément pivot est choisi au hasard. Quelle peut être la pire complexité temporelle de cet algorithme. Selon moi, ce devrait être , car le pire des cas se produit lorsque le pivot choisi au hasard est sélectionné dans l' ordre...
L'algorithme de minimisation DFA de Brzozowski crée un DFA minimal pour DFA en:GGG inverser tous les bords de , faisant de l'état initial un état accepté, et des états acceptés initiaux, pour obtenir un NFA pour le langage inverse,GGGN′N′N' en utilisant la construction du jeu de puissance pour...
Dans le livre "Computational Geometry: Algorithms and Applications" de Mark de Berg et al., Il existe un algorithme de force brute très simple pour calculer les triangulations de Delaunay. L'algorithme utilise la notion d' arêtes illégales - des arêtes qui peuvent ne pas apparaître dans une...
J'ai lu ce livre pour ma classe, Randomized Algorithms. Dans ce livre en particulier, il existe une section entière dédiée à la recherche de la médiane d'un tableau à l'aide de la sélection aléatoire, ce qui conduit à un algorithme plus efficace. Maintenant, je voulais savoir s'il existe des...
La page wikipedia sur les algorithmes de multiplication en mentionne une intéressante par Donald Knuth . Fondamentalement, cela implique de combiner la multiplication par transformée de Fourier avec une table précalculée de multiplications de taille logarithmique. Il fonctionne en temps linéaire....
Je suis toujours un peu confus avec les termes "longueur d'entrée" et "taille d'entrée" lorsqu'ils sont utilisés pour analyser et décrire la limite supérieure asymptomatique d'un algorithme Il semble que la longueur d'entrée de l'algorithme dépende en grande partie du type de données et de...
J'ai un algorithme récursif avec une complexité temporelle équivalente à choisir k éléments parmi n avec répétition, et je me demandais si je pouvais obtenir une expression big-O plus simplifiée. Dans mon cas, peut être supérieur à et croît indépendamment.kkknnn Plus précisément, je m'attendrais à...