Проблема HW во время выполнения программы

Question

Для алгоритма требуется 0,5 мсек. размер ввода 100, как долго это будет взять для запуска, если размер ввода составляет 500 и программа O (n lg (n))?

В моей книге говорится, что при удвоении размера ввода n lg (n) занимает «чуть более чем вдвое больше времени». Это не очень мне помогает.

То, как я это делал, это решение для постоянного множителя (о котором книга не говорит, поэтому я не знаю, действительно ли это):

.5ms = c * 100 * lg (100) => c = .000753

So

.000753 * 500 * lg (500) = 3,37562мс

Это правильный способ подсчета времени работы и есть ли лучший способ выяснить это?

Answer 1

Это не совсем верно. Томас был прав, говоря, что есть накладные расходы, а реальное уравнение больше похоже на

runtime = inputSize * lg(inputSize) * singleInputProcessTime + overhead

singleInputProcessTime имеет отношение к машинным операциям, таким как загрузка адресных пространств, арифметика или что-либо, что должно выполняться каждый раз, когда вы взаимодействуете с вводом. Обычно это имеет время выполнения, которое варьируется от нескольких циклов ЦП до секунд или минут в зависимости от вашего домена. Важно понимать, что это время примерно ПОСТОЯННО и, следовательно, не сильно влияет на общее время выполнения. ДА НУЖНО БОЛЬШИЕ входные размеры.

Издержки - это стоимость установки проблемы / решения, такого как чтение алгоритма в память, распределение входных данных между серверами / процессами или любая операция, которая должна выполняться только один раз или определенное количество раз, которая НЕ зависит от входной размер. Эта стоимость также постоянна и может варьироваться от нескольких циклов ЦП до минут в зависимости от метода, используемого для решения проблемы.

InputSize и n * lg (n), о которых вы уже знаете, но что касается вашей домашней задачи, если вы объясните, как вы пришли к решению, у вас все будет в порядке.

Answer 2

Да. Именно так и работает.

Конечно, это игнорирует любые возможные издержки инициализации, так как это не указано в нотации big-o, но это не имеет значения для большинства алгоритмов.