Алгоритм: T(N) =2^N
Предположим, что количество операций, требуемых конкретным алгоритмом, точно равно T(n) = 2^n, и наша Компьютер с частотой 1,6 ГГц выполняет ровно 1,6 миллиарда операций в секунду. Какой самый большой проблема, с точки зрения n, которую можно решить менее чем за секунду? Менее чем за сутки?
Мне надоело 2^1,6 на секунду и 2^(1,6*60*24), но я думаю, что неправильно понял проблему.
В вашем заголовке написано 2 ^ N, в вашем вопросе написано 2 N, я думаю, вы имеете в виду 2 ^ n, должен ли я предположить 2 ^ n?
Да, извините за путаницу.
Если я не знаю k, должен ли я просто предположить, что это t = k / 1,6? И меня смущает, что если общее время равно t, а я не знаю k, то как мне узнать его время и как узнать, что это за секунду или час?
Итак, t(n) — это общее время?
Первый вопрос означает: найти н такое, что 2^n = 1600000000
24 часа в сутки * 60 минут в час * 60 секунд в минуту дает количество секунд в сутках. Умножьте на 1,6 миллиарда, чтобы получить количество операций, которые компьютер может выполнить за один день.
Итак, «за секунду» 2 ^ n = 1,6 миллиарда, и мне нужно найти n? А 'за сутки' это 24*60*60*1.6 операций? Тогда n тут ни при чем, а значит ответ для 'за секунду' будет 1,6 миллиарда напрямую?
Ответы 1
Что мы знаем:
- Чтобы быть менее 1 секунды, вам нужно выполнить менее 1,6 * 10 ^ 9 операций.
- Необходимое количество операций равно T (n) = 2 ^ n, где n - размер проблемы.
Ищем максимальное n (максимальный размер задачи до 1 сек). Итак, мы можем написать:
2^n <= 1.6*10^9
n <= ln(1.6*10^9) / ln(2)
n <= 30
So in one sec you can compute a problem of size 30
Теперь 1 день равен 24 * 60 * 60 секунд, поэтому:
2^n <= 86400 * 1.6*10^9
n <= ln(86400 * 1.6*10^9)/ln(2)
n <= 46
So in one day you can compute a problem of size 46
Представьте себе время, необходимое для задачи размера 64...
Ой! Спасибо! Итак, 1,6 миллиарда — это c(f(n)), но как узнать, что полный размер задачи равен 64?
Полный размер проблемы не 64. Это просто пример. При 2^n время очень быстро растет с размером n.
И я думаю, что вы забыли разделить ln(2) на день.
Если известно количество операций
K, то общее время их выполнения равноt = K / (1.6 B / second)