0

这是解决数独（9x9）的代码：

#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;

 }

有人可以告诉我用 Big O 或 Big Theta 表示法对这个算法进行分类。我得到了 O(n^3) 但我们可以看到那不是真的！所以，给我一个提示或建议如何开始，我将非常感激。如果你愿意，我也可以用伪代码发布！

谢谢，MB

4

1 回答 1

0

大 O 是关于哪些术语占主导地位。

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

它们是固定长度的，还是变化的？

可以更改哪些参数会影响运行时间？

于 2013-07-10T23:10:30.433 回答