数独算法分析

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是哪些方面占据主导地位。

那么每个循环运行多少次？

他们是固定长度，还是他们有所不同？

哪些参数可能会影响运行时间？