Почему мы не можем просто выбрать самый большой термин с обозначением big-O?

Question

Я смотрю на страницу Cracking the Coding Interview 6th edition, пример 8.

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

Если длина самой длинной строки равна s, а длина массива равна a, книга говорит, что сортировка каждой строки будет такой:

O(a*s log s)

Я понимаю, что сложность зависит от верхней границы в этом случае, поэтому она должна быть:

O(s log s)

Например, если s - длина самой длинной строки и s1, s2, s3 - это длины других строк, сложность будет:

O(s log s + s1 log s1 + s2 log s2 + s3 log s3)

, что в конечном итоге:

O(s log s)

, поскольку значение s является самым высоким.Зачем нам умножать, если с a?

Answer 1

Как указывает Дюкелинг, здесь указаны параметры a и s.

Таким образом, время выполнения вашего алгоритма зависит от обоих.Без дополнительной информации об отношениях между ними вы не сможете упростить дальнейшее.Например, это не похоже на то, что вам дали a < s.

Но скажите, что вам дали a < s.Тогда вы могли бы сказать, что, поскольку ваша O(s log s) операция сортировки должна выполняться a = O(s) раз, чтобы отсортировать все строки в вашем массиве, итоговое значение составляет O(s^2 log s).

Answer 2

Вы можете игнорировать меньшие термины только при их постоянном количестве.

Возможность игнорировать меньшие термины фактически вытекает из того факта, что вы можете игнорировать постоянные факторы, но это работает только тогда, когда у вас естьпостоянное количество меньших членов (иначе постоянный коэффициент не будет постоянным).

Интуитивно:

Что если у вас 50000000000 строк длиной 10?Какой-то предопределенный коэффициент 10 log 10 не подходит для времени выполнения, вам нужно где-то 50000000000.

Математически:

Допустим, у вас есть f(n) + g(n), где g(n) меньше f(n), поскольку n стремится к бесконечности.

Вы можете сказать, что:

f(n) <= f(n) + g(n) <= f(n) + f(n) = 2.f(n)    (as n tends to infinity)

Теперь вы отменили g(n)и существует только постоянный коэффициент между 1 и 2 для f(n), который можно игнорировать с помощью асимптотической записи, поэтому сложность просто равна O(f(n)).

Если у вас есть переменное число a условий, у вас будет a.f(n), и вы не можете игнорировать это a.

Доказательство a.f(n) = O(f(n)) (по крайней мере, один способ доказать это) включает в себя выбор константы M такое, что |a.f(n)| <= M.f(n) от некоторого значения n и далее.Независимо от того, какое значение M вы выберете, всегда может существовать большее значение a (просто M+1 будет работать), поэтому это доказательство не сработает.