Историческая информация: Я решил проблему N-Queens с помощью приведенного ниже алгоритма C#, который возвращает общее количество решений, учитывая доску размером n x n. Он работает, но я не понимаю, почему это будет иметь временную сложность O(n!), или если это другая временная сложность. Я также не знаю, сколько места используется в стеке рекурсии (но знаю о дополнительном месте, используемом в булевом рваном массиве). Я никак не могу понять временную и пространственную сложность таких решений. Такое понимание было бы особенно полезно на технических собеседованиях, для анализа сложности без возможности выполнения кода.

Предварительное расследование: Я прочитал несколько сообщений в SO, где автор прямо просит сообщество предоставить временную и пространственную сложность их алгоритмов. Вместо того чтобы делать то же самое и просить быстрых и легких ответов, я хотел бы понять, как вычислить временную и пространственную сложность алгоритмов с обратным ходом, чтобы я мог делать это в дальнейшем.

Я также читал во многих местах в SO и за его пределами, что в общем случае рекурсивные алгоритмы обратного обхода имеют временную сложность O(n!), поскольку на каждой из n итераций вы просматриваете на один элемент меньше: n, затем n - 1, затем n - 2, …. 1. Однако я не нашел объяснения, почему это так. Я также не нашел объяснения пространственной сложности таких алгоритмов.

Вопрос: Может ли кто-нибудь объяснить пошаговый подход к решению задач для определения временных и пространственных сложностей рекурсивных алгоритмов с обратным ходом, таких как эти?

public class Solution {
    public int NumWays { get; set; }
    public int TotalNQueens(int n) {
        if (n <= 0)
        {
            return 0;
        }

        NumWays = 0;

        bool[][] board = new bool[n][];
        for (int i = 0; i < board.Length; i++)
        {
            board[i] = new bool[n];
        }

        Solve(n, board, 0);

        return NumWays;
    }

    private void Solve(int n, bool[][] board, int row)
    {
        if (row == n)
        {
            // Terminate since we've hit the bottom of the board
            NumWays++;
            return;
        }

        for (int col = 0; col < n; col++)
        {
            if (CanPlaceQueen(board, row, col))
            {
                board[row][col] = true; // Place queen
                Solve(n, board, row + 1);
                board[row][col] = false; // Remove queen
            }
        }
    }

    private bool CanPlaceQueen(bool[][] board, int row, int col)
    {
        // We only need to check diagonal-up-left, diagonal-up-right, and straight up. 
        // this is because we should not have a queen in a later row anywhere, and we should not have a queen in the same row
        for (int i = 1; i <= row; i++)
        {
            if (row - i >= 0 && board[row - i][col]) return false;
            if (col - i >= 0 && board[row - i][col - i]) return false;
            if (col + i < board[0].Length && board[row - i][col + i]) return false;
        }

        return true;
    }
}

Ответы (1)

Во-первых, определенно не верно, что все алгоритмы рекурсивного бэктрекинга имеют сложность O(n!): конечно, это зависит от алгоритма, и вполне может быть еще хуже. Тем не менее, общий подход состоит в том, чтобы записать рекуррентное соотношение для временной сложности T(n), а затем попытаться решить его или хотя бы охарактеризовать его асимптотическое поведение.

Шаг 1: Уточните вопрос

Нас интересует наихудший случай, наилучший случай или средний случай? Каковы входные параметры?

В этом примере предположим, что мы хотим проанализировать поведение в наихудшем случае, и соответствующим входным параметром является n в методе Solve.

В рекурсивных алгоритмах полезно (хотя и не всегда возможно) найти параметр, который начинается со значения входного параметра и затем уменьшается с каждым рекурсивным вызовом, пока не достигнет базового случая.

В данном примере мы можем определить k = n - row. Таким образом, при каждом рекурсивном вызове k уменьшается, начиная с n до 0.

Шаг 2: Аннотируем и сокращаем код

