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

Question

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

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

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

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

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

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

Answer 1

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

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

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

При условииis is if, оператор if / else выполняется в O (1)

Outer * Inner = O (clogn * dlogn)