Pourquoi mergesort O (log 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 tableau divisé par deux? C'est essentiellement asymptotiquement O (n) dans mon esprit. Si possible, veuillez fournir des exemples et expliquer comment compter correctement les opérations! Je n'ai encore rien codé mais j'ai regardé des algorithmes en ligne. J'ai également joint un gif de ce que Wikipédia utilise pour montrer visuellement comment fonctionne Mergesort.

C'est O (n * log (n)), pas O (log (n)). Comme vous l'avez deviné, toute l'entrée doit être itérée, et cela doit se produire O (log (n)) fois (l'entrée ne peut être divisée par deux O (log (n)) fois). n éléments itéré log (n) fois donne O (n log (n)).

Il a été prouvé qu'aucun tri par comparaison ne peut fonctionner plus rapidement que cela. Seuls les tris qui reposent sur une propriété spéciale de l'entrée, comme le tri radix, peuvent battre cette complexité. Les facteurs constants du fusionnement ne sont généralement pas si bons que cela, donc les algorithmes avec une complexité pire peuvent souvent prendre moins de temps.

La complexité du tri par fusion est O (nlogn) et NON O (logn).

Le tri par fusion est un algorithme de division et de conquête. Pensez-y en termes de 3 étapes -

1. L'étape de division calcule le point médian de chacun des sous-tableaux. Chacune de ces étapes ne prend que O (1).
2. L'étape de conquête trie récursivement deux sous-tableaux de n / 2 (pour n même éléments) chacun.
3. L'étape de fusion fusionne n éléments, ce qui prend du temps O (n).

Maintenant, pour les étapes 1 et 3, c'est-à-dire entre O (1) et O (n), O (n) est plus élevé. Considérons que les étapes 1 et 3 prennent un temps O (n) au total. Disons que c'est cn pour une constante c.

Combien de fois ces étapes sont-elles exécutées?

Pour cela, regardez l'arborescence ci-dessous - pour chaque niveau de haut en bas, la méthode de fusion des appels de niveau 2 sur 2 sous-tableaux de longueur n / 2 chacun. La complexité ici est de 2 * (cn / 2) = cn Méthode de fusion des appels de niveau 3 sur 4 sous-tableaux de longueur n / 4 chacun. La complexité ici est 4 * (cn / 4) = cn et ainsi de suite ...

Maintenant, la hauteur de cet arbre est (logn + 1) pour un n donné. Ainsi, la complexité globale est (logn + 1) * (cn). C'est O (nlogn) pour l'algorithme de tri par fusion.

Crédits image: Khan Academy

Le tri par fusion est un algorithme récursif et la complexité temporelle peut être exprimée comme suit la relation de récurrence.

T (n) = 2T (n / 2) + ɵ (n)

La récurrence ci-dessus peut être résolue à l'aide de la méthode de l'arbre de récurrence ou de la méthode principale. Elle tombe dans le cas II de la méthode maître et la solution de la récurrence est ɵ (n log n).

La complexité temporelle du tri par fusion est ɵ (nLogn) dans les 3 cas (pire, moyen et meilleur) car le tri par fusion divise toujours le tableau en deux moitiés et prend un temps linéaire pour fusionner deux moitiés.

Il divise le tableau d'entrée en deux moitiés, s'appelle lui-même pour les deux moitiés, puis fusionne les deux moitiés triées. La fonction merg () est utilisée pour fusionner deux moitiés. La fusion (arr, l, m, r) est un processus clé qui suppose que arr [l..m] et arr [m + 1..r] sont triés et fusionne les deux sous-tableaux triés en un seul. Voir l'implémentation C suivante pour plus de détails.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

Si nous regardons de plus près le diagramme, nous pouvons voir que le tableau est récursivement divisé en deux moitiés jusqu'à ce que la taille devienne 1. Une fois que la taille devient 1, le processus de fusion entre en action et commence à fusionner les tableaux jusqu'à ce que le tableau complet soit fusionné.

Les algorithmes de tri basés sur la comparaison ont une limite inférieure 𝞨(n*log(n)), ce qui signifie qu'il n'est pas possible d'avoir un algorithme de tri basé sur la comparaison avec une O(log(n))complexité temporelle.

Soit dit en passant, le tri par fusion est O(n*log(n)). Pensez-y de cette façon.

[ a1,a2,         a3,a4,         a5,a6,          a7,a8     .... an-3,an-2,     an-1, an ] 
   \ /            \  /           \ /             \  /            \  /            \  /    
    a1'            a3'            a5'             a7'            an-3'           an-1'    
      \            /                \             /                 \             /
            a1''                          a5''                       an-3''
             \                             /                         /
                          a1'''                                     /
                           \
                                              a1''''

Cela ressemble à un arbre binaire inversé.

Laissez la taille d'entrée être n.

Chacun a_nreprésente une liste d'éléments. La première ligne a_nn'a qu'un seul élément.

A chaque niveau, la somme du coût de fusion est en moyenne n(il existe des cas d'angle dont le coût est inférieur [1]). Et la hauteur de l'arbre est log_2(n).

Ainsi, la complexité temporelle du tri par fusion est O(n*log_2(n)).

[1] si tri sur une liste déjà triée, ce qui est appelé le meilleur cas. le coût réduit à n/2 + n/4 + n/8 + .... + 1 = 2^log_2(n) -1 ~ O(n). (supposez que la longueur nest une puissance de deux)

Le tri est un problème NP-Complete en informatique (problème non polynomial). Cela signifie que, sauf preuve mathématique, vous ne pouvez pas descendre en dessous de O (n log n) lors du tri d'une liste d'éléments.

Consultez cet article sur Wikipedia ( https://en.wikipedia.org/wiki/P_versus_NP_problem )

Fondamentalement, jusqu'à présent, personne n'a réussi à prouver que (P == NP) et si vous le faites, vous devenez d'abord millionnaire, ensuite vous commencez la Troisième Guerre mondiale en raison du fait que vous serez en mesure de briser tous les mécanismes de sécurité de pub / clé privée utilisés partout de nos jours :)