Questions sur complexity-theory

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
10
réponses

Quelles sont les différences entre NP, NP-Complete et NP-Hard?

Quelles sont les différences entre NP , NP-Complet et NP-Dur ? je suis au courant de beauco ... a raison est qu'elles peuvent être différentes de ce qu'il y a dehors, ou c'est dehors et je ne suis pas au courant.
demandé sur 2009-12-07 04:11:36
22
réponses

Big O, comment calculez-vous/approximatif?

la plupart des diplômés en sciences savent certainement ce que Big O signifie . Il nous aide à mesurer comment (dans) ... ématurée est la racine de tout mal , et l'optimisation sans cause justifiée devrait mériter ce nom aussi bien.
demandé sur 2008-08-06 14:18:16
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
5
réponses

Temps Amorti Constant

Qu'entend-on par" temps amorti Constant " lorsqu'on parle de la complexité temporelle d'un algorithme?
demandé sur 2008-10-14 12:32:47
30
réponses

Y a-t-il des algorithmes O(1/n)?

y a-t-il des algorithmes O(1/n)? Ou n'importe quoi d'autre qui est à moins de O(1)?
demandé sur 2009-05-25 10:15:28
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
6
réponses

C'est quoi "P=NP"?"et pourquoi est-ce une célèbre question? [fermé]

La question de savoir si P=NP est peut-être le plus célèbre dans l'ensemble de l'Informatique. Ça veut dire quoi? Et p ... H, et pour un crédit supplémentaire, veuillez poster une preuve de la vérité ou de la fausseté de la déclaration. :)
demandé sur 2008-09-21 20:07:07
5
réponses

Quelles garanties y a-t-il sur la complexité à court terme (Big-O) des méthodes LINQ?

j'ai récemment commencé à utiliser LINQ un peu, et je n'ai pas vraiment vu aucune mention de la complexité du temps d' ... r le fournisseur D'objets aussi? Si oui, est-ce différent si vous utilisez la syntaxe déclarative ou fonctionnelle?
demandé sur 2010-05-10 02:29:05
24
réponses

Un Regex qui ne sera jamais égalé par quoi que ce soit

Cela peut sembler une question stupide, mais j'ai eu une longue conversation avec certains de mes collègues développeu ... e que soit la chaîne que je lui donne. ainsi, vous avez là ma raison pour cette "Pas une vraie question"...
demandé sur 2009-11-12 18:46:20
8
réponses

Big-oh vs big-theta [dupliquer]

possibilité de dupliquer: Quelle est la différence entre Θ(n) et O(n)? il me ... précié)? Bonus: pourquoi les gens apparemment toujours utiliser big-oh quand parler de manière informelle?
demandé sur 2010-07-12 20:13:07
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
7
réponses

O (N log N) complexité-semblable à linéaire?

donc je pense que je vais me faire enterrer pour avoir posé une question aussi insignifiante mais je suis un peu confu ... au départ. Est-ce parce que la différence entre log(n) log(n+1) augmente linéairement? Merci, Gav
demandé sur 2009-06-07 22:59:16
7
réponses

Comment comprendre le problème knapsack est NP-complet?

nous savons que le problème knapsack peut être résolu dans la complexité O(nW) par la programmation dynamique. Mais no ... plet. Je pense qu'il est difficile à comprendre ici. (n est le nombre d'éléments. W est le volume maximal.)
demandé sur 2010-10-11 19:17:57
8
réponses

Règles générales pour simplifier les déclarations SQL

je suis à la recherche de quelques" règles d'inférence " (semblables à des règles d'opération ou des règles de logique) ... valentes de déclarations SQL comme le fait que la plupart des sous-sélects peuvent être réécrits comme une jointure.
demandé sur 2009-07-01 18:14:46
7
réponses

Est liste::size() O(n)?

récemment, j'ai remarqué que certaines personnes mentionnaient que std::list::size() a une complexité linéaire. ... oi ressemble actuellement gcc ? Si elle est vraiment en O(n), pourquoi le les développeurs choisissent de le faire?
demandé sur 2008-10-23 12:08:58
4
réponses

Pourquoi le problème du sac à dos est-il pseudo-polynomial?

je sais que Knapsack est NP-complet alors qu'il peut être résolu par DP. Ils disent que la solution DP est pseudo-pol ... trée). Malheureusement, je n'ai pas l'obtenir. Quelqu'un peut m'expliquer ce truc de pseudo-polynomial lentement ?
demandé sur 2010-12-27 15:19:21
13
réponses

Qu'est-ce qu'O(1)?

j'ai remarqué de très étranges utilisation de O(1) lors de la discussion des algorithmes impliquant hachage et les typ ... réponses, et certains des fils de commentaires sont un peu plus intéressants que leurs réponses, dans quelques cas.
demandé sur 2008-12-02 06:29:44
7
réponses

Différences entre complexité temporelle et complexité spatiale?

j'ai vu que dans la plupart des cas la complexité du temps est liée à la complexité de l'espace et vice versa. Par exempl ... me O(n)?). ma question:est-il possible qu'un algorithme ait une complexité temporelle différente de celle de l'espace?
demandé sur 2013-09-08 20:41:54
6
réponses

