需要伪代码的复杂性
我需要确定我编写的伪代码的复杂性
while root ≠ null
while hasChild(root)
push(parentTree) ← root
root ← pop(getChilds(root))
...
is parentTree isEmpty
root ← null
else
root ← pop(parentTree)
如何知道最坏情况下的执行次数（每行）？
我无法确定它，因为我实际上不知道前两行。之后，很容易，但我不知道前两行的计数...
这是一个使用堆栈的树实现，root 是根节点，如您所见。
顺便说一句，这是我第一次写伪代码，所以我不确定我写得好不好。如果不正确，我可以重写。
I need to determine the complexity of the pseudocode I wrote
while root ≠ null
while hasChild(root)
push(parentTree) ← root
root ← pop(getChilds(root))
...
is parentTree isEmpty
root ← null
else
root ← pop(parentTree)
How can I know the number of execution (for each line) in a worst case scenario ?
I am not able to determine it, because I actually does not know the first two lines. After, it's easy, but I don't know the count for the two first lines...
It's a tree implementation using a stack, and root is the root node, as you see.
By the way, it's the first time I write pseudo code, so I am not sure i wrote it in a good way. If it's not correct, I can rewrite it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
初步分析让我认为运行时间是 O(logn*logn)
推理：
外部 while 循环最多执行 clon 次（其中 c 是常量）。这是因为它依赖于“root”变量，而“root”变量又依赖于“pop Parenttree”
父树仅迭代地填充“原始”根的孙子树。最多它会让所有的孩子沿着树中的一条路径走。已知树上单条路径的长度为 logn
内部 while 循环最多也执行 d logn 次（d 是常数），如果...不执行 O(1)那么它将在 dlogn+X 中执行，总体运行时间将为 O(logn*(logn+X))，可能简化为
O(Xlogn)假设是是一个如果，则if/else 语句的运行时间复杂度为 O(1)
Outer*Inner = O(clogn*dlogn)
prima facie analysis leads me to think the runtime is
O(logn*logn)Reasoning:
Outer while loop executes at most clogn times (where c is a constant). This is due to the fact that it relies on the 'root' variable, which in turn relies on the 'pop parenttree'
parent tree only gets populated with the 'original' root's grandchildren, iteratively. At most it will have all the children down one path in the tree. Its known that the length of a single path down a tree is logn
Inner while loop also executes at most d logn times (d is constant), if the ... does not execute in O(1) then it would execute in dlogn+X, and the overall runtime would be O(logn*(logn+X)), likely simplifying to
O(Xlogn)Assuming the is is an if, the if/else statements run in O(1)
Outer*Inner = O(clogn*dlogn)