Проблема сложности времени между двумя разными машинами

Question

Я застрял в проблеме ниже.

У конкретного алгоритма временная сложность T (n) = 3T (n-1) + 1.

Итак, в асимптотических терминахВышеупомянутый алгоритм имеет временную сложность O (3 ^ n).

То, что выполнение алгоритма на конкретной машине X требует t секунд для n входов.

Вопрос в том, чтоПредположим, что есть машина Y, которая в 27 раз быстрее, чем машина X, сколько входов Y может обработать за ту же секунду ...?

Я могу решить эту проблему в своей голове неоднозначно ... но больше не могу объяснить.

Есть ли простой способ решения этой проблемы?

Answer 1

Короткий ответ : быстрая машина обработает n + 3 элементов.

Поскольку сложность по времени составляет O (3 ^{n *)1009 *)} .Это означает, что если мы увеличим n на единицу, это займет примерно в три раза больше времени.Если мы увеличим n на два, то это займет в девять раз больше времени, и мы добавим три к n , тогда объем работы будет в 27 раз больше.

Таким образом, машина, которая в 27 раз быстрее, сможет обрабатывать на три элемента больше, чем медленная машина.Это, конечно, имеет место только при асимптотических условиях: так что если n уже велико.Для малых n другие члены в уравнении могут иметь большее влияние.

Более строго мы можем видеть это следующим образом: более быстрая машина может выполнять в 27 раз больше работы медленной машины.в то же время.

Это означает, что:

T (f (n)) = 27 × T (n)

Где f (n) - это функция, которую мы хотим найти.Асимптотически T (n) масштабируется с O (3 ⁿ ) , что означает, что мы имеем в качестве уравнения:

3 ^{f (n)} = 27 × 3 ⁿ

и, таким образом, имеет значение:

f (n) = log ₃ (27 × 3 ⁿ )

и, следовательно:

f (n) =n + log ₃ (27)

, поскольку log ₃ (27) равно 3 , это означает, что:

f (n) = n + 3