Как мне найти время работы с учетом скорости алгоритма и скорости компьютера?

Question

В настоящее время я работаю над заданием, которое касается Big-O и времени выполнения. Мне представили один вопрос, который мне кажется очень простым, но я не уверен, правильно ли я это делаю. Остальные проблемы были довольно сложными, и я чувствую, что здесь что-то упускаю.

Во-первых, у вас есть эти вещи: Алгоритм A, который имеет время работы 50n ^ 3. Компьютер А, который имеет скорость 1 миллисекунду за операцию. Компьютер B, который имеет скорость 2 миллисекунды за операцию. Экземпляр размером 300.

Я хочу выяснить, сколько времени требуется алгоритму A для решения этого экземпляра на компьютере A и сколько времени это занимает на компьютере B.

То, что я хочу сделать, это sub 300 in для n, поэтому у вас есть 50 * (300 ^ 2) = 4500000.

Затем умножьте это значение на 1 для первого компьютера и на 2 для второго компьютера.

Однако мне это кажется странным, потому что в нем говорится "время выполнения" равно 50n ^ 3, а не "количество операций равно 50n ^ 3", поэтому у меня возникает ощущение, что я умножаю время на время и получаю в квадрате единицы миллисекунд, что не совсем правильно все.

Я хотел бы знать, прав ли я, а если нет, что на самом деле означает этот вопрос.

Answer 1

Это не имело бы смысла, если бы у вас было O (n ^ 3), но вы не используете большие обозначения O в своем примере. То есть если бы у вас было O (n ^ 3), вы бы знали всю сложность вашего алгоритма, но не знали бы точное количество операций, как вы сказали.

Вместо этого похоже, что вам дано точное количество выполненных операций. (Даже знаю, что это прямо не указано). Таким образом, замена n будет иметь смысл.

Обозначение Big O описывает, как размер ввода влияет на время работы или использование памяти. Но с Big O вы не могли бы определить точное время работы, даже учитывая скорость каждой операции.

Размещение объяснения того, почему ваш ответ выглядит так просто (как я описал выше), также было бы безопасным способом. Но я уверен, что даже без этого вы получите оценки за этот вопрос.

Answer 2

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

Если алгоритму требуется 50n ^ 3 операций для выполнения чего-либо, где n - количество элементов для обработки, то замена 300 на n даст вам количество операций, которые нужно выполнить, а не единицу времени.

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

Выглядит прямо на меня.

Answer 3

Ваши данные 50 * n ^ 3 называются «время выполнения», но это потому, что модель, используемая для оценки скорости, предполагает машину с несколькими основными операциями, каждая из которых занимает 1 единицу времени.

В вашем случае запуск алгоритма занимает 50 * 500 ^ 3 единиц времени. На компьютере A каждая единица времени равна 1 мс, а на компьютере B - 2 мс.

Надеюсь, что это дает некоторый смысл подразделениям,
Асаф.