0
Einfügesortieren erfordert das Einfügen eines Elements in sortierter Reihenfolge, indem die Elemente einer bereits sortierten Liste verschoben werden, während über Array implementiert wird. Wenn wir Arrays verwenden, verwenden wir die doppelt verknüpfte Liste, was wäre die Zeitkomplexität?Komplexität der Einfügung Sortierung mit Doubly Linked List?
Zeit Komplexität ergibt sich O (n^2)? Warum? Wenn wir die Einfügung für n Elemente betrachten, dann ist es log (1) + log (2) + log (3) + ..... + log (n) - n mal für n Elemente daher Komplexität sollte O sein (nlogn)
Was lässt Sie denken, dass es "log (1) + log (2) + ... + log (n)" ist und nicht "1 + 2 + ... + n"? Bitte fügen Sie weitere Details in die Fragen ein, damit Sie bessere informative Antworten erhalten - was eher erklären wird, wo Ihr Fehler liegt. – amit
für die Einfügung mit der Einfügesortierung Wenn wir eine doppelt verknüpfte Liste verwenden, dauert die Einfügung eines Elements die Zeit log (k), wobei k die Anzahl der bereits sortierten Elemente ist – Luv