javascript - 我的递归函数的 Big-O 分析是什么?

标签 javascript algorithm recursion big-o

在准备技术面试时,我用递归解决了一道练习题。

像这样的递归函数的运行时复杂度是多少?我更关心解释而不是答案。

根据我的分析——操作次数将是 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/

相关文章:

c++ - 最近点算法 |如何改进?

python - 寻找最接近给定值的路径旅行成本

javascript - 带有信息窗口的 Google Maps API 多个标记

algorithm - 如何将其转换为图形算法?

javascript - 在 Meteor AutoForm SimpleSchema 中验证日期值

algorithm - 我的梯度下降算法有什么问题

java - java中递归的替代方法

JavaScript:匿名 promise 解析器函数中的递归

javascript - JS 将文本拆分成句子

javascript - 以罗马数字显示日期