Нахождение сложности возвратов рекурсивный алгоритм

Question

У меня есть этот рекурсивный алгоритм:

#include <iostream> 
#include <cmath> 
#include <map> 
#include <iterator> 
#define N 8 
using namespace std; 
void putIntoBoard(int a, int b, int board[][N]); 
bool isFull(int board[][N]); 
void cleanBoard(int board[][N]); 
void bishopSolver(int level, int i, int board[][N]); 
void putIntoArray(int a, int b); 
void printout(); 

map<int, int> coordMap; 

int main(){ 
    int board [N][N]= {0}; 
    int count= 0; 
    int level; 
    int i; 



    bishopSolver(0,0,board); 

    return 0; 
} 

void printout(){ 

    for (map<int,int>::iterator it = coordMap.begin(); it != coordMap.end(); ++it) { 
     int value = it->second; 


     int y = value/8; 
     int x = value - y * 8; 
     cout<<"("<<x<<";"<<y<<"), "; 
     x=x+1; 
     if ((x) == 7) x=0; 
     cout<<"("<<x<<":"<<y<<"), "<<endl; 


    } 
} 




void putIntoBoard(int a, int b, int board[][N]){ 


    int i=a,j=b; 
    board[i][j]=1; 

    while(i>0 && (j<7))/*Up right*/{ 
     i--; 
     j++; 
     board[i][j]=1; 
    } 
    i=a; 
    j=b; 
    while(j>0 && i>0) /*Up Left*/{ 
     i--; 
     j--; 
     board[i][j]=1; 

    } 
    i=a; 
    j=b; 
    while(i<7&& j<7) /*Down right*/{ 
     i++; 
     j++; 
     board[i][j]=1; 

    } 
    i=a; 
    j=b; 

    while(i<7 && j>0) /*Down left*/{ 

     i++; 
     j--; 
     board[i][j]=1; 
    } 


} 
bool isFull(int board[][N]){ 

    int x1, y1; 

    for (map<int,int>::iterator it = coordMap.begin(); it != coordMap.end(); ++it) { 
     int value = it->second; 


     int y = value/8; 
     int x = value - y * 8; 
     putIntoBoard(x, y, board); 
    } 

    int i, j; 
    int count=0; 
     for (i=0; i<=7; i++){ 

      if (i%2==1) j=1; 
     else j=0; 

     for (; j<=7; j+=2){ 
      if (board[i][j]==1) count++; 
     } 
    } 
    if (count==32){ 
     cleanBoard(board); 
     return true; 
    }else{ 
     cleanBoard(board); 
     return false; 
    } 
} 
void cleanBoard(int board[][N]){ 
     for (int i=0; i<N; i++) 
    { 
     for (int j=0; j<N; j++) board[i][j]=0; 
    } 
} 

void addToMap(int level, int i) { 
    coordMap[level] = i; 
} 

void removeFromMap(int level) { 
    coordMap.erase(level); 
} 


void bishopSolver(int level, int i, int board[][N]){ 
    int size = 63 - (6 - level); 
    for (; i < size; i+=2){ 
     addToMap(level, i); 
     if(level == 3 && isFull(board)){ 

      cout<<"Solved: "<<endl; 
      printout(); 
      return; 
     } 
     if (level < 3){ 
      bishopSolver(level + 1, i + 2, board); 
     } 
     removeFromMap(level); 
    } 
} 

В основном это решает проблему слона, чтобы заполнить доску с 8 епископов, так что вся шахматная доска занимает 8 архиереев ходов. На мой взгляд, этот алгоритм является n !, но это не грубая сила, поэтому я ошибаюсь. Может ли кто-нибудь дать мне правильный ответ здесь?

Answer 1

Если N = 8, то асимптотическая сложность отсутствует.

Если N варьируется, подход грубой силы будет (не так ли?), Чтобы выбрать N ячеек среди доступных N^2 и проверить, работает ли их епископы. Это приводит к сложности N^2, выберем N ~ N^{2N}/N! ~ (Ne)^N (раз полиномиальный член). Это экспоненциально больше, чем N! ~ (N/e)^N.

Я не читал детали вашего эго, но я бы поспорил, что это на самом деле N !.