Временная сложность обхода дерева на основе стека - PullRequest
Новая
       14

Временная сложность обхода дерева на основе стека

3 голосов
/ 18 марта 2011

Какова временная сложность реализации обхода двоичного дерева ниже? 

void Tree::nonRecInOrder()
{
    // nonrecursive inOrder Traversal using Stack
    Stack< TreeNode* > s ; // declare and initialize stack
    TreeNode* currentNode = root ;

    while( true )
    {
        while( currentNode )
        {
            // move down leftChild fields
            s.add( currentNode ) ;
            currentNode = currentNode->leftChild ;
        }

         if( ! s.isEmpty() ) // stack is not empty
         {
             currentNode = *s.del( currentNode ) ; // delete from stack
             cout << currentNode->data ;
             currentNode = currentNode->rightChild ;
         }
         else
         {
            break ;
         }
    }    
}

Не могли бы вы также объяснить, как вычислить сложность?

1 Ответ

4 голосов
/ 18 марта 2011

Один из способов охарактеризовать сложность функции big-O сложной функции - подумать о каком-то ресурсе, к которому она обращается, а затем ограничить число обращений к этому ресурсу.В этом случае, когда вы выполняете обход дерева, вы можете подумать о том, сколько раз каждый узел выталкивается или выталкивается из стека.Причина того, что это хорошая граница, заключается в том, что вся сложная работа этой функции - внутренний цикл, спускающийся вниз по цепочке узлов, и внешний цикл, обрабатывающий самый верхний в стеке - может быть ограничен числом нажатий узлана стек или выскочил из стека.Это связано с тем, что самый внешний цикл завершается, когда стек пуст, поэтому он не может запускаться больше раз, чем в стек помещается что-то, и самый внутренний цикл работает пропорционально числу раз, когда что-то помещается в стек надКонечно, цикл.

Итак, давайте посмотрим, как мы можем связать эти величины.Первый вопрос - сколько раз каждый узел может быть добавлен в стек.Что ж, узел добавляется в стек только в том случае, если он или один из его предков по левостороннему пути является текущим узлом, когда цикл начинает выполняться.Сколько раз это может случиться?Я утверждаю, что это происходит не более одного раза.Доказательством этого является индукция, основанная на глубине узла в дереве.Мы используем наблюдение, что узел выбирается снова как текущий узел, только если он является прямым правым потомком узла в стеке.В качестве базового случая индукции, если узел является корнем (он находится на нулевой глубине), то он не может быть выбран во второй раз, потому что у него нет родителя.Для индуктивного шага, если верно, что ни один узел на глубине d не может быть выбран в качестве текущего узла дважды, то ни один узел на глубине d + 1 не может быть выбран дважды, потому что узлы на глубине d + 1 выбираются, только если выбраны их родителиопять же, но по индуктивному предположению мы знаем, что это не так.Следовательно, мы имеем, что ни один узел никогда не выбирается в качестве текущего узла дважды.Мы следуем за этим простым наблюдением, что ни один узел, который является левым потомком, никогда не может быть текущим узлом в начале цикла, так как текущий узел является либо корнем (не левым потомком), ни правым потомком какого-либо узла.,Это утверждение в сочетании с тем фактом, что ни один узел не посещается дважды, означает, что узел добавляется в очередь не более одного раза, что происходит, когда его верхний левый предок становится текущим узлом.

Это также дает намограничение на количество возможных очередей, поскольку количество очередей не может превышать количество очередей.Поскольку каждый узел ставится в очередь не более одного раза, он также удаляется не более одного раза.Чтобы закончить, мы знаем, что сложность всей функции ограничена числом выполненных очередей и очередей, и поэтому сложность равна O (n), где n - количество узлов.

Whew!Это было не весело анализировать.Мне больше нравится рекурсивная версия.: -)

...