ste*_*ecb 6 javascript iteration recursion big-o
一个月前,我接受了一些谷歌PTO成员的采访.其中一个问题是: 在js中递归反转一个字符串,并用大O表示法解释运行时间
这是我的解决方案:
function invert(s){
return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s;
}
我觉得很简单.
而且,关于大写符号,我很快回答了O(n),因为运行时间线性地取决于输入. - 沉默 - 然后,他问我,如果你通过迭代实现它,在运行时间方面有什么不同？
我回答有时编译器将递归"转换"为迭代(一些编程语言课程记忆),因此在这种情况下迭代和递归没有差异.顺便说一句,因为我没有对这个特定问题的反馈,并且面试官没有回答"好"或"不",我想知道你是否同意我或者你是否可以解释我是否可能存在差异2种实现.
非常感谢和问候!
你的解决方案对我来说看起来是 O( n \xc2\xb2) 。调用substring很可能是 O( n ) \xe2\x80\x94 ，典型的实现将为新字符串分配空间，然后复制子字符串。[但请参阅注释。] 字符串连接+也可能是 O( n )。甚至可能length是 O( n ) 的情况，但我认为这不太可能。
您提出了编译器可以将递归转换为迭代的想法。这是事实，但它很少在函数式语言和Scheme之外实现；通常，唯一应用的转换是尾递归消除。在您的代码中，递归不在尾部位置：在递归调用之后invert，您仍然需要计算+. 因此尾递归消除不适用于您的代码。
invert这意味着必须以不同的方式实现迭代版本。它可能具有相同或不同的复杂性，在我们看到它之前我们不能说。