асимптотическая сложность

Question

предположим, что компьютер выполняет одну инструкцию в микросекунду, а алгоритм, как известно, имеет сложность O (2 ^ n), если этому алгоритму отводится максимум 12 часов компьютерного времени, определите максимально возможное значениеn, для которого может использоваться алгоритм

Answer 1

Нет, можно сделать.

O(2^n) означает, что существует C такое, что limit n->infinity f(n)<=C*(2^n).
Но это C также может быть числом 023945290378569237845692378456923847569283475635463463456, поэтому даже 12 часовне может гарантировать, что он будет работать даже на небольшом входе.

Answer 2

Недостаточно информации.Алгоритм с O (2 ^ n) не обязательно должен делать ровно 2 ^ n шагов для ввода размера n, он может принимать постоянный коэффициент этого.Фактически, это может занять операции C * (2 ^ n) + B, где C и B являются постоянными (то есть они не зависят от n), они оба являются целыми числами, а C> = 1 и B>= 0.

Answer 3

Ну, так как O (2 ^ n) - экспоненциальная сложность, и вас просят указать «максимально возможный показатель», вы пытаетесь найти N, так что 2 ^ N меньше или равно 12часы (* 3600 секунд, * 1000000 для микросекунд).Оттуда вы можете либо использовать логарифмы, чтобы найти правильное значение, либо оценить начальное значение N и выполнять итерации, пока не найдете значение.