Otóz mam rosnącą listę elementów i jaką strukturę mogę w tym przypadku zastosować aby wyszukanie elementu największego możliwego mniejszego od danego X było jak najszybsze do tej pory po prostu przechodziłem po elementach listy dopóki nie znalazłem większego od X i brałem poprzedni. Jakie rozwiązanie mogłoby przyspieszyć to działanie?
0
0
jedyne przyśpieszenie to posortowanie tej listy i dodawanie elementu w odpowiednie miejsce.
0
Jak juz wspomniałem lista jest posortowana. Tak więc nie da się nic lepszego wymyśleć? A zastosowanie np drzewa BST dla tych elementów przyspieszyłoby taką operację?
0
ale ile ty tych operacji potrzebujesz do znalezienie największego mniejszego od x? Dla 1 000 000 elementów potrzeba 20 (albo 21, nie pamiętam) porównań
0
Uzyj jakiegos zbalansowanego drzewa przeszukiwan. Gotowa implementacje masz w STL (map/set). Jest tez tam operacja znajdowania poprzednika. Zlozonosc wstawiania logn zlozonosc wyszukiwania poprzednika logn
0
Skoro masz posortowana tablice to mozesz uzywac wyszukiwania binarnego. Zlozonosc O(log n).