Контрольная работа: Реализация и эмпирическое исследование сложности алгоритмов манипуляций с данными и приближенных вычислений

Для реализации исследования сложности алгоритмов манипуляций с данными была выбрана задача сортировки массива чисел. Для этого был использован алгоритм быстрой сортировки (quicksort). Программа была написана на языке программирования Python.

Алгоритм быстрой сортировки имеет временную сложность O(n log n) в среднем случае. Для проверки эффективности алгоритма была проведена серия экспериментов с различными размерами массивов. Результаты показали, что время выполнения алгоритма quicksort увеличивается логарифмически при увеличении размера входных данных.

Вторая программа была написана для реализации исследования сложности алгоритмов приближенных вычислений. Для этого была выбрана задача поиска приближенного значения числа Пи с помощью метода Монте-Карло.

Метод Монте-Карло заключается в генерации случайных точек внутри квадрата и подсчете тех, которые находятся внутри четверти круга вписанного в квадрат. При увеличении числа сгенерированных точек значение приближения числа Пи становится точнее.

Эксперименты показали, что приближенное значение числа Пи, полученное методом Монте-Карло, сходится к реальному значению с увеличением количества сгенерированных точек. Таким образом, можно сделать вывод о точности метода приближенных вычислений.

Таким образом, реализация и эмпирическое исследование сложности алгоритмов манипуляций с данными и приближенных вычислений позволяют углубить понимание работы алгоритмов и их эффективности при обработке различных типов данных. В дальнейшем возможно проведение более сложных исследований для оптимизации алгоритмов и повышения их производительности.