Question

C语言迷宫问题，求该算法的时间和空间的复杂度。迷宫的路径已经定义好，求出路的算法。

详细见http://zhidao.baidu.com/question/1446899457771817460可以采纳多次。
分析时间复杂度是算出for循环里面的语句执行多少次吧，是怎么算出来的。分析一下每个语句执行了多少次

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励10（财富值+成长值）+提问者悬赏5（财富值+成长值）

Answer 1

该算法是不稳定的，其时空复杂度不仅和m,n有关，还和mg[][]的具体数值有关。
最坏情况下：每个点都试探过才走到终点。此时时间复杂度为：(m*n-1)*4，（其中4为4个方向），空间复杂度m*n*2，(其中m*n为存储迷宫图空间，m*n为栈空间);
再好情况下：一次试探过就走到终点。此时时间复杂度为：(min(m,n)-1)，空间复杂度m*n;

所以：
该算法时间复杂度为：[(m*n-1)*4+(min(m,n)-1)]/2，约为2×m×n
空间复杂度为3*m*n/2