Questions sur time-complexity

30
réponses

Quelle est l'explication en anglais de la notation" Big O"?

je préférerais une définition aussi peu formelle que possible et des mathématiques simples.
demandé sur 2009-01-28 14:10:32
9
réponses

Comment trouver le temps complexité d'un algorithme

La Question Comment trouver la complexité temporelle d'un algorithme? Qu'ai-je fait avant de ... la complexité temporelle d'un algorithme? Je suis sûr qu'il y a plein de débutants comme moi qui veulent le savoir.
demandé sur 2012-06-14 15:21:15
9
réponses

Quelle est la différence entre Θ(n) et O(n)?

Parfois je vois Θ (n) avec l'étrange Θ symbole avec quelque chose au milieu de lui, et parfois juste O(n). Est-ce just ... graphie parce que personne ne sait comment taper ce symbole, ou est-ce que cela signifie quelque chose de différent?
demandé sur 2009-01-23 01:58:39
11
réponses

Complexité computationnelle de la séquence de Fibonacci

je comprends la notation Big-O, mais je ne sais pas comment la calculer pour de nombreuses fonctions. En particulier, ... - 2); } Quelle est la complexité computationnelle de la séquence de Fibonacci et comment est-elle calculée?
demandé sur 2008-12-11 23:20:25
22
réponses

Y a-t-il des cas où vous préféreriez un algorithme de grande complexité temporelle plus élevé que le plus bas?

y a-t-il des cas où vous préféreriez O(log n) complexité temporelle à O(1) complexité temporelle? Ou O(n) à O(log n) ? avez-vous des exemples?
demandé sur 2015-12-09 16:25:45
15
réponses

Java est hashmap vraiment O(1)?

j'ai vu des affirmations intéressantes sur les hashmaps de Java et leur temps de recherche O(1) . Quelqu'un peut m'expl ... n) plutôt que O(1) . peut-on expliquer si sont O (1) et, dans l'affirmative, comment y parvenir?
demandé sur 2009-06-28 20:49:25
19
réponses

Bénéfice maximal par vente

supposons qu'on nous donne un tableau de n entiers représentant les cours des actions sur un seul jour. Nous vo ... lleur de toutes. Cependant, y a-t-il un meilleur algorithme, peut-être un algorithme qui tourne en O(n) time?
demandé sur 2011-08-17 03:45:55
6
réponses

Qu'est-ce qui causerait la complexité O(log n) d'un algorithme?

ma connaissance du big-O est limitée, et quand les Termes logarithmes apparaissent dans l'équation, cela me perturbe e ... t la médiane de la liste (3, 4, 5, 5, 7, 8, 8, 9, 9, 10). [Conseil: utiliser les concepts de recherche binaire]
demandé sur 2012-02-06 00:49:50
9
réponses

Exemples D'algorithmes présentant des complexités O(1), O(N log n) et O(log n)

Quels sont certains algorithmes que nous utilisons quotidiennement qui ont des complexités O(1), O(N log n) et O(log n)?
demandé sur 2009-10-20 09:33:17
4
réponses

Quelle est la complexité temporelle de ma fonction? [dupliquer]

cette question a déjà une réponse ici: comment trouver la complexité temporelle d ... roit? Edit: (pas une copie) je sais ce que Big O est. J'ai demandé la bonne évaluation dans un cas précis.
demandé sur 2016-02-11 00:20:53
2
réponses

Qu'est-ce qui causerait la complexité O(log n) d'un algorithme?

cette question antérieure traite de certains des facteurs qui pourraient faire en sorte qu'un algorithme présent ... une complexité O(log n). Qu'est-ce qui ferait qu'un algorithme présente une complexité temporelle O(log n)?
demandé sur 2013-05-10 02:13:54
2
réponses

Grand O de tableaux JavaScript

Les tableaux en JavaScript sont très faciles à modifier en ajoutant et en supprimant des éléments. Il masque quelque pe ... plupart semblent supposer que l'ajout et la suppression sont des opérations O(1) lorsqu'ils décrivent leur grand O.
demandé sur 2012-07-17 03:59:38
7
réponses

Évaluation paresseuse et complexité du temps

je regardais autour de moi stackoverflow Non-Trivial d'Évaluation différée , qui m'a conduit à Keegan McAllister ... l'évaluation paresseuse joue-t-elle un rôle mystérieux ici? Si oui, quelle est l'explication derrière cela?
demandé sur 2012-08-21 18:56:02
5
réponses

Le pire dans Max-Heapify-Comment obtenir 2n / 3?

En CLRS, troisième Édition, à la page 155, c'est une donnée que dans MAX-HEAPIFY, les sous-arbres des ... t à moitié plein, alors la taille de l'arbre de l'enfant est jusqu'à 2n/3? Comment calculer? Merci
demandé sur 2012-02-01 20:05:53
23
réponses

Le pire, c'est mieux. Est-il un exemple?

Est-il largement utilisé algorithme de complexité temporelle pire que celui d'un autre algorithme connu mais c'est un mieu ... ent un avantage pour les matrices si grandes qu'elles ne peuvent pas être traitées par le matériel moderne (Robinson 2005)."
demandé sur 2009-01-23 04:35:32
7
réponses

