scala - 评估功能的性能

Question

“oneToEach”函数将 a 的每个元素加 1 List[Int]。第一个函数不是尾递归的，而后者是。

如果我将一百万长度的 List[Int] 传递给这两个函数，那么哪个函数的性能会更好？更好 = 更快或更少的资源使用。

// Add one to each element of a list
def oneToEach(l: List[Int]) : List[Int] =
  l match {
   case Nil => l
   case x :: xs => (x + 1) :: oneToEach(xs)
}

...

def oneToEachTR(l: List[Int]) : List[Int] =  {
  def go(l: List[Int], acc: List[Int]) : List[Int] = 
     l match {
       case Nil => acc
       case x :: xs => go(xs, acc :+ (x + 1))
     }
  go(l, List[Int]())
}

如果我理解，第一个函数的算法复杂度为 O(n)，因为有必要递归遍历列表的每个项目并加 1。

对于oneToEachTR，它使用:+运算符，我读过，它是 O(n) 复杂度。由于对列表中的每个递归/项目使用此运算符，最坏情况的算法复杂度是否变为 O(2*n)？

最后，对于百万元素列表，后一个函数是否会因为它是尾递归的而在资源方面表现更好？

Answer 1

1. 关于

   对于oneToEachTR，它使用:+运算符，我读过它是O(n)复杂的。由于对列表中的每个递归/项目使用此运算符，最坏情况的算法复杂度是否变为O(2*n)？

   不，它变成O(n^2)

2. 尾递归不会保存足够大的O(n^2)算法；100万当然够了！O(n)n

---

为什么是 O(n^2)？

• 你有一个n元素列表。
• 第一次调用:+将遍历 0 个元素（acc最初为空）并追加 1: 1 操作。
• 第二次调用将遍历 1 个元素并追加 1: 2 操作
• 第三次调用.. 2 个元素 + 追加 1：3 次操作
• ...
• 所有“操作”的总和是1 + 2 + 3 + ... + n= n(n+1)/2= (1/2)n^2 + n/2。那是“按顺序” n^2，或O(n^2)。