Powiem tak: nie mam dowodu, że moje rozumowanie jest poprawne, ale tak długo machałem rękami, że aż sam siebie przekonałem.
gmore pisze:Ciąg A najpierw maleje na jakimś przedziale, a potem rośnie (jeden z przedziałów może być zdegenerowany). Analogicznie ciąg B najpierw rośnie na jakimś przedziale, a potem już tylko maleje (też jeden z przedziałów może być zdegenerowany).
Koncepcyjnie poprawnie, do tego dochodzi jeszcze potencjalny przedział (właściwie dwa indeksy) równych wartości.
gmore pisze:Wyszukanie punktu zmiany monotoniczności w przypadku każdego z ciągów to jest jakieś \(\displaystyle{ O(ln(n))}\).
Tak, do tego potrzebujesz lekko zmodyfikowanego wyszukiwania ternarnego ekstremum funkcji unimodalnej — to skomplikowanie brzmi, ale jest bardzo podobne do wyszukiwania binarnego. Modyfikacja polega na uwzględnieniu faktu, że ekstremum może wystąpić dwukrotnie
gmore pisze:Znajdujemy te przedziały monotoniczności - jest jasne, że jeśli mają dwa punkty wspólne, to każdy leży w osobnych przedziałach. To znaczy może być tak, że A wszędzie rośnie i ma dwa punkty wspólne z B, ale w przypadku B już jeden z tych punktów będzie siedział w przedziale rosnącym, a drugi malejącym. Więc możemy szukać punktów wspólnych na przecięciach tych przedziałów (binarnie) - będziemy musieli sprawdzić maksymalnie cztery takie segmenty (np tam gdzie A rosnie, a B maleje, tam gdzie oba rosną itp) - ogółem wyjdzie suma kilku operacji \(\displaystyle{ O(ln(n))}\) czyli \(\displaystyle{ O(ln(n))}\). O to chodzi?
Koncepcyjnie tak, robi się trochę przypadków, ale da się je ogarnąć ifologią.
gmore pisze:Edit: nie no jednak nie wiem jak szukać wspólnego indeksu w posortowanych rosnąco tablicach szybciej niż w \(\displaystyle{ O(n)}\)
Podejrzewam, że rysunek pomoże, zwróć uwagę, że jedne wartości będą rosły coraz szybciej, a drugie coraz wolniej. Najpierw uciąglijmy funkcję. Przede wszystkim sprawdzasz, czy punkt przecięcia w ogóle istnieje, czyli sprawdzasz wartości na końcach przedziału.
Jeżeli
\(\displaystyle{ A_0 > B_0}\) i
\(\displaystyle{ A_n < B_n}\), to funkcje musiały się przeciąć dokładnie raz, więc możesz spróbować wyszukać ten indeks binarnie.
Jeżeli zaś
\(\displaystyle{ A_0 > B_0 \wedge A_n > B_n}\) oraz A rośnie coraz szybciej, a B coraz wolniej (w przeciwnym wypadku przecięcia nie ma), to chcesz znaleźć indeks, w którym funkcje zamienią się miejscami (czyli A jest pod B). Kluczowe jest dla Ciebie użycie nie tylko wartości w punkcie, ale także otoczenie. Bierzesz indeks środkowy, obliczasz styczne w punkcie i patrzysz, po której stronie się przetną, a następnie w tę stronę przesuwasz indeks i kontynuujesz wyszukiwanie binarne. Tutaj oczywiście masz wartości dyskretne, więc nie liczysz stycznej per se, tylko różnicę wartości w indeksie i w indeksie o jeden mniejszym, a potem na tej podstawie wnioskujesz. Jak już znajdziesz indeks „zamiany miejsc” (o ile takowy istnieje), to masz dwa przedziały z pojedynczym przecięciem każdy.
Sumarycznie wyjdzie pewnie jakieś osiem przypadków, z których część chyba nie zachodzi, do tego trochę ifów wartości na krańcach przedziałów i powinno pójść w czasie logarytmicznym.