big-o - 即使这个函数有 3 个 for 循环，它的复杂度还是 O(n) 吗？

Question

我发现了一个函数，可以在给定一些炸弹和区域大小的情况下实现扫雷雷区。我想用大 O 表示法计算出该函数的时间复杂度。

函数 mine_sweeper 接受一个名为 bombs 的数组以及行数和列数 num_rows 和 num_cols 并返回雷区:

def mine_sweeper(bombs, num_rows, num_cols):
    field = [[0 for i in range(num_cols)] for j in range(num_rows)]
    for bomb in bombs:
        (row_i, col_i) = bomb
        field[row_i][col_i] = -1
        for i in range(row_i - 1, row_i + 2):
            for j in range(col_i - 1, col_i + 2):
                if (0 <= i < num_rows and 0 <= j < num_cols
                        and field[i][j] != -1):
                    field[i][j] += 1
    return field

# For example
# mine_sweeper([[0, 2], [2, 0]], 3, 3) should return:
# [[0, 1, -1],
# [1, 2, 1],
# [-1, 1, 0]]

关于代码的注释:

• 在返回的雷区中，炸弹由 -1 表示
• 否则，整数表示该位置周围的炸弹数量

原始问题:

• 此函数是否为 O(n)，其中 n 是炸弹数量？

我认为这是因为即使有 3 个 for 循环，如果炸弹数量增加，只有第一个 forombininbombs: 会运行更多次。所有其他指令都在恒定时间或 O(1) 内运行。

编辑:

正如其他人在评论和一些答案中所说的那样，为了计算时间复杂度而增加的变量不应该是炸弹的数量，而应该是单元格的数量。

我正在寻找显示以下内容的答案:

新问题:

• 我应该无限增加什么变量？
• 使用上述变量时，大 O 表示法表示的时间复杂度是多少？

Answer 1

由于函数定义了 field = [[0 for i in range(num_cols)] for j in range(num_rows)]

战场上的炸弹数量最多为细胞数量，复杂度为O(num_cols * num_rows)

只是为了初始化数组。

如果我们分析函数的其余部分，我们有 bombs其中bombs.size <= num_cols * num_rows必须持有。循环的其余部分仅执行 -1..2 == 3运营-1..2 == 3次，共 9 次操作。

与

 if (0 <= i < num_rows and 0 <= j < num_cols and field[i][j] != -1):
                    field[i][j] += 1

以恒定时间运行。

所以假设最坏的情况为 bombs.size == num_cols * num_rows bomb in bombs部分是 O(9 * num_cols * num_rows) -> O(num_cols * num_rows)仍然成立。