该算法的大 O 表示法是什么？
我目前正在尝试理解动态规划，我发现了一个有趣的问题：“给定一个 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，但我无法为这个特定的函数赋值。
I'm currently trying to understand dynamic programming, and I found an interesting problem : "Given a chess board of nxn squares and a starting position(xs,ys), find the shortest (as in no. of moves) path a knight can take to an end position(xe,ye)". This is how my solution would sound like :
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
}
Can someone please help me find out what's the computing-time O value for this function? I (kind of) understand big-O, but I just can't put a value for this particular function.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
因为您使用的是队列，所以处理方块的顺序将按照最小距离的顺序。这意味着您只会修改一个正方形的距离值一次，因此时间将为 O(n^2)，因为有 n^2 个正方形。
Because you are using a queue, the order that you process the squares is going to be in order of minimum distance. This means that you will only ever modify the distance value for a square once, and therefore the time will be O(n^2), since there are n^2 squares.
你的算法措辞很糟糕
你没有定义“队列”的内容
你没有定义“刷新”
你总是卡在第一个方块上，你没有跟踪当前的方块。
还有 Google Djkistra 算法不，不要使用 dijkstra 算法。你没有加权图。如果你想使用动态编程算法来暴力破解答案，我会从 (xe,ye) 开始，你应该能够在 nxn 网格上得到 O(n^2)
但如果你考虑你的约束（你的棋子像骑士一样移动，他沿着网格移动，而不是任意图形）你应该能够在 O(n) 时间内完成这个问题
Your algorithm is worded poorly
You don't define the contents of your "queue"
you don't define "refreshed"
you're always stuck on the first square, you're not keeping track of a current square.
also, Google Djkistra's algorithmNo, don't do dijkstra's algorithm. you don't have a weighted graph.If you want to use a dynamic programming algorithm to brute force your way to an answer, I'd start at (xe,ye), and you should be able to get O(n^2) on a nxn grid
but if you consider your constraints(your piece moves like a knight, and he moves along a grid, and not an arbitrary graph) you should be able to do this problem in O(n) time
听起来有点像 Dijkstra 的最短路径算法。在这种情况下，它的复杂度为 O(N^2)，您需要找到从源到目的地的所有可能路径的“距离”，以便确定最低的路径。
Sounds somewhat like Dijkstra's shortest path algorithm. In which case it is O(N^2), you're finding the "distance" for all possible paths from source to destination in order to determine the lowest one.
我认为这是广度优先搜索。很明显，您最多在队列中添加一个方块一次，并且队列条目的处理时间为 O(1)，因此总复杂度受 O(N^2) 限制。但是，如果您可以证明一个定理，该定理告诉 NxN 棋盘上从位置 A 到 B 的移动次数小于 N（直观上，对于 N 等于或大于 8，这听起来合理），那么您的算法将是在）。
This is a breadth first search in my opinion. It is clear that you add a square at most once in the queue and the processing of a queue entry is O(1), so the total complexity is bounded by O(N^2). However, if you can prove a theorem that tells the number of moves to get from position A to B on a NxN chess board is less than N (and intuitively this sounds reasonable for N equals or greater than 8), then your algorithm will be O(N).