Algorithmes: comment additionner O (n) et O (nlog (n)) ensemble?

22

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é temporelle de cela. Je sais que mergesort est nlog(n), et dans ma boucle for, j'itère sur l'ensemble des données afin que cela compte n. Je ne sais pas quoi faire de ces chiffres. Dois-je simplement les additionner ensemble? Si je devais le faire, comment le ferais-je?

algorithms algorithm-analysis big-o chopper dessiner lion4
la source
1
Remarque: vous pouvez utiliser une table de hachage pour le faire dans O (n) en fonction des besoins en mémoire.
corsiKa

Réponses:

67 
O(n) + O(n log(n)) = O(n log(n))

Pour la complexité de Big O, vous ne vous souciez que du terme dominant. n log(n)domine ndonc c'est le seul terme qui vous intéresse.

Justin Cave
la source
4
Une autre façon de penser à cela est d'imaginer que votre traitement O (n) était vraiment O (n log n), comme si vous faisiez deux sortes indépendantes. Vous auriez alors 2 * O (n log n). Mais les constantes disparaissent, vous êtes donc de retour à O (n log n).
Jonathan Eunice
4
@Jonathan Bien que cela fonctionne dans la pratique, il est tout à fait vrai que O (n) n'est pas égal à O (n log (n)), donc je ne conseillerais pas de l'utiliser régulièrement.
Aza
17
@Emrakul en fait je pense que le raisonnement est théoriquement aussi bien que pratique. O (n) est un sous-ensemble approprié de O (n log (n)). Donc, si f (n) appartient à O (n), il appartient également à O (n log (n)).
emory
17
Il convient de noter que lorsque nous disons f(n) is O(g(n))ce que nous disons vraiment, c'est que la fonction f is a member of the set of functions that grows at the rate of at most g(n) over the long term. Cela signifie que tous les membres de O(n)sont également membres de O(n*log(n)). Les +expressions in comme O(f(n)) + O(g(n))se réfèrent en fait à set union (lequel d'entre vous êtes vraiment pédant, vous devriez vraiment utiliser ∪).
Lie Ryan
3
@LieRyan A l' origine, il n'est pas défini union, mais somme ensemble: A + B = { a + b | a in A, b in B }. Il arrive que pour les ensembles de la forme, O(g(n))c'est la même chose que l'union d'ensemble, car l'un des ensembles est toujours un sous-ensemble de l'autre, et ils sont tous deux invariants aux sommes (c'est-à-dire A + A = A). (Oups, Nate a écrit essentiellement la même chose).
Paŭlo Ebermann
56

Raisonnons notre chemin et rappelons-nous la définition de O. Celui que je vais utiliser est pour la limite à l'infini.

Vous avez raison de dire que vous effectuez deux opérations avec des bornes asymptotiques correspondantes de O(n)et O(nlog(n))mais les combiner en une seule borne n'est pas aussi simple que d'ajouter les deux fonctions. Vous savez que votre fonction prend au moins du O(n)temps et aussi au moins du O(nlog(n))temps. Donc, vraiment, la classe de complexité de votre fonction est l'union de O(n)et O(nlog(n))mais O(nlog(n))est un surensemble de O(n)si vraiment c'est juste O(nlog(n)).

davidk01
la source
12
+1, cela devrait être la réponse. Il décrit la réponse plus précisément en utilisant des termes compsci.
5

Si vous deviez l'exposer à la main, cela ressemblerait à peu près à ceci:

Supposons que le temps total soit: an + bn log (n), où a et b sont des constantes (en ignorant les termes d'ordre inférieur).

Lorsque n va à l'infini (an + bn log (n)) / n log (n) -> a / log (n) + b -> b

Le temps total est donc O (bn log (n)) = O (n log (n)).

richardb
la source
2

Commençons par la définition de O ():

O (n log n) signifie "inférieur à C n log n, si n est grand".

O (n) signifie "inférieur à D n, si n est grand".

Si vous ajoutez les deux, le résultat est inférieur à C n log n + D n <C n log n + D n log n <(C + D) n log n = O (n log n).

En général, si f (n)> C g (n) pour les grands n et certains C> 0, alors O (f (n)) + O (g (n)) = O (f (n)). Et après avoir fait quelques cas en utilisant la définition de O (), vous saurez ce que vous pouvez et ne pouvez pas faire.

gnasher729
la source
1

La grande notation O est définie comme un ensemble:

entrez la description de l'image ici

entrez la description de l'image iciContient donc toutes les fonctions qui sont - à partir d'un grand point arbitraire entrez la description de l'image ici- toujours plus petites que g.

Maintenant, quand vous avez une fonction qui est dans entrez la description de l'image ici, puis exécutez une autre qui augmente plus lentement que g, elle augmente certainement plus lentement que 2g. Donc, exécuter quelque chose de plus lent que g ne changera pas la classe de complexité.

Plus formellement:

f, h \ in \ mathcal {O} (g) \ Rightarrow (f + h) \ in \ mathcal {O} (g)

Vous pouvez facilement le prouver.

TL; DR

Il est encore n log (n)

Martin Thoma
la source