Эта функция O (n), хотя она имеет 3 для циклов?

Question

Я нашел функцию, которая реализует минное поле минного тральщика, учитывая несколько бомб и размер поля. Я хочу выяснить временную сложность функции в Big O Notation.

Функция 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 - количество бомб?

Я думаю, это потому, что, хотя есть три цикла for, только первый, for bomb in bombs:, будет работать больше раз, если количество бомб увеличится. Все остальные инструкции выполняются в постоянном времени или O(1).

Edit:

Как уже говорили другие в комментариях и некоторых ответах, переменная, которую нужно увеличить, чтобы выяснить сложность времени, должна быть не количеством бомб, а количеством ячеек.

Я ищу ответ, который показывает:

Новые вопросы:

• Какую переменную я должен увеличивать без границ?
• Что такое временная сложность, представленная в обозначении Big 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) все еще сохраняется.

Answer 2

Является ли эта функция O (n) , где n - количество бомб?

Да, это очень много, и все же не: -)

Это так, потому что два внутренних цикла не имеют абсолютно никакого отношения к количеству столбцов или строк. Они просто перебирают previous/current/next row/column, фактически делая их постоянными.

Вы действительно затронули аспект анализа сложности, который пропускает большинство новичков:

Что такое n?

Здесь есть много возможностей: бомбы, строки, столбцы, ячейки или какой-то их продукт.

Однако, использование бомб определенно не правильно, потому что само это ограничено количеством клеток. Если предположить, что нормальные правила Сапера не более одной бомбы на клетку, то ограничивающим фактором является количество ячеек, поэтому это то, что вы должны использовать для n.

Отсюда и цикл обработки бомбы (с его телом постоянного времени, см. Выше) и инициализация поля:

field = [[0 for i in range(num_cols)] for j in range(num_rows)]

в конечном итоге ограничены количеством клеток.

И, поскольку две последовательные (не вложенные) O(n) операции по-прежнему O(n), это сложность, которую вы имеете.

---

Один момент, который я хотел бы затронуть, связан с реальными последствиями. Анализ сложности очень хорош для определения того, что происходит, когда входные данные становятся большими. Это означает такие вещи, как сортировка, когда вам может потребоваться отсортировать двадцать предметов или сто миллиардов.

Это , а не , что так полезно в такой игре, как Сапер, где вы, скорее всего, ограничены разрешением примерно 3840x2160. Если учесть крошечные ячейки размером 20х20, то получится 192х108 или около 20000 ячеек. Это то, что ваши компьютеры собираются пройти не сразу, а, вероятно, даже раньше, чем сигналы вашей автономной нервной системы достигнут вашего века, чтобы начать процесс: -)

Answer 3

Нет. Если n - количество бомб, то n не может превышать количество ячеек. Объем работы, выполняемой, когда n равен количеству ячеек, является фиксированным пределом, который алгоритм не может превышать. Следовательно, если мы предположим, что число ячеек постоянно, то это O (1).

Если мы предположим, что количество ячеек является переменным, это не O (n).

Так что нет предположения, которое приводит к выводу, что это O (n). (Кроме этого вы назвали этот «mine_sweeper», даже если это не классическая игра / алгоритм / задача подметальной машины, в которой в данной ячейке может находиться не более одной мины.)

Давайте назовем R числом строк, а C числом столбцов. В традиционном тральщике количество бомб составляет некоторую долю числа ячеек, то есть доля ячеек, содержащих бомбы, является постоянной. В этом случае:

1. Максимальное количество бомб - R * C.
2. Внешний цикл повторяет O (R * C) раз.
3. Следующий цикл повторяется за O (R) раз.
4. Следующий цикл повторяется O (C) раз.
5. Таким образом, общий алгоритм O (R ^ 2 * C ^ 2).

Если N - количество клеток, то O (N ^ 2), если вероятность ячейки, содержащей мину, постоянна. Если вместо этого число бомб постоянное, то это O (N), опять же, где N - количество ячеек.

Answer 4

Если мы предположим, что каждый оператор (включая доступ к элементам списков) выполняется детерминистически в постоянное время, то каждый внутренний цикл for будет иметь прибл. 3х постоянный коэффициент. Возьми их товар и получишь 9н; однако, поскольку нота Big O заботится только об ограничении поведения, она эквивалентна O (n), поэтому вы правы.