[Algorytmy]znajdowanie "średniego" elementu w tablicy

[leg14]

Mamy daną tablicę \(\displaystyle{ A[1,..,n ]}\) liczb całkowitych i mamy znaleźć najmniejsze \(\displaystyle{ k}\) takie, że dla dowolnego \(\displaystyle{ i \in \left\{ 1,...,k\right\}}\) i dowolnego \(\displaystyle{ j \in \left\{ k,...,n\right\}}\) zachodzi \(\displaystyle{ A \le A[j]}\).
No więc da się to zrobić tak:

Kod: Zaznacz cały

int i =0; bool czy = false;

int x = A[0];

while (i<=n-1  && !czy) do

{

x= max(x,A[i]);

if (x <= min(A,i+1,n)) czy =true;

i++;

}



 

Gdzie max to funkcja zwracająca wiekszą z dwóch liczb, a min(int tab, int y_1,int y_2 ) to funkcja rekurencyjna zwracająca najmniejszą wartość tablicy na przedziale \(\displaystyle{ [y_1,y_2]}\). Ale w pesymistycznym układzie to jest około \(\displaystyle{ n}\) porównań liczb, \(\displaystyle{ n}\) wywoływań funkcji max i \(\displaystyle{ n}\) wywoływań funkcji min, która sama w sobie robi więcej niż \(\displaystyle{ \frac{y_2 - y_1}{2}}\) (ale mniej niż \(\displaystyle{ \frac{y_2 - y_1}{1}}\)) porównań liczb. Czyli razem jakoś \(\displaystyle{ n + n+ (n + n-1 + n-2 +...+1) \approx \frac{n^2}{2}}\). Da się szybciej?

[Takahashi]

Przejdź dwa razy tablicę i notuj, jakie było kroczące minimum / maksimum.

-- 10 paź 2017, o 19:38 --

Masz listę \(\displaystyle{ A \colon \{1, \ldots, n\} \to \mathbb Z}\).

Zdefiniuj \(\displaystyle{ A_\min \colon \{1, \ldots, n\}}\) wzorem \(\displaystyle{ A_{\min }(k) = \max\{A(m) : 1 \le m \le k\}}\) oraz \(\displaystyle{ A_{\max}(k) = \max \{A(m) : k \le m \le n\}}\).

Czy już widzisz?

[leg14]

No chyba czaje (zakladajac, ze torche Ci sie pomieszaly min i max w zapisie). Czyli tworze dwie takie nowe listy i sobie spokojnie porownuje ich wartosci (tak?). Rzeczywiscie szybciej, ale znacznie wiecej pamieci na to potrzeba.

[Takahashi]

Tak. Twoje rozwiązanie było kwadratowe w czasie i stałe w miejscu, moje jest liniowe tu i tam. Pytanie, na czym nam zależy. (I tak, pomyliły mi się oznaczenia przy kopiowaniu).

[leg14]

ok dzieki