Лабораторная работа по Алгоритмам 2.

Контест [email protected]

Препроцессинг

Препроцессинг Bruteforce алгоритма работает за O(1), поэтому его просто нет на графике.
На данном графике видно, что подготовка данных у алгоритма на карте работает за O(N^3), когда алгоритм на дереве O(NLogN).
Уже после 200 точек и прямоугольников, график взмывает вверх, когда алгортм на дереве начинает возврастать после 800.

Запросы

На графике видно, что простой алгоритм перебором проигрывает в скорости работы Map, Tree алгоритмам,
которые идут достаточно вровень друг с другом O(LogN).
Особоенно существенна разница уже после 100 точек и прямоугольников.

Выводы

Если у нас есть жесткие лимиты по памяти, то надо брать Bruteforce, потому что он в целом показывает хороший результат.
Но если нам важно время выполнения, то лидером конечно является алгоритм на дереве.
Если сравнить Map и Tree, то Map проигрывает Tree во всех случаях.
Поэтому при маленьких объемах данных можно выбирать между Bruteforce и Tree алгоритмами.
Потому что построение у Map слишком затратно. При больших данных лучше остаться на Tree.