我正在嘗試估計以下解決方案的 Big-O 時間和空間復雜度，以解決一個微不足道的二和問題。在我的理解中，tailrec 遞回應該是一個更好的解決方案，但是當我嘗試確定復雜性時，看起來它們都有 O(n) 的時間和 O(n) 的空間。
inputArray = Array(4, 6, 5)
sumToCheck = 9
import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer
def checkTwoSum(inputArray: Array[Int], sumToCheck: Int): Boolean = {
val subtractList: ListBuffer[Int] = ListBuffer.empty
var output = false
for (i <- inputArray.indices) {
if (subtractList.contains(inputArray(i))) {
output = true
}
else {
subtractList = sumToCheck - inputArray(i)
}
}
output
}
def checkTwoSumRec(inputArray: Array[Int], sumToCheck: Int): Boolean = {
@tailrec
def inner(input: Array[Int], subtractList: Array[Int] = Array.emptyIntArray): Boolean = {
if (input.isEmpty) {
false
}
else if (subtractList.contains(Option(input.head).getOrElse(0))) {
true
}
else {
inner(input.tail, subtractList : (sumToCheck - Option(input.head).getOrElse(0)))
}
}
inner(inputArray)
}
如果這是真的，有人可以給個提示嗎？
uj5u.com熱心網友回復：
這里有幾件事：
- 這兩種解決方案都是
O(n^2)時間復雜度。請注意，contains在串列上是O(n)，并且由于您可以n多次使用它，因此復雜性變為O(n*n). 更快的解決方案應該使用Map. - 尾遞回通常更好，因為它是撰寫代碼的更好方式，即更難出錯。因此，遞回與迭代更多地是關于代碼的可維護性和可讀性，而不是關于速度。（在 Scala 中，尾遞回函式被重寫為
while回圈） Option(input.head).getOrElse(0)不安全。input.head拋出一個NoSuchElementException空串列。因此，如果您確定它input是非空的，那么只需使用input.head，如果您不確定，那么使用input.headOption和模式匹配就可以了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/507833.html
下一篇：網格搜索問題的最大遞回深度誤差