Пример O (n!)?

Question

Что является примером (в коде) функции O(n!)? Для выполнения должно быть выполнено соответствующее количество операций со ссылкой n; то есть я спрашиваю о сложности времени.

Answer 1

Вот, пожалуйста. Вероятно, это самый тривиальный пример функции, которая выполняется за O(n!) время (где n - аргумент функции):

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

Answer 2

Одним из классических примеров является проблема коммивояжера через поиск методом перебора.

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

Answer 3

См. Заказы общих функций статьи Big O Wikipedia .

Согласно статье, решение задачи коммивояжера путем перебора и поиска определителя с разложением по минорам оба являются O (n!).

Answer 4

Есть проблемы, которые NP-complete (проверяется в недетерминированном полиномиальном времени).Это означает, что если входные данные масштабируются, то ваши вычисления, необходимые для решения проблемы, возрастают более чем значительно.

Некоторые NP-hard проблемы : проблема пути Гамильтона ( open img ), Задача коммивояжера ( open img )
Некоторые NP-complete проблемы : Булева проблема выполнимости (сб.) ( open img ), N-головоломка ( open img ), задача о рюкзаке ( open img ), проблема изоморфизма подграфа (open img ), проблема подмножества сумм ( open img ), проблема клики ( open img ), Vertexпроблема покрытия ( open img ), независимая проблема множества ( open img ), проблема доминирующего множества ( openimg ), Проблема раскраски графика ( open img ),

Источник: ссылка 1 , ссылка 2

Источник: ссылка

Answer 5

Поиск определителя с разложением по несовершеннолетним.

Очень хорошее объяснение здесь .

# include <cppad/cppad.hpp>
# include <cppad/speed/det_by_minor.hpp>

bool det_by_minor()
{   bool ok = true;

    // dimension of the matrix
    size_t n = 3;

    // construct the determinat object
    CppAD::det_by_minor<double> Det(n);

    double  a[] = {
        1., 2., 3.,  // a[0] a[1] a[2]
        3., 2., 1.,  // a[3] a[4] a[5]
        2., 1., 2.   // a[6] a[7] a[8]
    };
    CPPAD_TEST_VECTOR<double> A(9);
    size_t i;
    for(i = 0; i < 9; i++)
        A[i] = a[i];


    // evaluate the determinant
    double det = Det(A);

    double check;
    check = a[0]*(a[4]*a[8] - a[5]*a[7])
          - a[1]*(a[3]*a[8] - a[5]*a[6])
          + a[2]*(a[3]*a[7] - a[4]*a[6]);

    ok = det == check;

    return ok;
}

Код от здесь .Вы также найдете необходимые .hpp файлы там .

Answer 6

Я думаю, что немного опоздал, но нахожу snailsort лучшим примером O (n!) Детерминированного алгоритма. В основном он находит следующую перестановку массива, пока не отсортирует ее.

Это выглядит так:

template <class Iter> 
void snail_sort(Iter first, Iter last)
{
    while (next_permutation(first, last)) {}
}

Answer 7

Любой алгоритм, который вычисляет всю перестановку данного массива, равен O(N!).

Answer 8

самый простой пример:)

псевдокод:

input N
calculate N! and store the value in a vaiable NFac - this operation is o(N)
loop from 1 to NFac and output the letter 'z' - this is O(N!)

вот так :)

В качестве реального примера - как насчет генерации всех перестановок набора элементов?

Answer 9

printf("Hello World");

Да, это O (n!).Если вы считаете, что это не так, я предлагаю вам прочитать определение BigOh.

Я только добавил этот ответ из-за досадной привычки, что люди всегда должны использовать BigOh независимо от того, что они на самом деле означают.

Например, я почти уверен, что вопрос, который задают Theta (n!), По крайней мере, cn!шаги и не больше, чем Cn!шаги для некоторых констант c, C> 0, но вместо этого было выбрано O (n!).

Другой пример: Quicksort is O(n^2) in the worst case, хотя технически корректно (Even худшей сортировкой является O (n ^ 2) в худшем случаеслучай!), что они на самом деле означают Quicksort is Omega(n^2) in the worst case.

Answer 10

В Википедии

Решение проблемы коммивояжера с помощью перебора;поиск определителя с разложением по несовершеннолетним.

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions