Witam. Słyszałem gdzieś, że podobno część problemów algorytmicznych można redukować ze złożoności O(n^2) do o(n * sqrt(n)). O ile dobrze pamiętam jeżeli mamy dany jakiś ciąg liczb i mamy do wyboru 2 operacje: zmiana jakiejś liczby na inną albo odczytanie wartości na przedziale, jest ileś zapytań. Najprostszy sposób to sumy prefiksowe i uaktualnienie ich po każdej zmianie. I to zadanie można zrobić z użycie drzewa przedziałowego (logarytmicznie) a podobno także pierwiastkowo. Jak dokładnie, nie mam pojęcia. Mógłby ktoś zweryfikować tą metodę, a właściwie mi ją wytłumaczyć i najlepiej podać jeszcze jakiś klasyczny przykład wykorzystania? Podobno na olimpiadzie czasem można coś z tego zrobić.
Zadania z algorytmiki - złożoność n * sqrt(n)
- Rejestracja: dni
- Ostatnio: dni
- Postów: 1039
0
Szczerze, to trudno zrozumieć o co Ci dokładnie chodzi. Podejrzewam, że o coś jak Range Minimum Query.
- Rejestracja: dni
- Ostatnio: dni
1
Szukaj hasła Square Root Decomposition.
- Rejestracja: dni
- Ostatnio: dni
- Postów: 1028
1
Na przykładzie zadania "Kontenery", z drugiego etapu tegorocznej OI:
Treść zadania: https://sio2.mimuw.edu.pl/c/oi24-2/p/kon/
I teraz można zauważyć, że jeśli l_i > sqrt(n), to można wykonać naiwne stawianie, zwiększenie wartości w tablicy co l_ity element, gdyż takich operacji będzie maksymalnie sqrt(n). Jeśli jednak l_i jest większe od pierwiastka, to można trzymać w jednej tablicy długości d_i ile "przedziałów" jest otwartych (z początkami modulo d_i) i podczas wypisywania jedynie patrzeć ile z tych przedziałów było otwartych (oczywiście, trzeba trzymać wartości modulo d_i, bo to mówi czy ustawiono kontener czy nie). Takich różnych reszt jest maksymalnie sqrt(n), gdyż mamy warunek, że d_i * l_i <= n, a skoro l_i > sqrt(n), to d_i < sqrt(n). Sumarycznie, w obu przypadkach daje to złorzoność O(n sqrt(n)). Jeśli coś niejasne, pytaj.
- Rejestracja: dni
- Ostatnio: dni