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

Question

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

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

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

То, что я хочу сделать, это саб 300 для 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 мс.

Надеюсь, это придаст смысл единицам,
Асаф.