[Algorytmika] Przekątne prostokątów

[gmore]

Mamy dane dwie tablice rzeczywiste długości \(\displaystyle{ n}\) , oznaczmy je przez \(\displaystyle{ A,B}\) . \(\displaystyle{ A}\) jest posortowana niemalejąco, a \(\displaystyle{ B}\) nierosnąco. pary \(\displaystyle{ A[k],B [k]}\) interpretujemy jako boki pewnego prostokąta i chcemy znaleźć taki indeks, który da prostokąt o najkrótszej przekątnej.
Wiadomo, że chodzi nam o jakąś pochodną wyszukiwania binarnego i koszt \(\displaystyle{ O(\ln(n))}\) . Ale nie mogę znaleźć żadnego punktu zaczepienia. Jeśli potraktujemy te przekątne jako funkcję \(\displaystyle{ f: [0,...,n] \rightarrow \RR}\) , gdzie \(\displaystyle{ f(k)}\) , to długość przekątnej \(\displaystyle{ k}\) -tego prostokąta i pozostałe wartości otrzymujemy przez łączenie punktów łamanymi, to ta funkcja zdaje się nie mieć absolutnie żadnych sensownych własności (wypukłość itp).

[Afish]

Przy podanych założeniach nie da się binarnie. Weź takie dane:

Kod: Zaznacz cały

A = [5, 5, 5]
B = [10, 5, 1]

Po sprawdzeniu środkowej pary możesz podjąć decyzję o skierowaniu swych kroków w prawo (do większych indeksów) lub w lewo. W tym wypadku pasuje w prawo, ale jak weźmiemy takie dane:

Kod: Zaznacz cały

A = [1, 5, 5]
B = [5, 5, 5]

to wypadałoby w lewo. Nie jesteś w stanie podjąć decyzji na podstawie pojedynczego indeksu.

[gmore]

No właśnie, to miałem na myśli. Czyli co – prymitywny liniowy algorytm?

[Afish]

A dlaczego prymitywny? Algorytm jak algorytm.