ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

Нужно полное решение с отчётом Вариант№0 Написать программу для сравнения по заданному критерию указанных алгоритмов сортировки массивов, содержащих N1, N2, N3 и N4 элементов. Каждую функцию сортировки вызывать трижды: для сортировки упорядоченного массива, массива, упорядоченного в обратном порядке и неупорядоченного массива. Сортируемая последовательность для всех методов должна быть одинаковой (считывать необходимое количество элементов из созданного файла). Подсчитать количество указанных в вариативной части операций. Оценить эффективность алгоритмов сортировки по заданному критерию и объему требуемой дополнительно памяти. Задание 2. Реализовать две указанные структуры данных, заполнив их значениями из созданного файла, выполнить поиск вводимых с клавиатуры 100 ключей в указанных структурах данных, подсчитать количество сравнений при поиске. При формировании тестового набора включить в него ключи, имеющиеся в файле, и ключи, отсутствующие в файле, в том числе имеющие значения больше наибольшего и меньше наименьшего из присутствующих. Оценить количество требуемой памяти для реализации каждой структуры. Сравнить временную и пространственную сложность использованных поисковых структур. При оформлении отчета перед каждой программой привести теоретические расчеты трудоемкости в нотации О, для неуникальных ключей сделать предположения о том, как наличие повторов ключей повлияет на трудоемкость сортировки. После результатов работы программ сделать выводы о правильности выполненных расчетов и выбрать из анализируемых наиболее эффективный алгоритм. После первой программы, помимо этого, вычислить количество используемой каждым алгоритмом дополнительной памяти, а после второй – количество используемой каждой реализованной структурой данных памяти. По результатам проведенных вычислений сделать выводы по соотношению трудоемкость/объем_памяти для анализируемых алгоритмов. Порядок: по не возрастанию элементов. Методы: шейкерная, пирамидальная, многопутевое слияние, поразрядная. N1=50000, N2=90000, N3=120000, N4=150000. Критерий – количество присваиваний. 2. Декартово дерево, АВЛ-дерево.