Questions marquées «big-o»

Lors de chaque entretien dans lequel j'ai participé, on m'a interrogé sur l'analyse mathématique de la complexité, y compris la notation big-O. Quelle est la pertinence de l'analyse big-O pour le développement de l'industrie? À quelle fréquence l'utilisez-vous réellement et dans quelle mesure...

Cette question d'entrevue a été posée à l'un de mes amis - "Il y a un flux constant de nombres provenant d'une liste infinie de nombres dont vous avez besoin pour maintenir une structure de données afin de renvoyer les 100 premiers nombres les plus élevés à un moment donné. Supposons que tous les...

J'essaie de m'apprendre à calculer la notation BigO pour une fonction arbitraire. J'ai trouvé cette fonction dans un manuel. Le livre affirme que la fonction est O (n 2 ). Cela explique pourquoi, mais j'ai du mal à suivre. Je me demande si quelqu'un pourrait peut-être me montrer le calcul derrière...

Hier soir, je discutais avec un autre programmeur du fait que même si quelque chose peut être O (1), une opération qui est O (n) peut la surperformer s'il existe une constante de grande taille dans l'algorithme O (1). Il n'était pas d'accord, alors je l'ai amené ici. Existe-t-il des exemples...

J'essaie de comprendre ces classifications et pourquoi elles existent. Ma compréhension est-elle correcte? Si non quoi? P est la complexité polynomiale, ou pour un nombre réel non négatif , tel que , etc. Si un problème appartient à P, il existe au moins un algorithme capable de le résoudre à...

Aidez-moi! J'ai une question où j'ai besoin d'analyser le Big-O d'un algorithme ou d'un code. Je ne sais pas exactement ce qu'est Big-O ou comment il se rapporte à Big-Theta ou à d'autres moyens d'analyser la complexité d'un algorithme. Je ne sais pas si Big-O fait référence au temps d'exécution du...

J'en ai appris plus sur Big O Notation et comment le calculer en fonction de la façon dont un algorithme est écrit. Je suis tombé sur un ensemble intéressant de «règles» pour calculer la notation Big O d'un algorithme et je voulais voir si je suis sur la bonne voie ou à la dérive. Notation Big O: N...

Mergesort est un algorithme de division et de conquête et est O (log n) car l'entrée est divisée par deux à plusieurs reprises. Mais ne devrait-il pas être O (n) parce que même si l'entrée est divisée par deux par boucle, chaque élément d'entrée doit être itéré pour effectuer l'échange dans chaque...

Je rafraîchis ma théorie CS, et je veux savoir comment identifier cet algorithme de complexité O (log n). Plus précisément, existe-t-il un moyen facile de l'identifier? Je sais qu'avec O (n), vous avez généralement une seule boucle; O (n ^ 2) est une double boucle; O (n ^ 3) est une triple boucle,...

Donné sont deux tableaux triés a , b de type T de taille n et m . Je recherche un algorithme qui fusionne les deux tableaux dans un nouveau tableau (de taille maximale n + m). Si vous avez une opération de comparaison bon marché, c'est assez simple. Prenez simplement dans le tableau avec le premier...

Qu'est-ce que Big et O en notation Big O? J'ai lu les définitions et cela ne dit pas ce que O se prononce comme «oh». Par exemple - je comprends que O (n) est la complexité d'un algorithme linéaire où n pourrait être le nombre d'opérations. mais qu'est-ce qu'un O

J'ai l'algorithme suivant qui trouve les doublons et les supprime: public static int numDuplicatesB(int[] arr) { Sort.mergesort(arr); int numDups = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] == arr[i - 1]) { numDups++; } } return numDups; } J'essaie de trouver le pire cas de complexité...

Quel terme puis-je utiliser pour décrire quelque chose avec une complexité O (N log N)? Par exemple: O (1): Constante O (log N): Logarithmique O (N): linéaire O (N log N): ?????? O (N 2 ): Quadratique O (N 3 ): Cubique

La notation Big O fournit une limite supérieure à une fonction tandis que Big Theta fournit une limite stricte. Cependant, je trouve que la notation Big O est généralement (et informellement) enseignée et utilisée quand elle signifie vraiment Big Theta. Par exemple, "Quicksort is O (N ^ 2)" peut se...

Fermé . Cette question est basée sur l'opinion . Il n'accepte pas actuellement de réponses. Voulez-vous améliorer cette question? Mettez à jour la question afin d'y répondre avec des faits et des citations en modifiant ce message . Fermé l'année dernière . Disons que j'ai une fonction qui trie une...

Je pose cette question parce que je suis confus sur un aspect concernant la notation O grand. J'utilise le livre, Structures de données et abstractions avec Java de Frank Carrano. Dans le chapitre sur "l'efficacité des algorithmes", il montre l'algorithme suivant: int sum = 0, i = 1, j = 1 for (i =...

Étant donné une fonction arbitrairement double récursive, comment calculer son temps d'exécution? Par exemple (en pseudocode): int a(int x){ if (x < = 0) return 1010; else return b(x-1) + a(x-1); } int b(int y){ if (y <= -5) return -2; else return b(a(y-1)); } Ou quelque chose de ce genre....

Je suis programmeur et je viens de commencer à lire des algorithmes. Je ne suis pas complètement convaincu des notations à savoir Bog Oh, Big Omega et Big Theta. La raison en est par définition de Big Oh, elle précise qu'il devrait y avoir une fonction g (x) telle qu'elle soit toujours supérieure...

J'ai l'habitude de chercher à la main la notation Landau (Big O, Theta ...) de mes algorithmes pour m'assurer qu'ils sont aussi optimisés que possible, mais quand les fonctions deviennent vraiment grandes et complexes, ça prend le pas trop de temps pour le faire à la main. il est également sujet...

Je suis en train de résoudre une question d'algorithme et mon analyse est qu'elle fonctionnerait sur O (2 ^ sqrt (n)). Quelle est sa taille? Est-ce que cela équivaut à O (2 ^ n)? Est-ce encore du temps non