3

这个的时间和空间复杂度是多少：

def isPalindrome[A](x: Seq[A]): Boolean = x match {
  case h +: middle :+ t => h == t && isPalindrome(middle)
  case _ => true
}

是否取决于实施Seq？既然IndexedSeq应该有O(1)tail vs O(n)for LinearSeqs？空间复杂度是O(n)因为递归调用堆栈还是 Scala 自动进行尾调用优化？

import scala.annotation.tailrec

@tailrec def isPalindrome[A](x: Seq[A]): Boolean = x match {
  case h +: middle :+ t => h == t && isPalindrome(middle)
  case _ => true
}
4

1 回答 1

1

它是否取决于 Seq 的实现？既然 IndexedSeq 对于 LinearSeqs 应该有 O(1) tail vs O(n)？

我通常会这样认为，但提取器实际上是O(n). Seqany的提取器scala.collection.:+是O(n)列表的最后一个和O(n)最后一个。这两个的代码如下：

  def init: Repr = {
    if (isEmpty) throw new UnsupportedOperationException("empty.init")
    var lst = head
    var follow = false
    val b = newBuilder
    b.sizeHint(this, -1)
    for (x <- this) { // O(n)
      if (follow) b += lst
      else follow = true
      lst = x
    }
    b.result
  }

  def last: A = {
    var lst = head
    for (x <- this) // O(n)
      lst = x
    lst
  }

由于递归调用堆栈，空间复杂度是 O(n) 还是 Scala 会自动进行尾调用优化？

我看到代码确实有这种优化。这是有道理的，因为它t && isPalindrome(middle)允许 Scala 关闭当前调用堆栈，传递t到下一个要&&编辑的堆栈，因此它可以进行尾递归优化。

恒定时间匹配

使用Vector我们可以实现O(1)时间：

object ends {
  def unapply[T](t: Vector[T]): Option[(T, Vector[T], T)] =
    if (t.length < 2) None
    else Some((t.head, t.drop(1).dropRight(1), t.last))
}

def isPalindrome[A](x: Vector[A]): Boolean = x match {
  case ends(i, middle, l) => i == l && isPalindrome(middle)
  case _ => true
}
于 2015-07-08T21:29:30.553 回答