스도쿠 알고리즘 분석

Question

이 스도쿠 (9 × 9)를 해결하기위한 코드입니다

#include <iostream> 
#define dim 9 
#define br_polja dim*dim 

using namespace std; 


bool Fsearch (int tab[dim][dim],int *x,int *y, int cand[dim], int *num_cand, int &free) { 
int min=9; 
*x=-1; 
*y=-1; 
free=0; 
for (int i=0;i<dim;i++) { 
    for (int j=0;j<dim;j++) { 

     if (tab[i][j]!=0) continue; 
     free+=1; 
     *num_cand=0; 
     int cand_f[dim]; 
     for (int w=0;w<dim;w++) 
      cand_f[w]=1; 

     int p,q; 
     p=i+3-(i%3); 
     q=j+3-(j%3); 

     for (int w=p-3;w<p;w++) 
      for (int r=q-3;r<q;r++) 
       if (tab[w][r]!=0){   
            cand_f[tab[w][r]-1]=0; 
            } 

     for (int w=0;w<dim;w++) { 
      if (tab[w][j]!=0) cand_f[tab[w][j]-1]=0; 
      if (tab[i][w]!=0) cand_f[tab[i][w]-1]=0; 
      } 

     for (int w=0;w<dim;w++) 
      if (cand_f[w]!=0) 
       *num_cand+=1; 


     if (*num_cand==1) { 
            *x=i; 
            *y=j; 
            int z=0; 
            for (int w=0;w<dim;w++) 
             if (cand_f[w]!=0) { 
              cand[z]=w+1; 
              z++; 
              } 
            return true; 
            } 
     else if (*num_cand<min && *num_cand>0) { 
            int z=0; 
            for (int w=0;w<dim;w++) 
             if (cand_f[w]!=0) { 
              cand[z]=w+1; 
              z++; 
              } 
            min=*num_cand; 
            *x=i; 
            *y=j; 
            } 
     else if (*num_cand==0) { 
      return false; 
      } 
     } 
    } 

    *num_cand=min; 
    if (free<1) return false; 
    else return true;   
} 

bool Fsudoku(int tab[dim][dim]) { 
int free=0; 

int x,y; 
int cand[dim]; 
int num_cand; 
brojacK=0; 
if (!Fsearch(tab,&x,&y,cand, &num_cand,free)) { 
               if (free==0) return true; 
               else return false; 
               } 


for (int i=0;i<num_cand;i++) { 
    tab[x][y]=cand[i]; 
    if (Fsudoku(tab)) return true; 
    else tab[x][y]=0; 
    } 
return false; 

} 

누군가가 나에게 큰 O 또는 큰 세타 표기법이 알고리즘을 분류하는 데 도움이 알 수 있습니다. 나는 O (n^3)를 얻었지만, 우리는 그것이 사실이 아님을 알 수 있습니다! 그래서 조언이나 조언을 해줘서 고맙습니다. 그리고 원한다면 의사 코드로도 게시 할 수 있습니다!

감사합니다, MB

Answer 1

빅 O 용어가 지배하는에 관한 것입니다.

각 루프는 몇 번 실행됩니까?

길이가 고정되어 있습니까?

런타임에 영향을 줄 수있는 매개 변수는 무엇입니까?