Сложность времени N Queen, использующая backtracking?

#include<stdio.h>
#include<math.h>

void printboard(int n);
void fourQueen(int k,int n);
int place(int k,int i);
int x[100];

void NQueen(int k,int n)
{
  int i;
  for(i=1;i<=n;i++)
  {
    if(place(k,i)==1)
    {     x[k]=i;
            if(k==n)
            {
                printf("Solution\n");
                printboard(n);
            }
            else
                NQueen(k+1,n);
    }
  }
}

int place(int k,int i)
{
  int j;
  for(j=1;j<k;j++)
  {
    if((x[j]==i)||abs(x[j]-i)==abs(j-k))
        return 0;
  }
  return 1;
}

void printboard(int n)
{
  int i;
  for(i=1;i<=n;i++)
    printf("%d  ",x[i]);
}

void main()
{
    int n;
    printf("Enter Value of N:");
    scanf("%d",&n);
    NQueen(1,n);
}

Я думаю, что у него есть временная сложность: O (n ^ n), поскольку функция NQueen рекурсивно вызывается, но существует ли какая-либо более жесткая граница для этой программы? как насчет лучшего случая, и худшей временной сложности. Я также путаюсь о функции place(), которая является O (k) и вызывает из NQueen().

Ответ 1

Существует много оптимизаций, чем может улучшить временную сложность алгоритма.

В этих ссылках есть дополнительная информация:

Ответ 2

Для вашей функции T(n) = n*T(n-1) + O(n^2), которая в среднем соответствует временной сложности O(N!).

Ответ 3

ВРЕМЕННАЯ КОМПЛЕКСНОСТЬ ПРОБЛЕМЫ N-QUEEN IS

O (N!)

Объяснение: Если мы добавим все это и определим время выполнения как T (N). Тогда T (N) = O (N2) + N * T (N-1). Если вы нарисуете дерево рекурсии с использованием этого повторения, конечный член будет чем-то вроде n3 + n! O (1). По определению Big O это можно свести к времени выполнения O (n!).

Ответ 4

Сложность n ^ n, и вот объяснение

Здесь n представляет число ферзей и останется таким же для каждого вызова функции. K - номер строки, и функция будет называться временами до тех пор, пока k не достигнет n. Если n = 8, у нас есть n строк и n королев.

T (n) = n (n + t (max k - 1)) = n ^ max k = n ^ n, поскольку max k равен n.

Примечание. Функция имеет два параметра. В цикле n не уменьшается. Для каждого вызова функции он остается таким же. Но для количества раз, когда функция вызывается, она уменьшается, так что рекурсия может завершиться.

Ответ 5

O (n ^ n) определенно является верхней границей при решении n-ферзей с использованием обратного отслеживания. Я предполагаю, что вы решаете это, назначая королеву по столбцам. Однако учтите это: когда вы назначаете местоположение королевы в первом столбце, у вас есть n опций, после этого у вас есть только n-1 опций, так как вы не можете поместить королеву в той же строке, что и первая королева, потом н-2 и тд. Таким образом, сложность в худшем случае все еще ограничена сверху O (n!).

Надеюсь, что это отвечает на ваш вопрос, хотя я почти на 4 года опоздал!

Ответ 6

Давайте рассмотрим, что наша королева - ладья, то есть нам не нужно заботиться о диагональных конфликтах.

Сложность времени в этом случае будет O(N!) В худшем случае, если мы собираемся проверить, существует ли какое-либо решение или нет. Вот простое объяснение.

Давайте возьмем пример, где N = 4.

Предположим, мы хотим заполнить 2-D матрицу. X представляет вакантную позицию, а 1 представляет занятую позицию.

В начале матрица ответов (которую нам нужно заполнить) выглядит так:

X X X X
X X X X
X X X X
X X X X

Давайте заполним этот ряд, то есть выберем одно место в каждом ряду, а затем перейдем к следующему ряду.

Для первой строки, поскольку ни одна не заполнена в матрице в целом, у нас есть 4 options. Для второго ряда у нас есть 3 options как один ряд уже снят. Аналогично, для третьего ряда у нас есть 2 options а для последнего ряда у нас остался только 1 option.

Всего опций = 4*3*2*1 = 24 (4!)

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

Ответ 7

Да, есть более жесткая привязка, но сначала вам может понадобиться немного изменить код:
вместо того, чтобы пробовать каждую строку каждого двоеточия, вы можете уменьшить общее количество рекурсии, просто перебирая все возможные перестановки чисел из 1- > n, почему? посмотрите на возможное решение:

8queens = [3,6,2,7,1,4,0,5] nqueens = [a1,a2,a3.....an]

это целочисленный массив, где индекс i этого массива указывает номер двоеточия, а queens [i] указывает номер строки
ai!= aj для я!= j, поскольку никакие королевы не могут находиться в одной строке... Таким образом, все решения заключаются в перестановке

вот полная версия алгоритма

Поскольку вы выполняете итерацию через перестановку вместо того, чтобы попробовать каждую строку и каждый двоеточие, ваше время выполнения идет от nxnxnxn... до nx(n-1)x(n-2)x(n-3)... короче, а не n ^ n, теперь у вас есть n!

Следующий шаг - выбрать ответы от всех кандидатов, вам нужно сравнить каждые два ферзя, чтобы убедиться, что они не разделяют диагональ... сравнить каждую две королевы довольно просто, просто выберите 2 или в других слова n(n-1)/2

так что теперь у вас это есть, время выполнения n! times n(n-1)/2

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