国际象棋骑士游戏的复杂性

Question

我在理解渐近分析或复杂性时遇到问题，我尝试了以下 link 并阅读完整的文章，但这并没有给我问题的最终答案，即：

我是应该为每一行代码编写复杂性并对其进行总结还是其他什么？我的老师没有完全解释如何做，但希望完成。

Condition: a knight (chess) must cross an iced-lake (m x n matrix) and get his buddy from the other side of the lake with given obstacles. Every time he jumps, the cell of the matrix that he jumps on becomes an obstacle (ice falls). After he gets his buddy he must return to the starting point following a different route. Starting point is bottom corner left cell, his buddy is located on top right corner cell

我对这个算法使用了回溯，剩下的问题是计算时间或渐近复杂度。代码如下：

#include<stdio.h>
#include<conio.h>
#define N 50
typedef struct{
   int x;
   int y;
} coordonate;
int sol=0,m,n;
coordonate vectSol[N];
void jump(int xL,int yL,int xD,int yD,int obstacole[N][N],int steps,coordonate road[N]);
int main(){
    int i,j,x,y,obstacole[N][N],nrObs;
    int KnightMatrixRoad[N][N], KnightMatrixBack[N][N];
    coordonate pathKnight[N],pathBack[N];
    printf("m=");
    scanf("%d",&m);
    printf("n=");
    scanf("%d",&n);
    printf("Nr. of obstacles: ");
    scanf("%d",&nrObs);
    for(i=0;i<nrObs;i++){
        printf("Insert obstacle %d through space bar (x,y):",i+1);
        scanf("%d %d",&x,&y);
        obstacole[y-1][x-1]=1;
    }
    jump(0,0,m-1,n-1,obstacole,0,pathKnight);
    for(i=0;i<=sol;i++){
        obstacole[vectSol[i].y][vectSol[i].x]=1;
        pathKnight[i]=vectSol[i];
        vectSol[i].x=0;
        vectSol[i].y=0;
    }
    sol=obstacole[n-1][m-1]=obstacole[0][0]=0;
    jump(m-1,n-1,0,0,obstacole,0,pathBack);
    for(i=0;i<=sol;i++){
        pathBack[i]=vectSol[i];
        vectSol[i].x=0;
        vectSol[i].y=0;
    }
    for(i=0;(pathKnight[i-1].x!=m-1) || (pathKnight[i-1].y!=n-1);i++){
        KnightMatrixRoad[pathKnight[i].y][pathKnight[i].x]=i;
    }
    puts("\nPath to his buddy:\n");
    for(i=n-1,sol=0;i>=0;i--){
        for(j=0;j<m;j++)
            printf("%3d",KnightMatrixRoad[i][j]);
        printf("\n\n");
    }
    for(i=0;((pathBack[i-1].x!=0) || (pathBack[i-1].y!=0)) || i==0;i++){
        KnightMatrixBack[pathBack[i].y][pathBack[i].x]=i;
    }
    puts("\nPath back to starting point:\n");
    for(i=n-1,sol=0;i>=0;i--){
        for(j=0;j<m;j++)
            printf("%3d",KnightMatrixBack[i][j]);
        printf("\n\n");
    }
    getch();
}
void jump(int xLocal,int yLocal,int xDest,int yDest,int obstacole[N][N],int steps,coordonate road[N]){
    int i,j;
    int tempObstacole[N][N];
    for(i=0;i<n;i++)
        for(j=0;j<m;j++){
            tempObstacole[i][j]=obstacole[i][j];
        }
    road[steps].x=xLocal;
    road[steps].y=yLocal;
    if(xLocal==xDest && yLocal==yDest){
        if(sol==0 || steps<sol){
            for(i=0;i<=sol;i++){
                vectSol[i].x=0;
                vectSol[i].y=0;
            }
            sol=steps;
            for(i=0;i<=sol;i++)
                vectSol[i]=road[i];
        }
    }
    if(sol==0 || steps+1<sol){
        tempObstacole[yLocal][xLocal]=1;
        if(yLocal+2<n && xLocal+1<m && !(tempObstacole[yLocal+2][xLocal+1]))
            jump(xLocal+1,yLocal+2,xDest,yDest,tempObstacole,steps+1,road);
        if(yLocal+2<n && xLocal-1>=0 && !(tempObstacole[yLocal+2][xLocal-1]))
            jump(xLocal-1,yLocal+2,xDest,yDest,tempObstacole,steps+1,road);
        if(yLocal-2>=0 && xLocal+1<m && !(tempObstacole[yLocal-2][xLocal+1]))
            jump(xLocal+1,yLocal-2,xDest,yDest,tempObstacole,steps+1,road);
        if(yLocal-2>=0 && xLocal-1>=0 && !(tempObstacole[yLocal-2][xLocal-1]))
            jump(xLocal-1,yLocal-2,xDest,yDest,tempObstacole,steps+1,road);
        if(yLocal+1<n && xLocal+2<m && !(tempObstacole[yLocal+1][xLocal+2]))
            jump(xLocal+2,yLocal+1,xDest,yDest,tempObstacole,steps+1,road);
        if(yLocal+1<n && xLocal-2>=0 && !(tempObstacole[yLocal+1][xLocal-2]))
            jump(xLocal-2,yLocal+1,xDest,yDest,tempObstacole,steps+1,road);
        if(yLocal-1>=0 && xLocal+2<m && !(tempObstacole[yLocal-1][xLocal+2]))
            jump(xLocal+2,yLocal-1,xDest,yDest,tempObstacole,steps+1,road);
        if(yLocal-1>=0 && xLocal-2>=0 && !(tempObstacole[yLocal-1][xLocal-2]))
            jump(xLocal-2,yLocal-1,xDest,yDest,tempObstacole,steps+1,road);
    }
}

Answer 1

分析代码的时候，需要逐行分析，计算每个operation/recognizing的时间复杂度，最后求和才能得到全貌。

例如，您可以有一个具有 线性复杂度 的简单循环，但稍后在同一程序中，您可以有一个具有 三次复杂度的三重循环，因此您的程序将具有 三次复杂度 。函数增长顺序在这里发挥作用。

我们来看一个算法的时间复杂度有哪些可能，可以看我上面说的增长顺序：

常数时间有一个增长顺序1，例如：a = b + c.
对数时间有一个增长阶数LogN，通常会出现当您将某物分成两半（二分搜索、树、偶数循环）或以相同方式将某物相乘时。

线性，增长顺序为N，例如

int p = 0;
for (int i = 1; i < N; i++)
  p = p + 2;

Linearithmic，增长顺序为n*logN，通常出现在分治算法中。

Cubic，增长顺序 N^3，经典示例是检查所有三元组的三重循环：

int x = 0;
for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++)
      for (int k = 0; k < N; k++)
          x = x + 2

指数，增长顺序2^N，通常发生在您进行穷举搜索时，例如检查某个集合的子集。

我认为你的老师想要全面了解回溯算法，你会发现回溯算法非常非常慢。

国际象棋骑士游戏的复杂性

Complexity of a Chess Knight game

c

backtracking

time-complexity