Questions sur time-complexity

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

Étant donné 2 tableaux triés d'entiers, trouver le nième plus grand nombre dans le temps sublinéaire [dupliquer]

possibilité de dupliquer: Comment trouver le kème plus petit élément dans l'union de deux tablea ... . Pour plus de simplicité, disons que les deux tableaux sont de la même taille et que tous les éléments sont uniques
demandé sur 2011-01-14 03:19:22
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
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

J'ai besoin de résoudre un problème NP-hard. Est-il de l'espoir?

il y a beaucoup de problèmes réels qui se révèlent être NP -hard . Si nous supposons que P ≠ NP , il n ... ces problèmes, est-il un espoir que vous serez en mesure de le faire efficacement? Ou êtes-vous juste pas de chance?
demandé sur 2014-12-13 07:36:48
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
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
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
5
réponses

Complexité temporelle du système.arraycopy ( ... )?

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) est une méthode native. Quelle est la complexité temporelle de cette méthode?
demandé sur 2011-08-23 22:11:28
2
réponses

Quand le pire des cas de Fusion de Tri se produire?

je sais que le pire des cas sur mergesort est O(nlogn), le même que la moyenne des cas. cependant, si les don ... deuxième matrice. Toutefois, nous pouvons faire plus que cela. Je suis à la recherche pour que les données d'entrée.
demandé sur 2014-07-06 12:39:34
3
réponses

Trouver Big O de la série harmonique

prouver que 1 + 1/2 + 1/3 + ... + 1/n is O(log n). Assume n = 2^k j'ai mis la série dans la sommation, mais je n'ai aucune idée de comment aborder ce problème. Toute aide est appréciée
demandé sur 2014-09-18 09:53:51
3
réponses

Complexité temporelle de la fonction pow () de la bibliothèque de mathématiques c++?

je voulais savoir quel est le pire cas de complexité temporelle de la fonction pow() construite en c++?
demandé sur 2012-11-16 18:05:23
2
réponses

La recherche de DataFrame de Pandas est-elle linéaire ou constante?

j'ai un objet dataframe df de plus de 15000 lignes comme: anime_id name genre rating ... r si cette recherche a été faite en temps constant (comme les dictionnaires) ou en temps linéaire(comme les listes).
demandé sur 2017-07-21 17:57:48
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
4
réponses

Comment est la complexité D'add(int, E) de O(1) de LinkedList?

De la liste liée tag wiki extrait: une liste liée est une structure de données dans laquelle les ... t certainement pas du temps constant. Qu'est-ce que je rate? Est-ce que j'ai mal compris la notation big-O?
demandé sur 2013-03-31 21:31:35
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
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
2
réponses

Complexité de l'exécution JavaScript des fonctions du tableau

est la complexité d'exécution définie par la norme JS sur les fonctions communes Array comme push , pop , shift ... lus, la réponse acceptée ne contient aucune référence indiquant que la norme la définit réellement de cette façon.).
demandé sur 2014-03-24 19:51:30
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
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