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)?
9 réponses
si vous voulez des exemples D'algorithmes/groupes d'énoncés avec la complexité de temps comme indiqué dans la question, voici une petite liste -
O(1) temps
1. Accès à L'Index des tableaux (int a = ARR[5];)
2. Insertion d'un noeud dans la liste liée
3. Poussant et poussant sur la pile
4. Insertion et retrait de la file d'attente
5. Trouver le parent ou l'enfant gauche/droit d'un noeud dans un arbre stocké dans le tableau
6. Aller à la page suivante / élément précédent dans la liste doublement liée
et vous pouvez trouver un million d'autres exemples de ce genre...
O(n) le temps
1. Traversée d'un réseau
2. Traversée d'une liste liée
3. Recherche Linéaire
4. Suppression d'un élément spécifique dans une Liste (Non triées)
5. Comparaison de deux cordes
6. Contrôle de Palindrome
7. Comptage / Tri De Seau
et ici aussi, vous pouvez trouver un million d'autres exemples de ce genre....
En un mot, tous les Algorithmes de force Brute, ou Noob ceux qui exigent la linéarité, sont basés sur O (n) la complexité du temps
O(log n) temps
1. Recherche Binaire
2. Trouver le plus grand / le plus petit nombre dans un arbre de recherche binaire
3. Certains Diviser et Conquérir des Algorithmes Linéaires de la fonctionnalité
4. Calcul Des Nombres De Fibonacci-Meilleure Méthode
Le principe de base ici n'est pas d'utiliser les données complètes, et de réduire la taille du problème à chaque itération
O(nlogn) temps
1. Fusion De Tri
2. Tas De Tri
3. Tri Rapide
4. Certains algorithmes de diviser pour mieux régner basés sur l'optimisation des algorithmes O(N^2)
Le facteur "log n" est introduit en prenant en considération diviser pour mieux régner. Certains de ces algorithmes sont les plus optimisés et fréquemment utilisés.
O(N^2) temps
1. Tri À Bulles
2. Insertion Tri
3. Tri De Sélection
4. Traversée d'un simple tableau 2D
Ceux-ci sont censés être les algorithmes les moins efficaces si leurs homologues O(nlogn) sont présents. L'application générale peut être brutale ici.
j'espère que cela répond bien à votre question. Si les utilisateurs ont plus d'exemples à ajouter, je serai plus qu'heureux :)
un exemple simple de O(1) pourrait être return 23; -- quelle que soit l'entrée, cela reviendra dans un temps fixe, fini.
un exemple typique de O(N log N) serait de trier un tableau d'entrées avec un bon algorithme (par exemple mergesort).
un exemple typique si O(log N) chercherait une valeur dans un tableau d'entrée trié par bisection.
O( 1) - la plupart des procédés de cuisson sont O(1), c'est-à-dire qu'il faut un temps constant même s'il y a plus de gens pour cuisiner (jusqu'à un certain point, parce que vous pourriez manquer de place dans votre casserole/Poêles et avoir besoin de diviser la cuisson)
O (logn) - trouver quelque chose dans votre annuaire téléphonique. Pensez à la recherche binaire.
O(n) - lecture d'un livre, où n est le nombre de pages. C'est le temps minimum qu'il faut pour lire un livre.
O (nlogn) - cant immédiatement penser à quelque chose que l'on pourrait faire tous les jours qui est nlogn...sauf si vous triez les cartes en faisant la fusion ou le tri rapide!
je peux vous offrir quelques algorithmes généraux...
- O (1): accès à un élément d'un tableau (i.e. int i = a[9])
- O(n log n): rapide ou mergesort (en moyenne)
- O (log n): recherche binaire
il s'agit des réponses intuitives, car cela ressemble à une question de travail ou d'entrevue. Si vous cherchez quelque chose de plus concret, c'est un peu plus difficile que le public en général. n'aurait aucune idée de la mise en œuvre sous-jacente (épargner open source bien sûr) d'une application populaire, ni le concept en général s'applique à une" application
O (1) - Suppression d'un élément d'une liste doublement liée. par exemple
typedef struct _node {
struct _node *next;
struct _node *prev;
int data;
} node;
void delete(node **head, node *to_delete)
{
.
.
.
}
la complexité de l'application logicielle n'est pas mesurée et n'est pas écrite en notation big-O. Il est seulement utile de mesurer la complexité de l'algorithme et de comparer les algorithmes dans le même domaine. Très probablement, quand nous disons O(n), nous voulons dire que c'est "O(n) comparaisons " ou "O (n) opérations arithmétiques". Cela signifie que vous ne pouvez comparer aucune paire d'algorithmes ou d'applications.
O(1): trouver le meilleur déménagement prochain dans les Échecs (ou Aller). Comme le nombre d'états de jeu est fini c'est seulement O(1) :-)
vous pouvez ajouter les algorithmes suivants à votre liste:
O(1) - déterminer si un nombre est pair ou impair; travailler avec HashMap
O(logN) - calcul x^n,
O(N Log N) - la plus longue augmentation ultérieure
O (N log n) est la limite supérieure de la vitesse à laquelle vous pouvez trier un ensemble arbitraire (en supposant un modèle de calcul standard et pas très parallèle).