在准备技术面试时,我用递归解决了一道练习题。
像这样的递归函数的运行时复杂度是多少?我更关心解释而不是答案。
根据我的分析——操作次数将是 n 的一半。也就是说,在最坏的情况下,一个 10 个字符的字符串将进行 5 次函数调用。但我从未见过 O(n/2) 运行时。此外,我的分析排除了对辅助函数 counterpartOf
的调用。有人可以给我一个正确的分析吗?
Write a function that accepts a string consisting of brackets ({}) and returns whether it is balanced.
function checkBraces(input){
// start at the center and work outwards, recursively
var c = input.length / 2;
if (input.charAt(c) !== counterpartOf(input.charAt(c-1))) {
var match = false;
return match;
} else {
// if only 2 characters are left, all braces matched
if (input.length === 2){
var match = true;
return match;
} else {
input = input.substring(0,c-1) + input.substring(c+1,input.length);
return checkBraces(input);
}
}
return match;
}
function counterpartOf(brace){
closing = ['}', ')', ']'];
opening = ['{', '(', '['];
var i = opening.indexOf(brace);
var counterpart = closing[i];
return counterpart;
}
最佳答案
常量无关紧要,这就是为什么您不会看到/2、*2 或类似内容的原因。
详细信息:
http://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant
O(k*g) = O(g) 如果 k 不为零。
否则,正如 Yevgeniy.Chernobrivets 提到的,您的算法不准确。但除了他的评论,我认为还有其他问题。
通常对于类似的任务,他们使用下推自动机。关于这个问题有一些理论背景:http://people.cs.clemson.edu/~goddard/texts/theoryOfComputation/7.pdf
关于javascript - 我的递归函数的 Big-O 分析是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23568381/