Нет, мы смотрим на код, сокращаем его до релевантных битов и аннотируем его сложности.

Мы можем свести ваш пример к следующему:

private void Solve(int n, bool[][] board, int row)
    {
        if (row == n) // base case
        {
           [...] // O(1)
           return;
        }

        for (...) // loop n times
        {
            if (CanPlaceQueen(board, row, col)) // O(k)
            {
                [...] // O(1)
                Solve(n, board, row + 1); // recurse on k - 1 = n - (row + 1)
                [...] // O(1)
            }
        }
    }

Шаг 3: Запишите рекуррентное соотношение

Рекуррентное соотношение для этого примера можно считать непосредственно из кода:

T(0) = 1         // base case
T(k) = k *       // loop n times 
       (O(k) +   // if (CanPlaceQueen(...))
       T(k-1))   // Solve(n, board, row + 1)
     = k T(k-1) + O(k)

Шаг 4: Решить рекуррентное соотношение

Для этого шага полезно знать несколько общих форм рекуррентных соотношений и их решений. Приведенное выше соотношение имеет общий вид

T(n) = n T(n-1) + f(n)

которая имеет точное решение

T(n) = n!(T(0) + Sum { f(i)/i!, for i = 1..n })

что мы можем легко доказать с помощью индукции:

T(n) = n T(n-1) + f(n)                                          // by def.
     = n((n-1)!(T(0) + Sum { f(i)/i!, for i = 1..n-1 })) + f(n) // by ind. hypo.
     = n!(T(0) + Sum { f(i)/i!, for i = 1..n-1 }) + f(n)/n!)
     = n!(T(0) + Sum { f(i)/i!, for i = 1..n })                 // qed

Теперь нам не нужно точное решение; нам нужно только асимптотическое поведение, когда n приближается к бесконечности.

Итак, давайте рассмотрим бесконечный ряд

Sum { f(i)/i!, for i = 1..infinity }

В нашем случае f(n) = O(n), но давайте рассмотрим более общий случай, когда f(n) является арифметическим многочленом от n (потому что окажется, что это не имеет значения). Легко убедиться, что ряд сходится, используя тест соотношений:

L = lim { | (f(n+1)/(n+1)!) / (f(n)/n!) |, for n -> infinity }
  = lim { | f(n+1) / (f(n)(n+1)) |, for n -> infinity }
  = 0  // if f is a polynomial
  < 1, and hence the series converges

Поэтому для n -> бесконечность,

T(n) -> n!(T(0) + Sum { f(i)/i!, for i = 1..infinity })
      = T(0) n!, if f is a polynomial

Шаг 5: Результат

Поскольку пределом T(n) является T(0) n!, мы можем написать

T(n) ∈ Θ(n!)

что является жестким ограничением на наихудшую сложность вашего алгоритма.

Кроме того, мы доказали, что не имеет значения, сколько работы вы делаете внутри цикла for в дополнение к рекурсивным вызовам, пока она полиномиальна, сложность остается Θ(n!) (для этой формы рекуррентных отношений) (Выделено жирным шрифтом, потому что есть много ответов SO, в которых это неверно).

Аналогичный анализ с другой формой рекуррентного соотношения см. в здесь.

Обновление

Я допустил ошибку в аннотации к коду (я оставлю ее, потому что она все еще поучительна). На самом деле, и цикл, и работа, выполняемая в цикле, зависят не от k = n - row, а от начального значения n (назовем его n0, чтобы было понятнее).

Таким образом, рекуррентное соотношение становится

T(k) = n0 T(k-1) + n0

для которого точным решением является

T(k) = n0^k (T(0) + Sum { n0^(1-i), for i = 1..k })

Но поскольку первоначально n0 = k, имеем

T(k) = k^k (T(0) + Sum { n0^(1-i), for i = 1..k })
     ∈ Θ(k^k)

что немного хуже, чем Θ(k!).

2022 WebDevInsider