algorithm - 该算法的大 O 表示法是什么？

Question

我目前正在尝试理解动态规划，我发现了一个有趣的问题:“给定一个 nxn 方格的棋盘和一个起始位置(xs，ys)，找到最短(如移动次数)路径骑士可以到达结束位置(xe，ye)”。这就是我的解决方案听起来的样子:

Initialize the matrix representing the chess board (except the "square" xs,ys) with infinity.
The first value in a queue is the square xs,ys.
while(the queue is not empty){
         all the squares available from the first square of the queue (respecting the rules of chess) get "refreshed"
         if (i modified the distance value for a "square")
                    add the recently modified square to the queue
}

有人可以帮我找出这个函数的计算时间 O 值是多少吗？我(有点)理解 big-O，但我无法为这个特定的函数赋值。

Answer 1

因为您使用的是队列，所以处理方 block 的顺序将按照最小距离的顺序。这意味着您只会修改一个正方形的距离值一次，因此时间将为 O(n^2)，因为有 n^2 个正方形。