Блог

Я пытался вычислить эту функцию, и я немного не уверен в своем результате. Я установил для него значение True. Кто-нибудь может объяснить, правильный ли мой ответ и почему?

 (3 log 2 n   55 log(n 10 )   8 log n) · log n = Ω(log 10 n)  
  

Я установил для него значение True

Ваш результат верен, но может быть дополнительно упрощен до Ω(log(n)) as log(10n) log(10) log(n) и log(10) является константой.
Чтобы доказать это f(n) = Ω(g(n)) , вам нужно показать, что g(n) это «нижняя граница» асимптотически для f(n) .
Формальное определение заключается в том, что f(n) = Ω(g(n)) существует ли некоторый c, n0 > 0 s.t. для всех n > n0 это так f(n) >= g(n) .
Напомним, что для каждого натурального целого числа, большего 2, выполняется это log(n) > 1 так
(3log(2n) 55log(10n) 8log n) · log n > 3log(2n) 55log(10n) 8log(n) > 8log(n) > log(n) .
Выбираем c = 1, n0 = 2 , и мы получаем это для всех n > n0 : (3log(2n) 55log(10n) 8log n) · log n > log(n) , таким образом (3log(2n) 55log(10n) 8log n) · log n = Ω(log(n) .