Нет способа узнать точно , но есть практические правила, которые позволят вам получить очень грубое приближение времени бега.
Вставка сортировки является алгоритмом O (n 2 ). В реальном мире это означает, что при прочих равных условиях увеличение размера n на некоторое число x увеличит время работы примерно на n 2 . Так что если вы удвоите размер n, время выполнения увеличится примерно в 4 раза. Если умножить n на 6, время выполнения увеличится примерно в 36 раз.
К сожалению, вы не всегда можете держать другие вещи равными. Вы должны подумать о последствиях пропадания кеша, виртуальной памяти, других вещей, работающих на компьютере, и т. Д. Асимптотический анализ на самом деле не является инструментом для вычисления времени выполнения в реальном мире, но он может служить очень грубым приближением: "оценка парка мячей", если хотите.
Другие алгоритмы сортировки имеют разные порядки сложности. Например, сортировка слиянием имеет вычислительную сложность O (n log n), что означает, что время выполнения увеличивается с логарифмом числа элементов. Это увеличивается намного медленнее, чем n ^ 2. Например, сортировка 1024 элементов (2 ^ 10) требует порядка (2 ^ 10 * 10) сравнений. Сортировка 2 ^ 20 элементов потребует порядка (2 ^ 20 * 20) сравнений.
Я не могу особо подчеркнуть, что эти расчеты являются очень грубыми приближениями. Они доставят вас в этот район - возможно, на порядок - но вы никогда не получите точное число таким образом.
То, что вы не можете сделать с какой-либо степенью уверенности, это сказать, что если сортировка вставкой занимает x времени, то сортировка слиянием займет y времени. Асимптотический анализ игнорирует постоянные факторы. Таким образом, вы даже не можете приблизить время выполнения сортировки слиянием на основе времени выполнения сортировки вставкой. Также, в этом отношении, вы не можете приблизить пузырьковую сортировку (другой алгоритм O (n ^ 2)) на основе времени выполнения сортировки вставкой.
Вся идея использования асимптотического анализа для оценки реального времени работы алгоритма чревата ошибкой. Он часто работает при оценке времени выполнения одной реализации одного алгоритма на конкретном оборудовании, но помимо этого он бесполезен.
Обновление
Вы спросили:
для n = 2 ^ 20, M секунд для сортировки слиянием и B секунд для пузырьковой сортировки. Если у меня другой размер, который занимает 4B для пузырьковой сортировки, как узнать время выполнения сортировки слиянием?
Как я указывал выше, вы не можете оценить время сортировки слиянием, основываясь на времени пузырьковой сортировки. То, что вы можете сделать, - это оценить время выполнения сортировки слиянием для нового размера на основе времени выполнения сортировки слиянием при размере n = 2 ^ 20.
Например, при n = 2 ^ 20 сортировка слиянием требует порядка (2 ^ 20 * 20) сравнений. При n = 2 ^ 21 требуется порядок (2 ^ 21 * 21) сравнений. При n = 2 ^ 32 (2 ^ 32 * 32) сравнений.
Затем вы можете взять ожидаемое количество сравнений для вашего нового n, вычислить ожидаемое количество сравнений и разделить его на (2 ^ 20 * 20). Так, например, когда n = 2 ^ 22, ожидаемое количество сравнений составляет приблизительно 92 274 688. Разделите это на 20 971 520 (2 ^ 20 * 20), и вы получите 4,4. Итак, если сортировка 2 ^ 20 элементов с сортировкой слиянием занимает время x, то сортировка 2 ^ 22 элементов займет приблизительно 4.4 * x.
Опять позвольте мне указать, что это очень грубые приближения , которые предполагают, что все остальное остается равным.