Python 算法：我的算法有多复杂，我该如何优化它？

Question

我正在尝试完成一项任务，其中给你 n（方形棋盘的大小、皇后（它们占据的正方形）和查询（坐标列表）。我要 return 一个布尔值列表，说明每个查询是否可被任何皇后攻击。我知道我的算法有效，但我也知道它效率不高 "enough"。通过研究，我猜复杂度是 O(queensqueries)？所以这是我的第一个问题，是 O(queensqueries)，如果不是为什么？其次，有没有人知道我可以如何优化它甚至到 O(queens + queries)？如果这是一个基本问题，我深表歉意，但我主要是自学成才，没有人可以问这个问题。提前致谢！

def squaresUnderQueenAttack(n, queens, queries):
    output = []
    for i in queries:
        attackable = False
        for j in queens:
            if attackable != True and (i[0]==j[0] or i[1]==j[1] or abs(i[0]-j[0])==abs(i[1]-j[1])):
                attackable = True
                break
        output.append(attackable)
    return output

Answer 1

您当前的代码是 O(queens * queries)。您可以将其改进为 O(queens + queries).

创建三个数组，每个数组有 8 个元素。称它们为 row、col、diagleft 和 diagright .

查看每个皇后，如果它在第 0 行，则将行中的位置设置为真。如果它在第 3 列，则将该位置设置为 col 为真。标记对角线 0-7 并在其中做适当的标记。

现在数组表示所有有皇后的行、列和对角线。

现在，查看每个查询并检查与其位置对应的任何数组条目是否标记为真。如果是这样，那就是女王威胁它了。

请注意，在大 O 表示法中，我们对运行时间中的哪个因子 "dominates" 感兴趣，因此上述解决方案可能更恰当地认为是在 [=22] 中运行=]O(max(queens,queries)) 时间。也就是说，如果你有很多查询，皇后计算只需要一点时间。同样，如果你有很多皇后而查询很少，那么该操作将占用你大部分时间。

Python 算法：我的算法有多复杂，我该如何优化它？

Python algorithm: What is the complexity of my algorithm and how can I optimize it?

python

optimization

performance

big-o