Example O (n!)?

Question

What is an example (in code) of the O(n!) Function? An appropriate number of operations must be performed to refer to n ; that is, I ask about the complexity of time.

Answer 1

There you go. This is probably the most trivial example of a function that works in O(n!) Time (where n is the argument of the function):

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

Answer 2

One classic example is the traveling salesman problem through brute force search.

If there are cities N , the brute force method will check each permutation of these cities N to find which one is the cheapest. Now the number of permutations with cities N is N! making it difficult factorial ( O(N!) ).

Answer 3

See General Feature Orders in the Big O Wikipedia section.

In accordance with this article, the solution to the traveling salesman problem by searching for brute force and finding determinant with expansion by minors is O (n!).

Answer 4

There are problems that are NP-complete (checked in non-deterministic polynomial time). Meaning, if the input scales, then your calculations necessary to solve the problem increase more than a lot.

Some NP-hard problems : Hamilton path problem ( open img ), Seller problem ( open img )
Some NP-complete problems : Boolean feasibility problem (Sat.) ( open img ), N-puzzle ( open img ), Backpack problem ( open img ), Subgraph isomorphism problem ( open img ), Subset sum problem ( open img ), Click problem ( open img ), Problem with vertex cover ( open img ), Independent installation problem ( open img ), Dominant set problem ( open img ), Graph coloring problem ( open img ),

Source: link 1 , link 2

Source: Link

Answer 5

Finding a determinant with decomposition into minors.

Very good explanation here .

 # 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; } 

The code is here . You will also find the necessary .hpp files there .

Answer 6

I think I'm a little late, but I think snailsort is the best example of the deterministic O (n!) Algorithm. It basically finds the next permutation of the array until it sorts it.

It looks like this:

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

Answer 7

Any algorithm that computes the entire permutation of a given array is O(N!) .

Answer 8

simplest example :)

pseudo code:

 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!) 

there you go :)

As a real example - how about generating all permutations of a set of elements?

Answer 9

printf("Hello World");

Yes, this is O (n!). If you think this is not the case, I suggest you read the definition of BigOh.

I just added this answer because of an annoying habit, people should always use BigOh no matter what they really mean.

For example, I am sure that the question asked by Theta (n!) Is at least cn! steps and no more than Cn! steps for some constants c, C> 0, but instead prefers to use O (n!).

Another instance: Quicksort is O(n^2) in the worst case , although technically correct (even in the worst case, the descriptor is O (n ^ 2)!) That they actually mean Quicksort is Omega(n^2) in the worst case .

Answer 10

On Wikipedia

Solving the traveling salesman problem by searching for brute force; finding a determinant with decomposition into minors.

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

Answer 11

In c #

Will it be O (N!) In cosmic complexity? because a string in C # is immutable.

 string reverseString(string orgString) { string reversedString = String.Empty; for (int i = 0; i < orgString.Length; i++) { reversedString += orgString[i]; } return reversedString; } 

Answer 12

You are right, recursive calls must take exactly n! time. there is code similar to checking factorial time for n different values. The inner loop works for n! time for different values ​​of j, so the complexity of the inner loop is 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; } } 

Here is the test result for n = 5, it accurately performs factorial time.

  N Fn N! 1 1 1 2 2 2 3 6 6 4 24 24 5 120 120 

Exact function with time complexity 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); } 

Answer 13

Bogosort is the only "official" I've come across that deals with O (n!). But this is not guaranteed to be O (n!), Since it is random in nature.

Answer 14

The recursive method that you probably learned to take the determinant of the matrix (if you took linear algebra) takes O (n!) Time. Although I especially do not want to code everything.

Answer 15

@clocksmith You are absolutely right. This is not a calculation of n !. And this is not O (n!). I ran it, collecting the data in the table below. Please compare columns 2 and 3. (#nF is the number of calls to 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 

So it is clear if it performs much worse than O (n!). Below is an example code to calculate n! recursively. You will notice that its order is O (n).

 int Factorial(int n) { if (n == 1) return 1; else return n * Factorial(n-1); } 

Answer 16

Add to function to

This is a simple example of a function with complexity O (n!) That has an int array in the parameter and an integer k. it returns true if there are two elements from the array x + y = k, for example: if tab was [1, 2, 3, 4] and k = 6, the return value will be true, because 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; } 

As a bonus, this is a unit test with jUnit, works great

 @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); } 

Answer 17

The simplest example of this is the factorial function:

 function factorial(n){ let fact=1; for(var i=1; i<=n;i++){ fact=fact*i; } return fact; } 

On!)