Алгоритмы с факторным временем и P/NP

1. Нет, факториальное время не является полиномиальным временем. Полиномиальное время обычно означает уравнение формы O(N^k), где N = количество обрабатываемых элементов, а k = некоторая константа. Важная часть заключается в том, что показатель степени является константой — вы умножаете N само на некоторое число, которое является фиксированным — не зависящим от самого N. Алгоритм факторной сложности означает, что число умножений не фиксировано — само число умножений растет с увеличением N.

2. У тебя похоже такая же проблема. N² будет полиномиальной сложностью. 2^N не будет. Ваше основное правило также ошибочно: алгоритм факторной сложности не означает, что «у нас есть достаточно быстрый алгоритм», по крайней мере, как общее правило. Во всяком случае, вывод скорее противоположный: факторный алгоритм может быть практичным в нескольких особых случаях (например, когда N чрезвычайно мало), но становится непрактичным очень по мере роста N.

Попробуем представить это в перспективе. Бинарный поиск — это O(log N). Линейный поиск — O(N). При сортировке «медленные» алгоритмы — это O(N²), а «продвинутые» — O(N lg N). Факторная сложность равна (достаточно очевидно) O(N!).

Давайте попробуем подсчитать это, учитывая (на данный момент) только 10 пунктов. Каждый из них будет примерно во сколько раз дольше будет обрабатываться 10 элементов вместо 1 элемента:

O(log N): 2
O(N):10
O(N log N): 23
O(N²): 100
O(N !): 3 628 800

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

Как видите, скорость роста для алгоритма факторной сложности намного выше, чем для любого другого. Если мы расширим его до 20 элементов, разница станет еще более существенной:

O(log N): 3
O(n): 20
O(N log N): 60
O(N²): 400
O(N !): 2 432 902 008 176 640 000

Скорость роста для N! настолько быстры, что почти наверняка будут непрактичными, за исключением тех случаев, когда количество задействованных элементов известно, что они довольно малы. Для грима предположим, что каждая базовая операция для описанных выше процессов может выполняться за один машинный такт. Просто ради аргумента (и для простоты вычислений) давайте предположим, что у нас процессор с тактовой частотой 10 ГГц. Итак, в основе лежит то, что обработка одного элемента занимает 0,1 нс. В этом случае с 20 элементами:

O(log N) = 0,3 нс
O(N) = 2 нс
O(N log N) = 6 нс
O(N²) = 40 нс< br> O(N!) = 7,7 лет.

Довольно легко увидеть, что факториал (приблизительно) экспоненциален в поведении.

Его можно (очень грубо) представить как nⁿ (точнее, sqrt(2n)(n/e)ⁿ).

Поэтому, если вы нашли какое-либо конкретное M, где, по вашему мнению, Mⁿ является хорошим приближением, вы (вероятно) ошибаетесь. 269! больше 100ⁿ и как n! будет умножаться на числа больше 100, она будет продолжать расти быстрее.