Асимптотическая запись - упрощает ли n (log n) (log n)?

Question

Если у меня есть алгоритм, который принимает n log n шагов (например, heapsort), где шаги занимают log n времени (например, сравнение / обмен "больших" целых чисел в диапазоне от 0 до n-1), что такое асимптотика на весь процесс.

Очевидно, что мы можем сказать «n (log n) (log n)», но я с трудом пытаюсь убедить себя, что не могу упростить это до «n log n». В то же время мне трудно оправдать инстинкт, который настаивает на том, что я могу.

Мой инстинкт просто неправ в этом?

EDIT

Кажется, мой простой пример, который нужно избегать, усложнил проблему. Ну хорошо.

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

Тем не менее, люди будут утверждать, что существует n состояний и m переходов, но n и m имеют тенденцию быть линейно связанными для автоматов, предполагая, что число аннотаций переходов является постоянным и что автоматы являются более или менее детерминированными.

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

EDIT

Я также все больше убеждаюсь, что «n (log n) (log n)» неверно.

Если a - это O (b log b), где b - это O (log c), что такое a в терминах c?

Answer 1

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

В конкретном приложении, скорее всего, большие целые числа следуют некоторому определенному распределению. Например, может быть известно, что все они ниже 10 ^ 20. Если это так, операции сравнения занимают постоянное время (определяется верхней границей 10 ^ 20). Тогда log M также является постоянной величиной, а вся сложность заключается в O (N log N).

Answer 2

Вот доказательство от противного:

Допустим, что функция f (n) = n (log n) (log n). Предположим, что мы думаем, что это тоже тэта (n log n), иными словами, существует a, для которого f (n) <= a * n log n выполняется для больших n. </p>

Теперь рассмотрим f (2 ^ (a + 1)):

f (2 ^ (a + 1)) = 2 ^ (a + 1) * log (2 ^ (a + 1)) * log (2 ^ (a + 1)) = 2 ^ (a + 1 ) * log (2 ^ (a + 1)) * (a + 1), который явно больше, чем * 2 ^ (a + 1) * log (2 ^ (a + 1)), и мы имеем противоречие , следовательно, f (n) не является функцией n log n.

Answer 3

Вы не сможете уменьшить n (log n) (log n) до n (log n) просто потому, что это не уменьшение на постоянный коэффициент.

Что не так с n (log n)2?

Answer 4

Хорошо, общая мера сложности программы следующая:

Сложность O (f (n)) означает, что существует c, так что число соответствующих шагов машины Тьюринга до его завершения не превышает c * f (n), где n - длина вход.

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

Но если бы мы программировали машины Тьюринга напрямую, ваш вопрос не возник бы. В реальном мире мы предпочитаем абстрагироваться. Хотя мы по-прежнему вычисляем «шаги», необходимые для запуска программы, мы предполагаем, что определенные операции занимают один шаг . Мы предполагаем, что по разным причинам:

• Это может напоминать фактическую работу ЦП, где каждое 32-разрядное целочисленное сложение действительно является одним шагом (и существуют алгоритмы, которые фактически злоупотребляют этим, например, «доминанты бит-веректоров»).
• Мы сравниваем различные алгоритмы в одной и той же области (например, сравниваем сортировки массивов путем измерения количества сравнений).

В этом случае (ваше первое РЕДАКТИРОВАНИЕ), если вы хотите конкретизировать свою меру сложности, вам нужно просто умножить функции под O. Если то, что вы думали сделать один шаг, теперь считается выполненным за O (log N), то количество конкретизированных шагов увеличивается в O раз (log N). Следовательно, общая сложность составляет O (N log N log N).

---

Что касается вашего второго РЕДАКТИРОВАНИЯ, это другая ситуация. Пусть ваш алгоритм будет сложностью O (n log N). Но вы знаете, что входные данные состоят из M чисел, каждое из log K цифр, поэтому `N = O (M log K) (нам нужны учетные разделители и т. Д.). Тогда математически правильно написать общую сложность как O (M * log K * (log M + log log K)), поэтому здесь нет никаких проблем. Но обычно мы абстрагируем ненужные детали, чтобы найти общую основу для сравнения различных алгоритмов.