Big O доказательство с sqrt и журналом

Question

Мне трудно понять, как доказать, что

t(n) = sqrt(31n + 12n log n + 57)

- это

O(sqrt(n) log n)

Мне еще не приходилось иметь дело с квадратным корнем в большой записи O, поэтомус этим много проблем!Любая помощь с благодарностью:)

Answer 1

Big O нотация о том, как характеристики алгоритма (время, использованное в памяти, использование памяти, время обработки) растут с ростом проблемы.

Постоянные факторы отбрасываются, потому что они не влияют на как значение масштабируется.

Незначительные термины также отбрасываются, потому что в итоге они почти не действуют.

Итак, ваше исходное уравнение

sqrt(31n + 12nlogn + 57)

сразу упрощается до

sqrt(n log n)

Квадратные корни распределяются, как и другие виды умножения и деления, так что это может быть легко преобразовано в:

sqrt(n) sqrt(log n)

Поскольку журналы преобразуют умножение в сложение (вот почему работают правила слайдов), это становится:

sqrt(n) log (n/2)

Опять же, мы отбрасываем константы, потому что нас интересует класс поведения

sqrt(n) log n

И у нас есть ответ.

Обновление

Как правильно было указано,

sqrt(n) sqrt(log n)

не становится

sqrt(n) log (n/2)

Так что конец моего происхождения неверен.

Answer 2

Подсказка: рассмотрим основные условия разложения sqrt (1 + x) для | x |<1. </p>

Answer 3

Начните с поиска коэффициента наибольшей степени внутри sqrt(), который будет 12nlogn. Коэффициент наибольшей степени делает все остальные факторы несущественными в терминах больших О, поэтому он становится равным O(sqrt(12nlogn)). Постоянный фактор также не имеет значения, поэтому он становится O(sqrt(nlogn)). Тогда я полагаю, что вы можете установить аргумент, равный O(sqrt(n) * sqrt(logn)) или O(sqrt(n) * log(n)^(1/2)), и исключить возможность включения logn, чтобы получить O(sqrt(n)logn). Но я не знаю, каким будет техническое обоснование для этого последнего шага, потому что, если вы можете превратить sqrt(logn) в logn, почему вы не можете превратить sqrt(n) в n?