Im folgenden Java-Code zu finden:Erwartete Anzahl der Zuordnungen Maximalwert in einem Array
int max = arr[0];
for (int i = 0; i < arr.length i++) {
if (arr[i] > max) {
max = arr[i];
}
}
Wie oft macht die Linie max = arr[i]; läuft unter der Annahme, dass das Array unsortiert ist.
Erwarteter Wert kann über die Linearität der Erwartungen berechnet werden. Ich könnte eine genauere Antwort geben, wenn diese Seite MathJax unterstützt.
Die Antwort ist Summe 1/(n-i + 1) für i = 1 bis n = Summe 1/i für i = 1 bis n = O (log n) wobei n die Größe des Arrays ist (angenommen alle Elemente des Arrays sind unterschiedlich)
Warnung, Math-sy Teil voraus. Die Schlüsselidee ist, dass, wenn wir jedem Element einen lexikographischen Index 'i' zuweisen, wobei 'i' bedeutet, dass das Element das 'i'te kleinste Element ist, dann wird eine Zuweisung nur dann erfolgen, wenn keiner der n-i +1 größere Elemente apprar vor dem ith-Element im Array. Die Wahrscheinlichkeit, dass dies in einem zufälligen Array geschieht, ist 1/(n-i + 1) für alle i. Dann wenden wir einfach die Linearität der Erwartungen an, indem wir eine Indikator-Zufallsvariable verwenden :)
Siehe auch https://en.wikipedia.org/wiki/Harmonic_series_(mathematik) –
Jedes Mal, wenn ein Wert im Array kleiner als der Maximalwert gefunden wird. – sAm
Aber es muss eine numerische erwartete Anzahl von mal es läuft – 12345webster12345
Dieser Code ist für das Minimum, nicht das Maximum. –