Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Korsun
0 / 0 / 0
Регистрация: 30.05.2014
Сообщений: 64
1

Как найти время работы алгоритма?

07.02.2015, 18:57. Просмотров 933. Ответов 5
Метки нет (Все метки)

Пусть время работы алгоритма Т(N) = O(f(N)). Если X элементов обрабатываются за Y мсек., то во сколько раз следует ожидать увеличения времени выполнения при обработке Z элементов?
f(N)=1, X=1000, Y=12, Z=3000
По сути все просто, но каким образом это решается понять никак не могу. Подскажите пожалуйста
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2015, 18:57
Ответы с готовыми решениями:

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

Как найти время работы алгоритма, по заданным значениям?
Помогите пожалуйста найти время работы: Пусть время работы алгоритма Т(N) = O(logN). Если 2000...

Время работы алгоритма пирамидальной сортировки массива
Чему равно время работы алгоритма пирамидальной сортировки массива A длины n, в котором элементы...

Докажите, что время работы алгоритма равно Ɵ(g(n)
Помогите решить задачу. Докажите, что время работы алгоритма равно Ɵ(g(n)) тогда и только тогда,...

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

5
Tklwegsd
Эксперт 1С
787 / 564 / 195
Регистрация: 24.07.2013
Сообщений: 1,970
08.02.2015, 10:30 2
Если f(N) = 1, то время работы алгоритма не зависит от объема входных данных.
Время работы при любых X, Y, Z будет равно 1.
0
Mysterious Light
Эксперт по математике/физике
4096 / 2005 / 410
Регистрация: 19.07.2009
Сообщений: 3,025
Записей в блоге: 22
09.02.2015, 12:08 3
Tklwegsd, формально вы неправы: время может зависеть от обьема, но оно всегда будет меньше константы, не зависящей от обьема.

так что ожидать можно 1, но реально может быть любое число.
1
Tklwegsd
Эксперт 1С
787 / 564 / 195
Регистрация: 24.07.2013
Сообщений: 1,970
09.02.2015, 19:46 4
Mysterious Light, Но ведь формально f(N) = 1, в этой функции нет зависимости от N (объема данных).
С другой стороны, точно неизвестно, что конкретно подразумевается под этой функцией. Обычно, это асимптотическая оценка, и тогда в каждом конкретном случае может быть любое число.
0
ValeryS
Модератор
7870 / 5854 / 765
Регистрация: 14.02.2011
Сообщений: 20,127
Завершенные тесты: 1
09.02.2015, 19:52 5
Цитата Сообщение от Korsun Посмотреть сообщение
Т(N) = O(f(N))
я так понял зависимость линейная
тогда обыкновенная пропорция
X-- Y
----
Z-- ?

?=Z*Y/X
но вот это
Цитата Сообщение от Korsun Посмотреть сообщение
f(N)=1
ставит в тупик
0
Tklwegsd
Эксперт 1С
787 / 564 / 195
Регистрация: 24.07.2013
Сообщений: 1,970
09.02.2015, 20:07 6
f(N) = 1 говорит о том, что зависимость не линейная.

Добавлено через 56 секунд
Линейная это f(N) = N.
0
09.02.2015, 20:07
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2015, 20:07

Как вычислить время работы алгоритма на C#?

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

Как можна подсчитать время работы алгоритма (части программы).
Мне нужно подсчитать время виполнения алгоритмов сортировки масивов! Наведите пожалуста функции а...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.