#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().
Существует много оптимизаций, чем может улучшить временную сложность алгоритма.
В этих ссылках есть дополнительная информация:
https://sites.google.com/site/nqueensolver/home/algorithm-results
https://sites.google.com/site/nqueensolver/home/algorithms/2backtracking-algorithm
Для вашей функции T(n) = n*T(n-1) + O(n^2), которая в среднем соответствует временной сложности O(N!).
ВРЕМЕННАЯ КОМПЛЕКСНОСТЬ ПРОБЛЕМЫ N-QUEEN IS
O (N!)
Объяснение: Если мы добавим все это и определим время выполнения как T (N). Тогда T (N) = O (N2) + N * T (N-1). Если вы нарисуете дерево рекурсии с использованием этого повторения, конечный член будет чем-то вроде n3 + n! O (1). По определению Big O это можно свести к времени выполнения O (n!).
Сложность 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 не уменьшается. Для каждого вызова функции он остается таким же. Но для количества раз, когда функция вызывается, она уменьшается, так что рекурсия может завершиться.
O (n ^ n) определенно является верхней границей при решении n-ферзей с использованием обратного отслеживания. Я предполагаю, что вы решаете это, назначая королеву по столбцам. Однако учтите это: когда вы назначаете местоположение королевы в первом столбце, у вас есть n опций, после этого у вас есть только n-1 опций, так как вы не можете поместить королеву в той же строке, что и первая королева, потом н-2 и тд. Таким образом, сложность в худшем случае все еще ограничена сверху O (n!).
Надеюсь, что это отвечает на ваш вопрос, хотя я почти на 4 года опоздал!
Давайте рассмотрим, что наша королева - ладья, то есть нам не нужно заботиться о диагональных конфликтах.
Сложность времени в этом случае будет 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!) точки зрения фактического количества операций.
Да, есть более жесткая привязка, но сначала вам может понадобиться немного изменить код:
вместо того, чтобы пробовать каждую строку каждого двоеточия, вы можете уменьшить общее количество рекурсии, просто перебирая все возможные перестановки чисел из 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
Я изучаю компьютерную науку, я понимаю, что иногда трудно найти точное время выполнения алгоритма особенно, когда у вас есть петли и циклы и рекурсии... но вместо подсчета иногда бывает легче проанализировать, что делает настоящий алгоритм, и получить заключение с точки зрения комбинаторной, надеясь, что это поможет