Сравните сложности двух функций

Question

Я должен сравнить вышеупомянутые сложности для домашней задачи, но я не знаю, как сравнить вторую сложность с первой:

1. Θ(2^(log(n))!)

2. Θ(Σ(x^k - x^(k-1)) from k = 1 to k = n

Спасибо за ваше время.

Answer 1

Если мы предположим, что первым будет Θ (2 ^ log (n!)), Вы можете сказать:

• 2 ^ log (n!) = N!
• Σ (x ^ k - x ^ (k-1)) = 1 + x ^ n

Таким образом, вы можете сказать, что временная сложность первого предложения больше, чем второго (при условии x << n). Если x близко к n, то временная сложность второго предложения больше, чем первое. </p>

Однако, если первое предложение 2 ^ (log (n)) !, то вы можете использовать временную сложность гамма-функции . Или просто скажите, если m = 2 ^ (log (n))! затем log(m) = (log(n))!, а затем сравните log (m) с x ^ n. Если вы хотите сравнить логарифм двух функций:

• (журнал (п))!
• log (x ^ n) = nlogx

Предполагая, что log (n) = k, вы можете сказать, что n = 2 ^ k, и вы сравниваете эти два:

• к! = гамма (к + 1)
• 2 ^ k * log (x)

Первый имеет такой рост:

У второго такой рост:

оказывается, что первый больше.