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

Question

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

Answer 1

Вы правы, рекурсивные вызовы должны занимать ровно 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!

// 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 2

In C #

Разве это не было бы O (N!) В сложности пространства? потому что строка в C # неизменна.

string reverseString(string orgString) {
    string reversedString = String.Empty;

    for (int i = 0; i < orgString.Length; i++) {
        reversedString += orgString[i];
    }

    return reversedString;
}

Answer 3

Простейшим примером этого является факториальная функция:

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

O (n!)

Answer 4

Добавить до функции k

Это простой пример функции со сложностью 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's any two numbers from the list add up to 50
        assertTrue("expected value is false", daProblem.addToUpK(tab, k) == result);
    }

Answer 5

@ clocksmith Вы абсолютно правы.Это не расчет n!И при этом это не O (n!).Я запустил собранные данные в таблице ниже.Пожалуйста, сравните колонку 2 и три.(#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);
}

Answer 6

Рекурсивный метод, который вы, вероятно, изучили для определения определителя матрицы (если вы взяли линейную алгебру), занимает O (n!) Времени.Хотя мне не особо хочется все это кодировать.

Answer 7

Bogosort - единственный "официальный", с которым я столкнулся, который входит в область O (n!) Но это не гарантированный O (n!), Поскольку он случайный по своей природе.