以下解决方案的时间和 space 复杂度是多少

Question

您好，我编写了以下代码来查找与目标总和相匹配的第一对数字。我对 BigO 符号有一个很好的想法，但我发现在下面的场景中很难。

fun twoNumberSum(array: MutableList<Int>, targetSum: Int): List<Int> {
    val end = array.size-1
    var i=0
    while(i <= end){    
        val firstNum = array[i]
        var j = i+1
        while(j <= end){
            val secondNum = array[j]
            if(firstNum + secondNum == targetSum){
             return listOf(firstNum,secondNum)  
            }
            j++
        }
        i++
    }

    return listOf<Int>()
}

我认为的另一种解决方案是首先对数组进行排序并对其进行迭代大约 O(nlog(n)T 和 O(1)S.. 哪个是优化的？

Answer 1

您代码的 时间复杂度 是 O(n^2)。这是您的代码：

val end = array.size-1
var i=0

//It should be end-1 
while(i <= end-1)
{    
    val firstNum = array[i]
    var j = i+1
   
    while(j <= end)
    {
        val secondNum = array[j]
        if(firstNum + secondNum == targetSum) return listOf(firstNum,secondNum)  
    
        j++
    }

    i++
}

您有一个 外循环 运行 n-1 次，其中 n 是输入数组的 长度。让我们看看内循环执行了多少次：

如果对 j 循环执行的次数求和，您将得到一个函数，该函数显示 具有 n 的函数增长率：

= 1 + 2 + 3 + 4 + 5 + ... + n-2 + n - 1 
= (n-1)*(n-2)/2
= (n^2 - 3n + 2)/2

忽略常量和低阶项3n，因为当它们足够大时它们将无关紧要。我们得到时间复杂度 共 O(n^2)。

由于您只使用了 三个额外的变量，您代码的 space 复杂度 为 O(1)。

您问题的答案：

Another solution I would think is first to sort the array and iterate over it approximately O(n*log(n)T and O(1)S.. Which one would be the optimized one?

是的，对于您的问题，存在一个 时间复杂度 为 O(n*log n) 的解决方案。这是相当流行的解决方案。它可以在线获得。它使用 Two-Pointer technique.

space 复杂度会发生变化，这取决于您使用的排序算法的类型。

希望对您有所帮助。 如果你对我的解释有任何疑问，请发表评论。

以下解决方案的时间和 space 复杂度是多少

What is the Time And space complexity for below solution

algorithm

big-o

data-structures

kotlin