使用尾递归的时间和 space 复杂度

Question

任何人都可以帮助我理解时间和 space 算法的复杂性来平衡括号

def isValid(s: String): Boolean = {
@annotation.tailrec
def go(i: Int, stack: List[Char]): Boolean = {
  if (i >= s.length) {
    stack.isEmpty
  } else {
    s.charAt(i) match {
      case c @ ('(' | '[' | '{')                     => go(i + 1, c +: stack)
      case ')' if stack.isEmpty || stack.head != '(' => false
      case ']' if stack.isEmpty || stack.head != '[' => false
      case '}' if stack.isEmpty || stack.head != '{' => false
      case _                                         => go(i + 1, stack.tail)
    }
  }
}
go(0, Nil)

}

根据我的理解，尾递归将 space 的复杂度降低到 0(1)，但在这里我使用 List 的附加数据结构作为累加器，谁能解释一下 space 的复杂度和可以计算时间复杂度

Answer 1

您的代码中有一个错误：您只将括号压入堆栈，但弹出所有内容，因此此实现仅适用于仅包含括号的字符串...不确定这是否是意图。通过正确的实现，它应该是时间线性的，space 复杂度也将是线性的，但不是整个字符串的长度，而是它包含的括号的数量。

    val oc = "([{" zip ")]}"
    object Open {  def unapply(c: Char) = oc.collectFirst { case (`c`, r) => r }}
    object Close { def unapply(c: Char) = oc.collectFirst { case (_, `c`) => c }}
    object ## { def unapply(s: String) = s.headOption.map { _ -> s.tail }}


    def go(s: String, stack: List[Char] = Nil): Boolean = (s, stack) match {
       case ("", Nil) => true
       case ("", _) => false
       case (Open(r) ## tail, st) => go(tail, r :: st)
       case (Close(r) ## tail, c :: st) if c == r => go(tail, st)
       case (Close(_) ## _, _) => false
       case (_ ## tail, st) => go(tail, st)
     }
    
     go(s)

（公平地说，这实际上是 space 的线性关系，因为 s.toList :) 我内心的美学家无法抗拒。如果你愿意，你可以把它变回 s.charAt(i)，它看起来不再那么漂亮了……或者使用 s.head 和 `s.

Answer 2

我认为当您将算法实现为尾递归函数与非尾递归函数或循环相反，否则每个人都会这样做。尾递归只是防止你进入会导致堆栈溢出的深层嵌套递归调用。

您当前算法的时间复杂度应为 O(n)，辅助 space 复杂度应为 O(n)，尾递归与否。

~~您仍然可以使用计数器而不是一堆括号将辅助 space 复杂度降低到 O(1)，但这与尾递归无关~~ . O(1) 辅助 space 复杂性只有在您只处理一种类型的括号时才有可能，您使用计数器而不是堆栈进行跟踪。但是，如果考虑堆栈帧大小，非尾调用优化递归可能仍会限制为 O(n)。

除了@Dima 提到的错误之外，如果我要重构您的解决方案，我会选择：

def isValid(s: String): Boolean = {
  @annotation.tailrec
  def go(l: List[Char], stack: List[Char] = Nil): Boolean = (l, stack) match {
    case ((c @ ('(' | '[' | '{')) :: cs, xs)  =>  go(cs, c :: xs)
    case (')' :: cs, '(' :: xs)               =>  go(cs, xs)
    case (']' :: cs, '[' :: xs)               =>  go(cs, xs)
    case ('}' :: cs, '{' :: xs)               =>  go(cs, xs)
    case ((')' | ']' | '}') :: _, _)          =>  false
    case (_ :: cs, xs)                        =>  go(cs, xs)
    case (Nil, xs)                            =>  xs.isEmpty
  }

  go(s.toList)
}

使用尾递归的时间和 space 复杂度

Time and space complexity using Tail recursion

scala

time-complexity

tail-recursion

space-complexity