Определение времени и пространства сложности - PullRequest
Новая
       25

Определение времени и пространства сложности

3 голосов
/ 17 января 2010

У меня проблемы с определением пространственно-временных сложностей. Например, если у меня есть дерево с коэффициентом ветвления b и глубиной d , как я могу рассчитать временные и пространственные сложности? Я знаю, что это O (b ^ d) и O (bd), но моя проблема в том, как добраться до этих значений.

Спасибо!

Ответы [ 2 ]

6 голосов
/ 26 февраля 2012

Время

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

nodes          b=2                        b=3
b^0             *                          *
              /   \               /        |        \
b^1          *     *             *         *         *
            / \   / \         /  |  \   /  |  \   /  |  \
b^2        *   * *   *       *   *   * *   *   * *   *   * 
               ...                        ...

Как видно на рисунке, для расчета первого уровня стоит c*b^0 стоимость - в точности c. Следующий уровень в дереве будет содержать b^1 узлов, а генерация второго уровня будет стоить c*b^1 = c*b. Для третьего уровня снова будет b узлов для каждого узла на втором уровне, это означает b*b^1 = b^2$ узлов и стоимость c*b^2.

На самом глубоком уровне дерева на глубине d будет b^d узлов, работа на этом уровне для этого будет c*b^d. Общий объем проделанной работы к этому моменту составляет c*b^0 + c*b^1 + ... + c*b^d. Для сложности мы смотрим только на самый быстро растущий член и отбрасываем константу, чтобы получить:

O(c + c*b + ... + c*b^d) = O(c*b^d) = O(b^d).

По существу : время является функцией f(d) = SUM(i=1..d){c*b^i} и O(f(d)) = O(b^d).

Space

На рисунке показан алгоритм на разных этапах для b=3. * обозначает развернутые в данный момент узлы, ? обозначает неизвестные узлы, а + обозначает узлы, оценка которых была полностью рассчитана. 

                    branching factor b = 3                     space
         *             *             *             *             b
       / | \         / | \         / | \         / | \         
      *  ?  ?       *  ?  ?       +  *  ?       +  +  *          b
    / | \         / | \            / | \            / | \      
   *  ?  ?       +  +  *          +  *  ?          +  +  *       b
 / | \               / | \         / | \               / | \   
*  ?  ?             +  *  ?       +  *  ?             +  +  *    b

Чтобы вычислить оценку узла, вы расширяете узел, выбираете дочерний элемент и рекурсивно расширяетесь, пока не достигнете конечного узла на глубине d. Как только дочерний узел полностью рассчитан, вы переходите к следующему дочернему узлу. Как только все b дочерние узлы вычислены, оценка родителей рассчитывается на основе дочерних узлов, и в этот момент дочерние узлы могут быть удалены из хранилища. Это показано на рисунке выше, где алгоритм показан на 4 разных этапах.

В любой момент у вас есть один раскрытый путь, и вам нужно c*b хранилище для хранения всех дочерних узлов на каждом уровне. Здесь снова предполагается, что вам нужно постоянное количество места на узел. Ключ в том, что любое поддерево можно обобщить по его корню. Поскольку максимальная длина пути равна d, вам максимально потребуется c*b*d пространства. Как и выше, мы можем отбросить постоянные условия и получить O(c*b*d) = O(b*d).

4 голосов
/ 17 января 2010

Пространство сложность составляет «сколько памяти мне нужно выделить для этого алгоритма». Сложность времени составляет «сколько времени потребуется для выполнения (в абстрактном смысле»).

Дерево с коэффициентом ветвления b и глубиной d будет иметь один узел на нулевом уровне, b узлов на своем первом уровне, b * b = b ^ 2 узлов на своем втором уровне, b ^ 2 * b = b ^ 3 на третьем уровне и т. д. На этих четырех уровнях (глубина 3) он имеет 1 + b + b ^ 2 + b ^ 3. С точки зрения сложности мы сохраняем только член высшего порядка и обычно отбрасываем любые умножающие константы. Таким образом, вы получите сложность O (b ^ d) для сложности пространства.

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

Я собираюсь выйти на конечность и предположить, что вы говорите о IDDFS. Объяснение того, откуда приходят O (b ^ d) и O (bd), хорошо объяснено в этой вики-статье.

...