| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сравнение времени работы |
| Автор: leahov 29.5.2008, 07:12 |
| Ребята помогите разобраться, вроде просто, но не могу въехать. Вот допустим пусть имеется алгоритм, решающий задачу размера n за f(n) микросекунд. Каков максимальный размер задачи, которую он сможет решить за время t ? Найти его для функций и времён log n за одну секунду, за 1 минуту, за час. В книжке Кормена как то не понятно написано (по крайней мере для меня). Ну например для секунды получается что надо 1*10^6*log(1*10^6) . Но есть чуйка что это не правильно |
| Автор: ksili 29.5.2008, 08:13 |
| Что подразумевается под функцией f? Какая-то конкретная функция? Тогда размером наверно будет f^-1(t). Если же имеется в виду o(n), т.е. время решения пропорционально размеру задачи, то и размер задачи, решаемой за время t должно быть пропорционально t. Не думаю, что есть смысл точно считать коэффициент пропорциональности, т.к. на время решения кроме алгоритмических вопросов влияет большое кол-во вопросов реализации. Кроме того, говорить о максимальном размере задачи можно, по-моему, только если f(n) - нижняя оценка времени. |