Я создал программу на C ++, которая выводит входной размер и время выполнения (микросекунды) алгоритмов и записывает результаты в файл .csv.После импорта .csv в LibreOffice Calc и построения графиков
я заметил, что бинарный поиск для входных размеров до 10000 выполняется в постоянное время, хотя я ищу элемент, не входящий в массив.Точно так же для одного и того же входного размера сортировка слиянием, кажется, выполняется в линейное время вместо линейно-логарифмического времени, в котором она выполняется во всех случаях.
Сортировка вставкой и сортировка пузырьками выполняются просто отлично, а выходной график напоминаетих наихудшая квадратичная сложность очень близка.
Я предоставляю входные массивы из файла.Для n = 5 содержимое файла выглядит следующим образом.Каждая строка представляет входной массив:
5 4 3 2 1
4 3 2 1
3 2 1
2 1
1
Файл результатов.csv при выполнении сортировки вставки:
Input,Time(ms)
5,4
4,3
3,2
2,2
1,2
График бинарного поиска для максимального ввода 100 здесь здесь.
Также график сортировки слиянием для максимального ввода 1000: здесь , который выглядит как линейный (значения в таблице также указывают на это).
Любая помощь по поводу того, почему это происходит, будет принята с благодарностью.
Вот ссылка на репозиторий github для исходного кода: https://github.com/dhanraj-s/Time-Complexity