как заказать следующие данные в асимптотическом порядке? - PullRequest
Новая
       90

как заказать следующие данные в асимптотическом порядке?

1 голос
/ 27 октября 2019

Эй, ребята, пожалуйста, помогите мне здесь, я не могу понять, как это сделать, и у меня есть представление в ближайшее время 

a1(n)=5,
a2(n)=2^nlogn,  
a3(n)=n^100
a4(n)=n^n
a5(n)=n!
a6(n)=(0.5)^log(base2)n

1 Ответ

0 голосов
/ 27 октября 2019
  • a6 (n) = (0,5) ^ log (основание 2) n уменьшается к 0 для увеличения n;следовательно, это O (1), так как оно в конечном итоге меньше любой положительной константы. должна быть возможность получить более жесткую границу, но это не было бы полезно в контексте анализа алгоритмов.
  • a1 (n) = 5 - постоянная функция, следовательно, O (1).
  • a3 (n) = n ^ 100 является полиномиальной функцией и асимптотически больше, чем функции O (1), описанные выше. Полиномиальные функции асимптотически меньше приведенных ниже экспоненциальных и факториальных функций.
  • если a2 (n) = (2 ^ n) logn, то это меньше, чем у двух других. Чтобы увидеть это, попробуйте n = 1000 и обратите внимание, сколько других факторов больше в двух других.
  • a5 (n) = n! Асимптотически меньше, чем n ^ n, так как оба имеют одинаковое количество членов, но коэффициенты n ^ n больше почти в каждом случае.
  • a4 (n) = n ^ n - самое большое. Если a2 (n) = 2 ^ (nlogn), то a2 (n) = a4 (n) = n ^ n с помощью алгебраических манипуляций.
...