Quelle est la signification de O(polyglog(n)? En particulier, comment polylog(n) est-il défini?

Bref: Lorsque les articles universitaires (en informatique) disent "o(polyglog(n))", Que signifient-ils? Je ne suis pas c ... rer. dans quoi qu'il en soit, un lien vers une définition faisant raisonnablement autorité serait grandement apprécié!
demandé sur 2009-11-26 04:45:59
8
réponses

pourquoi accéder à un élément dans un tableau, constamment prendre le temps?

disons que j'ai un tableau comme: int a []={4,5,7,10,2,3,6} quand j'accède à un élément, comme un[3], Que se passe-t-il ... emps constant? (je suis un noob dans les bas-niveau de programmation donc je voudrais apprendre plus de vous les gars)
demandé sur 2011-09-04 11:31:51
3
réponses

Quelle est la complexité temporelle des algorithmes Regex moyens?

Je ne suis pas nouveau à utiliser des expressions régulières, et je comprends le base théorie ils sont basés sur -- machi ... che linéaire. (Si le regex est simple.) Où puis-je aller pour en savoir plus sur la mise en œuvre d'un moteur regex?
demandé sur 2011-05-05 06:51:12
2
réponses

La complexité temporelle des opérations python set?

Quelle est la complexité temporelle de chacune des opérations de jeu de python dans O notation? j'utilise Python's set ... pouvons peut-être s'en sortir? points supplémentaires pour trouver la complexité temporelle de régler les opérations.
demandé sur 2011-09-08 20:33:10
12
réponses

Quels sont les défauts de Drupal? [fermé]

Drupal est un CMS "tout faire". Il existe des modules qui vous permettent d'ajouter presque n'importe quelle fonctionnalit ... e. Suis-je le seul à avoir cette opinion? Quelles choses (le cas échéant) changeriez-vous à propos du noyau de Drupal?
demandé sur 2009-01-15 21:27:48
5
réponses

Différence entre O(n) et O(log(n)), ce qui est bon et ce qui est exactement O(log(n))?

c'est mon premier cours sur les structures de données et à chaque conférence / conférence D'AT , nous parlons de O(log(n)) ... probablement une question stupide, mais j'apprécierais si quelqu'un peut m'expliquer exactement ce que cela signifie !?
demandé sur 2012-04-29 07:57:42
1
réponses

Haskell GHC: Quelle est la complexité temporelle d'une correspondance pattern avec n constructeurs?

disons que nous avons le Haskell suivant: data T = T0 | T1 | T2 | ... | TN toInt :: T -> Int toInt t = case t of T ... GHC, quel algorithme est utilisé, et quelle est la complexité temporelle en termes de N, pour l'appariement des motifs sur t
demandé sur 2012-01-27 04:12:08
17
réponses

Quelle est la meilleure façon d'obtenir la valeur minimale ou maximale d'un Tableau de nombres?

disons que j'ai un tableau de nombres: [2,3,3,4,2,2,5,6,7,2] Quelle est la meilleure façon de trouver la va ... tout simplement pas être la meilleure façon de faire cela (j'essaie d'éviter les boucles chaque fois que possible).
demandé sur 2009-01-08 18:57:19
4
réponses

Les clés du dictionnaire Python. "Dans" la complexité

question rapide pour satisfaire principalement ma curiosité sur le sujet. if(key in dict.keys()): ...code... à: ... e pour moi d'utiliser la version du bas de mon code, mais alors j'étais juste curieux et j'ai pensé que je demanderais.
demandé sur 2013-07-09 07:25:11
4
réponses

Construire des instances monad efficaces sur " Set` (et autres conteneurs avec des contraintes) en utilisant la suite monad

Set, de même pour [] possède des opérations monadiques parfaitement définies. Le problème est qu'ils exigent que les valeu ... ut-être, il pourrait y avoir des cas où envelopper un calcul dans la suite monad le rendra exponentiellement plus long?)
demandé sur 2012-08-29 21:49:06
14
réponses

Bases de données par opposition au texte en clair

lorsqu'il s'agit de petits projets, ce qui vous semble être le point d'équilibre pour stocker des données dans des fic ... ser correctement les bases de données dans mon code au lieu des techniques plus ad hoc que j'utilise habituellement.
demandé sur 2009-02-05 06:44:26