Я просто написал алгоритмы сортировки быстрых и слияний, и я хочу сделать график логарифмического журнала их времени выполнения и размера массива для сортировки.Лог-лог-график/график сложности алгоритма
Как я никогда не делал этого, мой вопрос заключается в том, имеет ли значение произвольные числа для длины массива (размер ввода) или я должен следовать шаблону (что-то вроде 10^3, 10^4, 10^5 , и т.д)?
В общем, вам нужно выбрать длины массивов для каждого метода, которые достаточно велики для отображения ожидаемого поведения типа o (n log n) или O (n^2).
Если ваше n слишком мало, время выполнения может зависеть от других темпов роста, например, алгоритм с временем запуска = 1000000 * n + n^2 будет выглядеть равным ~ O (n) для n < 1000. Для большинства алгоритмов малое поведение n означает, что ваш лог-лог-график будет изначально изогнут.
С другой стороны, если ваше n слишком велико, ваш алгоритм может занять слишком много времени.
Лучший компромисс может заключаться в том, чтобы начать с малых n и времени для n, 2n, 4n, ... или n, 3n, 9n, ... и продолжать увеличиваться, пока вы не сможете четко видеть графики журнала асимптотику к прямым линиям.
Быстросортированные и объединенные объекты имеют одинаковую (среднюю) временную сложность, то есть O (n log n). Вы действительно имеете в виду «время работы»? –
Собственно, да. Я запутался. Я сразу отредактирую вопрос. – PetarMI