Maximales Element finden

Autoren:- Devanshu Dalal , Yash Gaherwar

Zeitkomplexitätsanalyse :-

Wie viele von Ihnen haben darüber nachgedacht, was Zeitkomplexität ist. Viele denken, es hängt mit der Zeit zusammen und würde in Millisekunden oder einer anderen Zeiteinheit angegeben, aber das ist nicht der Fall. Mal sehen, die Zeitkomplexität ist die Anzahl der primitiven Operationen, die zum Ausführen oder Ausführen eines Algorithmus erforderlich sind.

Aber dann stellt sich die Frage, warum messen wir es nicht in Zeit?

Die Antwort ist, weil wir verschiedene Arten von Prozessoren haben, einige sind schnell, während andere langsam sind. Es macht also keinen Sinn zu sagen, dass mein Algorithmus auf einem OctaCore-Prozessor mit 8 GB RAM in 2 ms funktioniert. Unsere Zeitkomplexität sollte immer unabhängig vom Prozessor oder anderen externen Faktoren sein. Aus diesem Grund messen wir die Zeitkomplexität als die Anzahl der primitiven Operationen, die wir ausführen müssen.

Kommen wir zu unserem Hauptproblem.

Wir alle kennen das Problem, das maximale Element in einem gegebenen Array zu finden.

Alle könnten jetzt sagen, dass es ein einfaches Problem ist.

Ja, ein sehr einfaches Problem, aber wie viele von Ihnen haben über die durchschnittliche Anzahl von Operationen nachgedacht, die erforderlich sind, um das maximale Element zu finden.

Mal sehen mit einem Beispiel

Angenommen n = 3

Also alle möglichen Permutationen von Arrays für Elemente zwischen 1 bis 3 sind

[1,2,3]

[1,3,2]

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

Wir haben insgesamt 6 mögliche Arrays.

Sehen wir uns die Anzahl der Aktualisierungen an, die in der max-Variablen in den folgenden Permutationen enthalten sind, indem zunächst 1 Element als max-Element genommen wird.

Für [1,2,3]

Wir nehmen erstes Element 1 als maximales Element, anfänglich max=1, update=0

Dann 2>1, max =2, update=1

Dann 3>2, max=3, update=2

Insgesamt 2 Updates erforderlich

Lassen Sie uns nach [1,3,2] suchen

Wir nehmen erstes Element 1 als maximales Element, anfänglich max=1, update=0

Also 3>1, max=3, update=1

Dann 2, max=3, update=1

Insgesamt 1 Update erforderlich

In ähnlicher Weise berechnen wir für andere Permutationen von Arrays

Gesamtpermutation = 6

Gesamtaktualisierungen = 5

Durchschnittliche Aktualisierung = 5/6 = 0,83

Durchschnittliche Aktualisierung in Bezug auf n = 5/18 = 0,27

Ähnlich, wenn wir für andere Werte von n rechnen

Wir können hier sehen, dass die durchschnittlichen Aktualisierungen in Bezug auf n mit zunehmenden Werten von n abnehmen.

Die Berechnung auf diese Weise könnte jedoch ein sehr zeitaufwändiger Algorithmus sein.

Versuchen wir also, eine Wiederholungsbeziehung zu formulieren, damit wir diesen Algorithmus in einer besseren Zeitkomplexität lösen können.

Da der Wert der Aktualisierung in Bezug auf n abnimmt, können wir dies als eine Verbindung mit dem harmonischen Mittel sehen.

Mal sehen,

Die obige Gleichung würde uns helfen, die Nr. zu finden. des durchschnittlichen Aktualisierungsbedarfs als Funktion von n.

Lassen Sie uns die Wiederholungsrelation für dasselbe finden

Daher können wir jetzt mit Hilfe der obigen Wiederholungsbeziehung die Antwort in der linearen Zeitkomplexität unter Verwendung der dynamischen Programmierung finden.

Fazit:-

Aus der obigen Analyse wissen wir also, warum die Zeitkomplexität eine wichtige Rolle für jedes Datenstrukturproblem spielt. Hier haben wir die tatsächliche Analyse durchgeführt, wie das maximale Element in einem Array gefunden werden kann. Und wir haben auch die Analyse für verschiedene Permutationen von Arrays durchgeführt. Wir haben die Eigenzeitkomplexität in tabellarischer Form für verschiedene Werte von n erläutert, damit eine ordnungsgemäße Analyse durchgeführt werden kann. Ich hoffe, dies wird für alle hilfreich sein, um die Komplexität auf effiziente Weise zu verstehen.