В терминах Big-O, если O (n-1) - это то же самое, что и O (n), то почему в основной теореме T (n-1) не равно T (n)?

Итак, я новичок в CS и недавно узнал о Big-O, Theta и Omega, а также об основной теореме, и на лекции я увидел, что по какой-то причине это не так, и мне было интересно, почему это так?


recurrence math big-o master-theorem
person dawooshifingerhold    schedule 29.06.2020    source источник
comment
Вычисление O (независимо от того) может указать минимальное значение n, для которого выполняется ограничение производительности. Таким образом, нет проблемы предсказания невероятно малых времен для вырожденных случаев, таких как попытка выполнить сортировку NlgN, когда N равно 1 (но lgN равно нулю).   -  person supercat    schedule 29.06.2020
comment
Также Big-O касается предела поведения алгоритма, когда число приближается к бесконечности. Бесконечность = бесконечность -1 = бесконечность/2, поэтому O(n) = O(n-1) = O(n/2). это не имеет ничего общего с пределом, приближающимся к бесконечности, поэтому вы не можете использовать упрощения, которые допускает бесконечность.   -  person Jerry Jeremiah    schedule 29.06.2020
comment
О, в этом столько смысла. Спасибо!   -  person dawooshifingerhold    schedule 29.06.2020

Ответы (1)


arrow_upward
2
arrow_downward

Хотя и O(n), и T(n) используют заглавные буквы снаружи и строчную n в середине, они представляют собой принципиально разные концепции.

Если вы анализируете алгоритм с использованием рекуррентного соотношения, обычно T(n) обозначает количество времени, которое требуется алгоритму для завершения на входе размера n. В результате мы не ожидаем, что T(n) будет таким же, как T(n-1), поскольку в большинстве случаев алгоритмы выполняются дольше, когда вы даете им большие входные данные.

В более общем случае, для любой функции f, если вы хотите утверждать, что f(n) = f(n-1), вам нужно объяснить, почему вы могли это предположить, потому что обычно это не так. дело.

Хитрость здесь в том, что когда мы пишем O(n), это выглядит так, как будто мы пишем функцию с именем O и передаем аргумент n, но запись означает нечто совершенно другое. Обозначение O(n) является заполнителем для «некоторой функции, которая, когда входные данные становятся действительно большими, ограничена сверху числом, кратным n». Точно так же O(n-1) означает «некоторую функцию, которая, когда входные данные становятся действительно большими, ограничена сверху числом, кратным n-1». И бывает так, что любая функция, ограниченная сверху числом, кратным n, также ограничена сверху числом, кратным n-1, поэтому O(n) и O(n-1) обозначают одно и то же.

Надеюсь это поможет!

person templatetypedef    schedule 29.06.2020