Алгоритм: T (N) = 2 ^ N

Question

Предположим, что количество операций, требуемых конкретным алгоритмом, равно T (n) = 2 ^ n, и наш компьютер с частотой 1,6 ГГц выполняет ровно 1,6 миллиарда операций в секунду.Какая самая большая проблема, с точки зрения n, может быть решена менее чем за секунду?Менее чем за день?

Я устал 2 ^ 1.6 за секунду и 2 ^ (1.6 * 60 * 24), но я думаю, что я неправильно понял проблему.

Answer 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

Итак, за одну секунду вы можете вычислить задачу размером 30

Теперь 1 день равен 24 * 60 * 60 секундам, поэтому:

2^n <= 86400 * 1.6*10^9 
n <= ln(86400 * 1.6*10^9)/ln(2)
n <= 46

Итак, за один день вы можете вычислить задачу размером 46

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