Morris遍历o(n)的时间复杂度如何?
|
http://geeksforgeeks.org/?p=6358
谁能解释一下莫里斯遍历的时间复杂度为
o(n)
吗?在遍历中,只要节点有左孩子,就将其副本复制到其前任的右孩子。因此,最坏的情况是必须为每个节点找到前身
while(pre->right != NULL && pre->right != current)
pre = pre->right;
哪个会增加时间复杂度?
我在这里想念什么吗?
没有找到相关结果
已邀请:
4 个回复
念炯
田眯衅
舞备联
掸牛浓疗
该循环确实增加了算法的运行时间(与该循环不在代码中相比) 但是在最坏的情况下,它添加的时间恰好是n(将运行时间从n变为2n)。最坏的情况发生在必须额外访问每个节点以查找所有先前节点的时候。顺便说一句,给定节点的每次这样的额外访问是查找前任时唯一被访问的额外时间(这是因为找到任何其他前任将永远不会遍历与查找任何其他前任所经历的相同的节点) -解释了为什么额外的时间从n-> 2n [线性]而不是n-> n ^ 2 [二次]贡献 即使2n> n,当考虑[Big-O]复杂度时,O(2n)= O(n) 换句话说,与n相比花费2n更长的时间并不是实际的额外复杂度:n和2n运行时都具有相同的O(n)复杂度[它们都是\“ linear \”] 现在,即使听起来好像我在暗示以上整个算法运行时间为2n,但实际上不是3n。 仅代码片段本身中的循环就贡献了n倍的时间 但是该算法的整体运行时间为3n,因为每个节点最多被访问3次(一次/最先“线程化”)回到它的前身(代码片段有助于实现的最终目标) ;第二次到达正常遍历(与先前的线程无关);然后是第三次/最终时间(再次发现其本身为第二次/最终时间),并且其右子指针/线程从指向当前节点的右子对象中移除(直接在打印当前节点之前) } 再一次[就像复杂度O(2n)= O(n)],复杂度O(3n)= O(n) 总结一下:是的,您的代码片段循环确实会花费时间,但不会增加时间复杂度 顺便说一句,我认为(从完整算法中)删除旧的前身“ thread”引用绝对不是必要的(尽管它不会造成伤害,并且可以认为是整理得当) :