001
13.06.2003, 09:49 Uhr
~0xdeadbeef
Gast
|
Das hier ist O(n):
| C++: |
#include <math.h>
int find_median_index(int [] arr, int len) {
int i, med_ix = 0, sum_n = 0;
double med = 0.0L;
for(i = 0; i < len; ++i) {
med + =((double) ((i+1)*arr[i]-sum_n))/((i+1)*(i+2));
sum_n += arr[i];
if(fabs(arr[i] - med) < fabs(arr[med_ix] - med)) med_ix = i;
}
return med_ix;
}
|
Das basiert darauf, dass du vom Median der ersten n Werte auf den Median der ersten n+1 Werte schließen kannst, indem du
1. Auf den Hauptnenner erweiterst, um in LaTeX zu sprechen:
| Code: |
\frac{\sum_{i=1}^n a_i}{n} = \frac{(n+1)\sum_{i=1}^n a_i}{n(n+1)}
|
2. Den Zähler hernimmst, das macht die Sache einfacher. Dann einmal die Summe von a_1 bis a_n abziehen und n*(a_{n+1}) draufrechnen:
| Code: |
(n+1) \sum_{i=1}^n a_i - \sum_{i=1}^n a_i + na_{n+1} = n \sum_{i=1}^{n+1}a_i
|
Im Endeffekt kriegst du
| Code: |
\frac{n\sum_{i=1}^{n+1}a_i}{n(n+1)} = \frac{\sum_{i=1}^{n+1} a_i}{n+1}
|
und das wollten wir ja haben. Also musst du bei jedem Iterationsschritt folgendes auf den Median draufaddieren:
| Code: |
\frac{na_{n+1} - \sum_{i=1}^n a_i}{n(n+1)}
|
und weil wir in C 0-basierte Arrays haben, sieht das in Code so aus:
| C++: |
med + =((double) ((i+1)*arr[i]-sum_n))/((i+1)*(i+2));
|
Kleinere Tipfeeler bitte ich zu entschuldigen, es geht mir um das grundsätzliche Rechenprinzip. |
