Comparer et contraster avec Big O

Par définition Si F et G sont des fonctions positives du vrai X positif, "g est O (f (x))" signifie qu'il existe des x et certains m tels que pour tous x> x: g (x) <= M * f (x)

Vous pouvez remplacer réel x avec N naturel N et obtenir la même définition.

En pratique, disons que vous avez un tableau (liste, vecteur) et vous avez une tâche.

Disons que le tableau des chiffres est commandé et que vous devez trouver un numéro particulier. Vous vérifiez donc le milieu de la matrice que vous ne comparez que vous obtenez avec numéro, vous devez trouver et vérifier la moitié supérieure ou la moitié supérieure de la moitié inférieure. Ensuite, vous continuez jusqu'à ce que vous trouviez le nombre de prouve qu'il n'y a pas de tel nombre. Le nombre de tentatives sera fermé pour log2 (n) afin que vous puissiez dire que le temps est O (journal n) car o (log2 n) est identique.

Si vous passez par numéro de tableau par numéro, vous devez vérifier que tous les éléments et le temps seront O (n). Disons que vous avez un million d'éléments. Ensuite, dans la recherche binaire, vous avez besoin d'environ 20 chèques, en pleine boucle dont vous avez besoin. C'est pourquoi la différence entre O (log n) et O (n) est essentielle.

Un autre exemple, vous devez commander (trier) un tableau. Vous pouvez trouver un élément minimal en vérifiant tous les éléments. Ensuite, vous trouverez le deuxième minimum en vérifiant tout en attendant d'abord, vous continuez jusqu'à ce que vous obteniez un élément le plus important. Les calculs de numéro sont N + (N-1) + ... + 2 + 1 = N (N + 1) / 2 qui est O (n ^ 2).

Vous pouvez également utiliser un algorithme de tri rapide où vous combinez une recherche binaire et une boucle totale à travers tous les éléments. Dans ce cas, le temps sera O (n * journal n)

Permet de dire que vous avez un million d'éléments dans la matrice. Si vous utilisez la première approche du tableau de tri, le temps sera fermé à (10 ^ 6) ^ 2 = 10 ^ 12 = 1 000 000 000 000 opérations (le nombre réel sera moins, mais ne comporte que le pouvoir). La deuxième approche donnera lieu à 10 ^ 6 * Log (10 ^ 6) qui est d'environ 10 ^ 6 * 10 = 10 000 000 (nombre réel sera également de 20 000 000 nous ne comptons pas lorsque nous vérifions BIG-O). Voir la différence.

même problème avec l'espace. Disons que vous devez faire quelque chose avec des valeurs d'entrée de l'utilisateur (fichier d'entrée) et vous n'avez pas d'autre choix que de garder toutes les valeurs en mémoire. Dans ce cas, vous avez besoin de la mémoire O (n). Toutefois, si vous trouvez une solution non trop, toutes les valeurs de la mémoire, mais uniquement la valeur d'entrée actuelle et peut-être d'autres variables techniques, vous dites que vous avez besoin de O (1) de mémoire. Comparez un million d'octets avec plusieurs octets pour voir à quel point il est critique.

Un exemple de tâche dans lequel vous n'avez pas besoin d'une matrice complète est de 2 derniers chiffres de produit pour toutes les valeurs données dans le fichier d'entrée. Vous n'avez pas besoin de réserver la mémoire pour la liste complète des valeurs.

La complexité spatiale en général est la quantité d'espace nécessaire pour effectuer une tâche particulière dans votre ordinateur.

Disons que vous disposiez d'une matrice avec 10 éléments aléatoires et que vous souhaitez renvoyer la matrice de tri.

Il y a couple de manières vous pouvez le faire

1) Créez un nouveau tableau et stockez les éléments de manière triée et retour New Array (Cette approche prendra espace supplémentaire et plus d'espace dépend généralement de la taille de la matrice d'origine)

2) Trier les éléments de la matrice en place sans utiliser d'espace / mémoire supplémentaire (cette approche est recommandée car elle n'a pas besoin d'espace supplémentaire)

Pensez maintenant à un tableau non formé dont la taille est dans milliards de milliards - si vous souhaitez extraire les éléments de la matrice dans la commande triée, vous ne voudriez pas créer une autre copie de la matrice dont la taille est en milliards et envoyer le nouveau tableau de tri.

Au lieu de cela, vous souhaitez modifier la matrice existante en place (sans utiliser d'espace supplémentaire)

La plupart de l'application que nous utilisons dans la vie quotidienne Utilisez des algorithmes sur place (comme QuickSort) où l'économie d'espace est une priorité absolue.

différence entre o (logn) et O (n * logn)

• journal (N) -> Si vous effectuez une recherche binaire sur N (par exemple 32) éléments triés, vous trouverez vos éléments dans le plus au plus ( log32 ), qui est 5 lorsque vous continuez à plonger votre tableau en 2 moitiés jusqu'à ce que vous trouviez votre élément.

• Cependant, n * journal (n) prend -> 32 * journal (32) ~ 32 * 5 qui est beaucoup plus grand que 5.

  Pensez maintenant aux éléments qui sont milliards de taille. Idéalement, votre objectif tout en écrivant un algorithme consiste à économiser du temps et de l'espace pour effectuer une opération particulière.

  Log (1 milliard) est beaucoup mieux que 1 milliard de fois log (1 milliard)

  Enfin, la complexité dépend de vos besoins mais la plupart du temps l'accent sera davantage sur la complexité du temps plutôt que la complexité spatiale.