Что является примером (в коде) функции O(n!)? Должно быть выполнено соответствующее количество операций для ссылки на n; то есть я спрашиваю о сложности времени.
Пример O (n!)?
Ответ 1
Там вы идете. Это, вероятно, самый тривиальный пример функции, которая работает в O(n!) времени (где n - аргумент функции):
void nFacRuntimeFunc(int n) {
for(int i=0; i<n; i++) {
nFacRuntimeFunc(n-1);
}
}
Ответ 2
Один классический пример проблема коммивояжера посредством поиска грубой силы.
Если есть города N, метод грубой силы будет проверять каждую перестановку этих городов N, чтобы найти, какая из них самая дешевая. Теперь число перестановок с городами N составляет N!, что делает его сложным factorial (O(N!)).
Ответ 3
См. раздел Заказы общих функций в разделе Big O Wikipedia.
В соответствии с этой статьей, решение проблемы коммивояжера путем поиска грубой силы и нахождения determinant с расширение минорами - это O (n!).
Ответ 4
Есть проблемы, которые NP-complete (проверяемые в недетерминированном полиномиальном времени). Значение, если входные шкалы, то ваши вычисления, необходимые для решения проблемы, возрастают больше, чем много.
Некоторые проблемы NP-hard: Гамильтонова проблема пути (открыть img), Проблема продавцов (открыть img)
Некоторые проблемы NP-complete: Булева проблема выполнимости (Sat.) (открыть img), N-puzzle (открыть img), Проблема с рюкзаком (открыть img), Проблема изоморфизма подграфов (open img), Проблема суммы подмножества (открыть img), Проблема клики (открыть img), Проблема с крышкой вершины (открыть img), Независимая проблема установки (открыть img), Проблема с доминирующим набором (открыть img), Проблема с раскраской графа (открыть img),
Источник: ссылка
Ответ 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;
}
Ответ 6
Я думаю, что немного опоздал, но я считаю snailsort лучшим примером детерминированного алгоритма O (n!). Он в основном находит следующую перестановку массива, пока он не сортирует его.
Он выглядит следующим образом:
template <class Iter>
void snail_sort(Iter first, Iter last)
{
while (next_permutation(first, last)) {}
}
Ответ 7
Любой алгоритм, который вычисляет всю перестановку данного массива, является O(N!).
Ответ 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!)
там вы идете:)
Как реальный пример - как насчет генерации всех перестановок набора элементов?
Ответ 9
printf("Hello World");
Да, это O (n!). Если вы считаете, что это не так, я предлагаю вам прочитать определение BigOh.
Я только добавил этот ответ из-за раздражающей привычки люди всегда должны использовать BigOh независимо от того, что они на самом деле означают.
Например, я уверен, что вопрос, заданный Тета (n!), по крайней мере, cn! шагов и не более, чем Cn! шаги для некоторых констант c, C > 0, но вместо этого предпочтет использовать O (n!).
Другой экземпляр: Quicksort is O(n^2) in the worst case, хотя технически корректен (даже в самом худшем случае в качестве дескриптора есть O (n ^ 2)!), что они на самом деле означают Quicksort is Omega(n^2) in the worst case.
Ответ 10
В Википедии
Решение проблемы коммивояжера путем поиска грубой силы; нахождение определителя с разложением на миноры.
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
Ответ 11
В С#
Не будет ли это O (N!) в космической сложности? потому что строка в С# является неизменной.
string reverseString(string orgString) {
string reversedString = String.Empty;
for (int i = 0; i < orgString.Length; i++) {
reversedString += orgString[i];
}
return reversedString;
}
Ответ 12
Вы правы, рекурсивные вызовы должны принимать ровно n! время. здесь есть код, похожий на проверку факториального времени для n разных значений. Внутренний цикл работает для n! время для разных значений j, поэтому сложность внутреннего цикла - Big O (n!)
public static void NFactorialRuntime(int n)
{
Console.WriteLine(" N Fn N!");
for (int i = 1; i <= n; i++) // This loop is just to test n different values
{
int f = Fact(i);
for (int j = 1; j <= f; j++) // This is Factorial times
{ ++x; }
Console.WriteLine(" {0} {1} {2}", i, x, f);
x = 0;
}
}
Вот результат теста для n = 5, он точно выполняет факториальное время.
N Fn N!
1 1 1
2 2 2
3 6 6
4 24 24
5 120 120
Точная функция с временной сложностью n!
// Big O(n!)
public static void NFactorialRuntime(int n)
{
for (int j = 1; j <= Fact(i); j++) { ++x; }
Console.WriteLine(" {0} {1} {2}", i, x, f);
}
Ответ 13
Bogosort является единственным "официальным", с которым я столкнулся, который занимается в области O (n!). Но это не гарантировано O (n!), Поскольку оно является случайным по своей природе.
Ответ 14
Рекурсивный метод, который вы, вероятно, узнали для принятия определителя матрицы (если вы взяли линейную алгебру), принимает время O (n!). Хотя мне особенно не хочется кодировать все.
Ответ 15
@clocksmith Вы абсолютно правы. Это не вычисление n!. И это не O (n!). Я запустил его, собрав данные в таблице ниже. Пожалуйста, сравните столбцы 2 и 3. (#nF - количество вызовов nFacRuntimeFunc)
n #nF n!
0 0 1
1 1 1
2 4 2
3 15 6
4 65 24
5 325 120
6 1956 720
7 13699 5040
Так ясно, если выполняется намного хуже, чем O (n!). Ниже приведен пример кода для вычисления n! рекурсивно. вы заметите, что его порядок O (n).
int Factorial(int n)
{
if (n == 1)
return 1;
else
return n * Factorial(n-1);
}
Ответ 16
Добавить до функции к
Это простой пример функции со сложностью O (n!), Имеющей массив int в параметре и целое число k. он возвращает true, если есть два элемента из массива x + y = k, например: если tab был [1, 2, 3, 4] и k = 6, возвращаемое значение будет true, потому что 2 + 4 = 6
public boolean addToUpK(int[] tab, int k) {
boolean response = false;
for(int i=0; i<tab.length; i++) {
for(int j=i+1; j<tab.length; j++) {
if(tab[i]+tab[j]==k) {
return true;
}
}
}
return response;
}
В качестве бонуса это юнит-тест с jUnit, отлично работает
@Test
public void testAddToUpK() {
DailyCodingProblem daProblem = new DailyCodingProblemImpl();
int tab[] = {10, 15, 3, 7};
int k = 17;
boolean result = true; //expected result because 10+7=17
assertTrue("expected value is true", daProblem.addToUpK(tab, k) == result);
k = 50;
result = false; //expected value because there any two numbers from the list add up to 50
assertTrue("expected value is false", daProblem.addToUpK(tab, k) == result);
}
Ответ 17
Простейшим примером этого является функция факториала:
function factorial(n){
let fact=1;
for(var i=1; i<=n;i++){
fact=fact*i;
}
return fact;
}
На!)