Рубрики

Алгоритмы | Анализ алгоритмов | Вопрос 19

Какой из приведенных вариантов обеспечивает возрастающий порядок асимптотической сложности функций f1, f2, f3 и f4?

  f1(n) = 2^n
  f2(n) = n^(3/2)
  f3(n) = nLogn
  f4(n) = n^(Logn)

(А) f3, f2, f4, f1
(B) f3, f2, f1, f4
(С) f2, f3, f1, f4
(D) f2, f3, f4, f1

Ответ: (А)
Объяснение:

  f1(n) = 2^n
  f2(n) = n^(3/2)
  f3(n) = nLogn
  f4(n) = n^(Logn)

За исключением f3, все остальные экспоненциальные. Таким образом, f3 определенно первым в выходе. Среди оставшихся n ^ (3/2) следующий.

Один из способов сравнить f1 и f4 — взять журнал обеих функций. Порядок роста Log (f1 (n)) равен Θ (n), а порядок роста Log (f4 (n)) равен Θ (Logn * Logn). Поскольку Θ (n) имеет больший рост, чем Θ (Logn * Logn), f1 (n) растет быстрее, чем f4 (n).

Ниже приведен еще один способ сравнить f1 и f4.

Давайте сравним f4 и f1. Давайте возьмем несколько значений для сравнения

n = 32, f1 = 2^32, f4 = 32^5 = 2^25
n = 64, f1 = 2^64, f4 = 64^6 = 2^36
...............
............... 

Также см. Http://www.wolframalpha.com/input/?i=2^n+vs+n^%28log+n%29.

Спасибо fella26 за предложенное выше объяснение.

Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Анализ алгоритмов | Вопрос 19

0.00 (0%) 0 votes