Diese Frage wird oft gestellt (ist das eine beliebte Hausaufgabenfrage oder etwas?) und die Antwort ist immer die gleiche: nein .
Denk darüber mathematisch nach. Wenn das Array nicht sortiert ist, gibt es nichts, was "halbiert" werden kann, um Ihnen das Verhalten log(n) zu geben.
Lesen Sie die Fragekommentare für eine tiefer gehende Diskussion (die wahrscheinlich sowieso nicht in Frage kommt).
Dies ist in O(log(N)) nicht möglich. Es ist O(N) im besten / schlechtesten / durchschnittlichen Fall, weil man jedes Element im Array aufsuchen müsste, um festzustellen, ob es das Größte ist oder nicht. Array ist unsortiert, was bedeutet, dass Sie keine Ecken schneiden können.
Selbst im Fall der Parallelisierung kann dies nicht in O(N) durchgeführt werden, da es für die Big-O -Notation egal ist, wie viele CPU man hat oder wie hoch die Frequenz jeder CPU ist. Es wird speziell davon abstrahiert, um ein rohes Estagam des Problems zu erhalten.
Die Parallelisierung kann vernachlässigt werden, da die Zeit, die zum Teilen eines Jobs aufgewendet wird, der Zeit der sequentiellen Ausführung gleichgesetzt werden kann. Dies liegt daran, dass Konstanten vernachlässigt werden. Die folgenden sind alle gleich:
%Vor%Andererseits können in der Praxis parallele Algorithmen, die Sie teilen und beherrschen, Ihnen einige Leistungsvorteile bringen, so dass sie ein wenig schneller laufen können. Glücklicherweise befasst sich Big-O nicht mit dieser feinkörnigen algorithmischen Komplexitätsanalyse.
Nein. Ist Zustand). Im schlimmsten Fall müssen alle Mitglieder des Arrays besucht und verglichen werden.
Natürlich NICHT. Angenommen, es gibt immer noch ein Element, das Sie noch nicht mit irgendeinem anderen Element verglichen haben. Es gibt also keine Garantie, dass das Element, das Sie nicht verglichen haben, nicht das maximale Element ist.
und nehmen an, dass Ihr Vergleichsdiagramm (Scheitelpunkte für Elemente und Kanten zum Vergleichen) mehr als eine Komponente enthält. in diesem Fall müssen Sie eine Kante (in der besten Weise zwischen maximal zwei Komponenten) setzen. Wir können sehen, dass bei n-1-Betrieb getan werden muss
Das ist sehr alt, aber ich stimme den Antworten nicht zu. YES kann mit paralleler Hardware in logarithmischer Zeit durchgeführt werden.
Zeitkomplexität wäre:
%Vor% n ist die Anzahl der zu vergleichenden Zahlen; m ist die Größe jeder Zahl.
Die Hardware-Größe wäre jedoch:
%Vor%Der Algorithmus wäre:
Vergleichen Sie Zahlen paarweise. Die Zeit hierfür ist O(log(m)) und die Größe ist O(n * m) , wobei carry look-ahead-Komparatoren verwendet werden.
Verwenden Sie das Ergebnis in 1, um beide Eingänge von 1 zu multiplexen. Die Zeit ist O(1) und die Größe ist O(n * m) .
Jetzt haben Sie ein Array mit der halben Anfangsgröße; gehe zu Schritt 1. Diese Schleife wird log(n) mal wiederholt, also ist die Gesamtzeit O(log(n) * log(m)) und die Gesamtgröße ist O(n * m) .
Wenn Sie weitere MUXs hinzufügen, können Sie auch den Index der größten Zahl verfolgen, wenn Sie sie brauchen, ohne die Komplexität des Algorithmus zu erhöhen.