N皇后问题的两种算法速度比较

Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

对于这个经典的问题，通常有一下两种算法。我看一本算法书上说第二种效率要比第一种高，为啥第一种算法可以AC而第二个却超时了？请教各位大神！

算法一：

#include<iostream>
using namespace std;
int n,c[15],cnt,ans[15];
void DFS(int cur)
{
     if( cur==n){
         cnt++;
         return ;
     }
     else{
          for(int i=0; i<n; i++){
               c[cur]=i;
               bool flag=true;
               for(int j=0; j<cur; j++){
                    if( c[j]==i|| c[j]-j==i-cur|| c[j]+j==cur+i){
                        flag=false;
                        break;
                    }
               }
               if( flag)
                   DFS(cur+1);
          }
     }          
}
int main()
{
    int i;
    for( i=1; i<11; i++){
         memset(c,0,sizeof(c));
         cnt=0;
         n=i;
         DFS(0);
         ans[i]=cnt;
    }
    while( scanf("%d",&n)&&n){
           printf("%d\n",ans[n]);
    }
}

算法二：

#include <stdio.h>
int tot=0;
int n;
int c[100];
void search(int cur);
int main()
{
    while(~scanf("%d",&n))
    {
        search(0);
        printf("%d\n",tot);
    }
    return 0;
}
void search(int cur)
{
    int i,j,ok;//ok的值定在第i列，即判断第i列是否可以放皇后
    if(cur==n)tot++;
    else for(i=0;i<n;i++){//判断第cur行的第i列是否可以存放元素
        c[cur]=i;
        ok=1;
        for(j=0;j<cur;j++){
            if(c[cur]==c[j]||c[j]+j==c[cur]+cur||j-c[j]==cur-c[cur])
            {ok=0;break;}
            if(ok)search(cur+1);
        }
    }
}