Détection si une chaîne a des caractères uniques: comparer ma solution à " Cracking the Coding Interview?"

je travaille sur le livre "Cracking the Coding Interview" et j'ai rencontré des questions ici demandant des réponses, mai ... ent, que fait l'opérateur"|="? Pourquoi est - 'a' soustrait du caractère courant dans la chaîne de la valeur "val"? Je sais "
demandé sur 2013-10-21 04:11:01
17
réponses

Trouver l'élément majoritaire dans array

l'élément majoritaire est l'élément qui représente plus de la moitié de la taille du tableau. Comment trouver ... un tableau dans O(n) ? exemple d'entrée: {2,1,2,3,4,2,1,2,2} résultats escomptés: 2
demandé sur 2010-12-01 17:11:00
1
réponses

Quelle est la Grande o analyse de cet algorithme?

je travaille sur un cours sur les structures de données et je ne sais pas comment procéder avec cette analyse de Big O: ... nera que lorsque j/i n'a pas de reste et la règle de multiplication est inapplicable. Est mon raisonnement correct ici?
demandé sur 2015-03-19 22:00:30
2
réponses

Quelle est la complexité temporelle d'un appel size () sur une liste LinkedList en Java?

Comme le demande le titre, je me demande si la méthode size() dans la classe LinkedList prend amorti O(1) en temps O(n) fois.
demandé sur 2009-05-14 17:57:23
4
réponses

Quelle est la complexité temporelle de HashMap.containsKey () en java?

j'ai besoin de savoir: quelle est la complexité temporelle de HashMap.containsKey () en java?
demandé sur 2012-01-19 12:49:46
4
réponses

Complexité temporelle de l'opérateur delete [] [duplicate]

cette question a déjà une réponse ici: Big-O du C++ déclaration de 'delete [] Q;' ... ce à l'opérateur de faire de même pour types primitifs ( int , etc.) et les types définis par l'utilisateur?
demandé sur 2014-01-12 20:27:15
3
réponses

HashSet recherche complexe?

une opération de recherche ou contains pour simple peut être O(n) dans le pire des cas ? Donc, pour n regarder hashSet sera
demandé sur 2011-07-04 22:25:41
1
réponses

Comprendre le calcul de la complexité temporelle pour L'algorithme de Dijkstra

selon ma compréhension, j'ai calculé la complexité temporelle de L'algorithme de Dijkstra comme notation big-O en utilisan ... es est V * (E*logV)I. e O(VElogV). mais la complexité temporelle pour L'algorithme de Dijkstra est O (ElogV). Pourquoi?
demandé sur 2014-10-24 16:24:19
2
réponses

Pourquoi les listes de différences sont-elles plus efficaces que la concaténation régulière?

je travaille actuellement mon chemin à travers le apprendre vous un Haskell Livre en ligne, et sont venus à un chapi ... termes simples pourquoi l'exemple ci-dessus est si inefficace, et de quelle manière la DiffList résout ce problème?
demandé sur 2012-12-14 17:04:34
6
réponses

Existe-t-il un algorithme de tri des entiers O(n)?

La semaine dernière, je suis tombé sur ce document notez que cela donne un temps de fonctionnement linéaire pour les ... es de graphes telles que les poids de bord entier [3], [...] mais je n'avais accès à aucune des revues scientifiques.
demandé sur 2010-02-28 22:27:31
5
réponses

Complexité temporelle de l'attribution de la mémoire

Quelle est la complexité temporelle de l'allocation dynamique de la mémoire en utilisant new, malloc,etc.? Je sais très ... du que l'allocation de tas est illimitée dans le pire des cas, mais je suis vraiment intéressé par le cas moyen/typique.
demandé sur 2008-11-12 06:27:08
2
réponses

Quelle est l'efficacité/la rapidité de Python? (Le temps de la Complexité sage)

en Python, Quelle est l'efficacité du in mot clé, par exemple: a = [1, 2, 3] if 4 in a: ...
demandé sur 2012-10-16 03:37:46
7
réponses

Comment améliorer la performance de ce code?

grâce à l'aide des gens d'ici, j'ai pu obtenir mon code pour le puzzle des chameaux de Tasmanie. Cependant, il est hor ... s-je faire pour améliorer ce code? (Surtout en termes de performance, mais toute autre suggestion est la bienvenue).
demandé sur 2010-11-28 10:27:43
6
réponses

Quelle est la complexité temporelle de std:: sort () dans la bibliothèque standard C++?

Quelle est la complexité de std::sort() dans la bibliothèque Standard C++? Quelle sorte est appliquée? Y a-t-il une règle pour appliquer un algorithme de tri particulier?
demandé sur 2010-12-19 23:20:44
1
réponses

Javascript ES6 de calcul/de l'heure de la complexité des collections

quelle complexité temporelle (en notation big-O) est fournie par la spécification ES6 pour les Collections à clé (Set, Map ... e seraient pas tenus ou autorisés par la spec, et je serais très intéressé par une explication de pourquoi c'est le cas.
demandé sur 2015-06-27 20:59:11