Оценка сложности алгоритма

Цель работы – научиться оценивать временную и пространственную сложность алгоритмов, познакомиться с различными поисковыми структурами и алгоритмами поиска, сравнить их эффективность по памяти и количеству операций. Постановка задачи Произвести сравнение указанных в вариативной части структур данных по пространственной сложности и вычислительной сложности поиска. Работа выполняется в четыре этапа. На первом этапе требуется произвести теоретические расчеты сложности поиска и занимаемого структурой объема памяти (если в вариативной части не указано, что она должна вычисляться только в программе). На втором этапе нужно сформировать тестовый набор из 100 ключей, включив в него как имеющиеся в файле, так и отсутствующие в нем ключи (меньшие 10000000, большие 100000000 и принадлежащие интервалу [10000000; 100000000) ), стараться обеспечить равномерный поиск по всей структуре. На третьем этапе нужно написать программу, в которой реализовать обе указанные структуры данных, заполнив их всеми значениями из приложенного файла test_numbers.txt. Выполнить поиск 100 ключей в указанных структурах данных, для каждого ключа выводить сообщение о том, найден он или нет, и количество выполненных при поиске сравнений ключей, в конце программы вывести среднее количество сравнений, пришедшееся на один ключ. Подсчитать количество требуемой памяти для реализации каждой структуры и количество сравнений при поиске. На заключительном четвертом этапе требуется произвести анализ полученных теоретических и практических результатов, сравнить поисковые структуры по вычислительной и пространственной сложности и выбрать наиболее эффективную из них. Вариант № 4 Порядок: по возрастанию элементов. Методы: пузырька, шейкера, быстрая сортировка, сортировка естественным слиянием. N1=10000, N2=50000, N3=100000, N4=150000. Критерий – количество сравнений.