нужна сложность псевдокода

Мне нужно определить сложность псевдокода, который я написал

while root ≠ null
    while hasChild(root)
        push(parentTree) ← root
        root ← pop(getChilds(root))
        ...
    is parentTree isEmpty
        root ← null
    else    
        root ← pop(parentTree)

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

Я не могу это определить, потому что фактически не знаю первых двух строк. Дальше все просто, но я не знаю счет двух первых строк...

Это реализация дерева с использованием стека, а root, как вы видите, является корневым узлом.

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


complexity-theory pseudocode
person Pier-Alexandre Bouchard    schedule 01.02.2012    source источник
comment
Каково общее название функции? Что означает поп(вар)? обычно поп - это просто поп(). В то время как псевдокод дает вам некоторую свободу действий в определении вещей (или не в их определении...), когда что-то появляется совершенно неожиданно, например, unique[] и insertLegend, трудно догадаться, что происходит.   -  person Abdul Hfuda    schedule 01.02.2012
comment
Убираю легенду возврата. На самом деле это часть большого алгоритма, который мне нужно проанализировать. Мне просто нужно количество первых двух строк. Я не знаю, как это определить.   -  person Pier-Alexandre Bouchard    schedule 01.02.2012
comment
Я удаляю части, которые вам не нужно понимать. root имеет дочерние элементы, и его дочерние элементы также имеют дочерние элементы. Таким образом, pop(getChilds(root)) на самом деле является root.getChilds().pop(), первым дочерним элементом корневого дочернего элемента. И push(parentTree) заключается в том, что мне нужно нажать узел в родительском дереве, здесь parentTree.   -  person Pier-Alexandre Bouchard    schedule 01.02.2012

Ответы (1)


arrow_upward
0
arrow_downward

анализ prima facie заставляет меня думать, что время выполнения O(logn*logn)

Обоснование: внешний цикл while выполняется не более clogn раз (где c — константа). Это связано с тем, что он зависит от переменной «root», которая, в свою очередь, зависит от родительского дерева «pop parenttree», которое итеративно заполняется только внуками «исходного» корня. В лучшем случае все дети будут идти по одному пути в дереве. Известно, что длина одного пути вниз по дереву равна logn.

Внутренний цикл while также выполняется не более d logn раз (d является константой), если ... не выполняется за O(1), тогда он будет выполняться за dlogn+X, а общее время выполнения будет O(logn*(logn+X)), что, вероятно, упростится до O(Xlogn)

Предполагая, что это if, операторы if/else выполняются в O (1)

Внешний * Внутренний = O(clon*dlogn)

person Abdul Hfuda    schedule 01.02.2012