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

Question

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

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

Неужели мой инстинкт просто ошибается в этом?

Редактировать

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

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

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

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

Редактировать

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

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

Answer 1

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

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

Теперь рассмотрим 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), что явно больше, чем a * 2 ^(a +1) * log(2^(a+1)), и мы имеем противоречие.следовательно, f (n) не является функцией n log n.

Answer 2

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

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

---

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