Блог

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

 public boolean algorithm(int x, int y) {
    if (x == matrixHeight - 1 amp;amp; matrix1[x][y] == '0') {
        return true;
    } else if (x == 1 amp;amp; matrix1[x-1][y] == '0') {
        return true;
    } else if (y == matrixWidth - 1 amp;amp; matrix2[x][y] == '0') {
        return true;
    } else if (y == 1 amp;amp; matrix2[x][y-1] == '0') {
        return true;
    }
    if (matrix1[x-1][y] == '0' amp;amp; tempMatrix[x-1][y] == '-'){
        path.push(new int[]{x-1, y});
        tempMatrix[x-1][y] = ' '
        if (!algorithm(x-1, y)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix2[x][y] == '0' amp;amp; tempMatrix[x][y 1] == '-'){
        path.push(new int[]{x, y 1});
        tempMatrix[x][y 1] = ' ';
        if (!algorithm(x, y 1)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix1[x][y] == '0' amp;amp; tempMatrix[x 1][y] == '-'){
        path.push(new int[]{x 1, y});
        tempMatrix[x 1][y] = ' ';
        if (!algorithm(x 1, y)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix2[x][y-1] == '0' amp;amp; tempMatrix[x][y-1] == '-'){
        path.push(new int[]{x, y-1});
        tempMatrix[x][y-1] = ' ';
        if (!algorithm(x, y-1)) {
            path.pop();
        } else {
            return true;
        }
    }
    return false;
}
  

• Там, x , y есть координаты в матрице.
• matrix1 и matrix2 являются двумерными массивами, которые содержат '0' или '1'
• tempMatrix представляет собой двумерный массив, содержащий ‘ ‘ или ‘-‘
• path является ли стек
• matrixHeight является matrix1.length
• matrixWidth является matrix[0].length
• N M — размер матрицы (константа)

Примечание: это решатель лабиринта, который использует обратный путь.

Для рекурсии вам необходимо сгенерировать рекуррентное соотношение и решить. Смотрите http://en.wikipedia.org/wiki/Recurrence_relation . Не существует установленного способа решить каждое рекуррентное соотношение или даже сгенерировать его на основе алгоритма.

Примером может служить сортировка слиянием. Подумайте, сколько работы выполняется при каждом рекурсивном вызове. Сначала происходит постоянное разделение по времени; затем выполняются два рекурсивных вызова; затем происходит линейное слияние по времени. Сколько работы занимает рекурсивный вызов? Ну, каждый из них выполняет одно и то же, два рекурсивных вызова плюс шаг линейного слияния. Итак, вам нужно выражение для определения глубины и ширины дерева. Вы знаете, что при размере входных данных n высота дерева равна O (log (n)), и на каждом шаге выполняется в общей сложности O (n) работы по слиянию, поэтому всего выполняется O (n log (n)) работы.

Это похоже на решатель лабиринта с первой глубиной, который возвращает true, если вы можете выйти из лабиринта, и false в противном случае. Сложность заключается O(lines * columns) в том, что в худшем случае вы посещаете каждую ячейку постоянное количество раз.

 1 1 1 1
1 0 0 1
0 0 0 1
1 1 1 1
  

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

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

Посмотрите на алгоритм Ли для лучшего подхода.

На самом деле существует действительно простой анализ сложности этого алгоритма.

Каждый вызов algorithm выполняет от нуля до четырех рекурсивных вызовов algorithm и выполняет некоторый постоянный объем другой работы. Итак, если мы можем ограничить количество раз, которое algorithm вызывается, тогда мы знаем сложность. Теперь обратите внимание, что непосредственно перед каждым вызовом algorithm (за исключением первого) вы меняете элемент tempMatrix с ‘-‘ на ‘ ‘. Итак, количество вызовов алгоритма ограничено размером tempMatrix, и сложность составляет O(matrixWidth * matrixHeight) .

Другой подход (который был бы более очевиден при использовании более значимых имен переменных) заключается в простом замечании, что вы выполняете поиск в глубину по сетке x-y. И так каждый «квадрат» будет посещен один раз.