#big-o
#big-o
Вопрос:
Докажите или опровергните следующие утверждения:
- Существующая функция
f(n)
sof(n-k)
не равнаBig-theta (f(n))
. когдаk>=1
и является положительной константой.
Существует ли какая-либо функция, для которой это утверждение верно? Я думал об f(n)=n!
, но я не уверен, что это правильный ответ. Более того, если f(n)=n!
верно, то как это утверждение может быть доказано?
- Существуют функции so
(f(n))^2=Big-O(f(n))
иf(n)=Big-omega (log(log(n)))
.
Я думаю, что нет функции, которая делает утверждение истинным. Если это правильно — как это можно доказать?
Ответ №1:
-
Исправьте для f (n) = n!. Достаточно показать, что для любого фиксированного k >= 1, (n — k)! не является Omega (n!), как и для любой константы c > 0, она выполняется для всех n, достаточно больших, чтобы c * n! > (n — k)!.
-
Не существует f (n) такого, чтобы оба f (n) ^ 2 = O (f (n)) и f (n) = Omega (log log n). Последнее подразумевает, что для некоторой константы c > 0 и всех n достаточно больших значений f (n) > c log log n и, в частности, f (n) > 1 для всех n достаточно больших значений. Если мы теперь предположим, что f (n) ^ 2 = O (f (n)), то существует константа r > 0, так что для всех n достаточно больших f (n) ^ 2 < r * f (n), а именно f (n) < r . Но это подразумевает, что log log n < (r / c) для всех n достаточно больших, что неверно для всех n > e ^ (e ^ (r / c)) (где e является основой log).
Комментарии:
1. Что касается первого вопроса, есть ли у вас еще один пример функции, которая подтверждает утверждение об истинности?