使用尾递归的时间和空间复杂度 [英] Time and space complexity using Tail recursion

问题描述

谁能帮我理解算法的时间和空间复杂度来平衡括号

Can anyone please help me to understand the time and space complexity of algo to balance parenthesis

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)

}

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

As per my undertanding, tail recursion reduces space to 0(1) complexity but here I am using additional data structure of List as accumulator, can anyone please explain how the space complexity and time complexity can be calculated

推荐答案

您的代码中存在一个错误:您仅在堆栈上推送括号，但弹出所有内容，因此此实现仅适用于only 包含括号......不确定这是否是意图.如果实现得当，它在时间上应该是线性的，空间复杂度也是线性的，但不是在整个字符串的长度上，只在它包含的括号数上.

There is a bug in your code: you are pushing only parentheses on stack, but pop everything, so this implementation only works for strings that only contain parentheses ... not sure if that was the intent. With the proper implementation, it should be liner in time, and the space complexity would be linear too, but not on the length of the entire string, only on the number of parentheses it contains.

    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)

(公平地说，由于s.toList，这实际上在空间上是线性的:)我内心的审美无法抗拒.如果你愿意，你可以把它改回 s.charAt(i) ，它看起来不再那么漂亮了......或者使用 s.head 和`s.

(to be fair, this is actually linear in space because of s.toList :) The esthete inside me couldn't resist. You can turn it back to s.charAt(i) if you'd like, it just wouldn't look as pretty anymore ... or use s.head and `s.

这篇关于使用尾递归的时间和空间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！