Является ли O (n Log n) полиномиальным временем?

Ответ 1

Да, O (nlogn) - это полиномиальное время.

Из http://mathworld.wolfram.com/PolynomialTime.html:

Алгоритм называется разрешимым в полиномиальное время, если число шагов, необходимых для завершения алгоритма для данного входа, является O (n ^ m) для некоторого неотрицательного целого m, где n - сложность вход.

Из http://en.wikipedia.org/wiki/Big_O_notation:

f есть O (g), если f

Теперь я докажу, что n log n равно O (n ^ m) для некоторого m, что означает, что n log n является полиномиальным временем.

Действительно, возьмем m = 2. (это означает, что я докажу, что n log n есть O (n ^ 2))

Для доказательства возьмем k = 2. (Это может быть меньше, но это не обязательно.) Существует такое n_0, что для всех больших n выполнено.

n_0 * f (n) <= g (n) * k

Возьмем n_0 = 1 (этого достаточно) Теперь легко видеть, что

n log n <= 2n * n

log n <= 2n

n > 0 (предположение)

Нажмите здесь, если вы не уверены в этом.

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

Ответ 2

Это, по крайней мере, не хуже полиномиального времени. И все же не лучше: n < n log n < п * п.

Ответ 3

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

EDIT: со страницы wikipedia: "Говорят, что алгоритм имеет полиномиальное время, если его время выполнения ограничено сверху полиномиальным выражением в размере ввода для алгоритма".

Ответ 4

Да. Какой предел nlogn при n идет в бесконечность? Интуитивно, для больших n, n → logn, и вы можете рассматривать продукт, в котором доминируют n, и поэтому nlogn ~ n, что является явно полиномиальным временем. Более строгим доказательством является использование теоремы Сэндвича, которую сделал Вдохновленный:

n ^ 1 < nlogn < п ^ 2.

Следовательно, nlogn ограничена сверху (и ниже) последовательностью, которая является полиномиальным временем.