scala - 评估职能绩效

Question

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

如果我将一个一百万长度的 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，它使用 :+ 运算符，我已经read ，是 O(n) 复杂度。由于对列表中的每个递归/项目使用此运算符，最坏情况的算法复杂度是否会变为 O(2*n)？

最后，对于百万元素列表，后一个函数由于是尾递归，因此在资源方面会表现更好吗？

Answer 1

1. 关于

   For oneToEachTR, it uses the :+ operator, which, I've read, is O(n) complexity. As a result of using this operator per recursion/item in the list, does the worst-case algorithm complexity become O(2*n)?

   不，它变成了O(n^2)

2. 尾递归不会保存 O(n^2)算法对比O(n)对于足够大的n ; 100万当然够了!

---

为什么是 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) .