Задача в книге Кормена "Алгоритмы. Построение и анализ"
объясните, пожалуйста, как решить эту задачку:
В книге вот такое определение:
Т.е. я должен доказать, что, например, в первом случае [lgn]! = O(n^k), правильно? Подскажите, с чего начать. Хочу разобраться.
Ответы (1 шт):
Функция Ceil(logn) (а у вас указаны именно такие скобки с округлением вверх) имеет ограничение Theta(logn), поскольку оно не превосходит значения logn+1, и (logn+1)/logn==>C (стремится к единице, константе). Для строгого доказательства таких моментов, думаю, будет много, но заниматься ими не хочется. Благодаря Theta будем использовать просто f(n)=(log(n))!
Нужно показать, как сравнивается f(n) ? O(n^k). Со степенной функцией сравнивать трудно, возьмем от обеих сторон логарифмы, и нужно показать сравнение log(f(n)) ? k*log(n)
По формуле Стирлинга log((log(n))!) = Theta(logn*loglogn). Сравниваем с логарифмом степенной функции
logn*loglogn ?? k*logn //делим на logn
loglogn ?? k
Но k - константа, а слева - бесконечно (хоть и медленно) растущая функция, её рост описывается как омега_малое(n). Таким образом,
logn*loglogn = w(n)*logn
и f(n)=(log(n))! === w(n) * Theta(n^k) > O(n^k), т.е. не является полиномиально ограниченной