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

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

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

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

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

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

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

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


performance complexity-theory
person Zachary Wright    schedule 19.10.2008    source источник
comment
Просто хотел отметить, что вы перешли от 50n ^ 3 в описании к 50n ^ 2 в своих расчетах. Излишне говорить, что это имеет большое значение в результате, который вы получите.   -  person Mark Bessey    schedule 23.10.2008

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

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

person Brian R. Bondy    schedule 19.10.2008

arrow_upward
1
arrow_downward

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

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

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

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

person Lasse V. Karlsen    schedule 19.10.2008

arrow_upward
0
arrow_downward

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

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

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

person Asaf R    schedule 19.10.2008