algorithm - 这个函数的大Θ分析是什么？

Question

public SomeObject secondFunction(SomeObject obj) {

    SomeObject retVal = new SomeObject

    for data in this.dataCollection {
        for data2 in obj.dataCollection {
            if(someCondition) { 
                retVal.add(data) 
            }
        }
    }

    return retVal
}

我正在尝试学习算法分析。什么是大 Θ 分析这个功能的实现？为什么/如何？

我不认为这是一个 n 平方算法，因为被循环的两个结构可能具有不同的大小。直觉上，我想称它为 n*m 算法，因为 obj、dataCollection 和 this.dataCollection 中的元素数量都是未知数。但我以前从未见过这种措辞，所以它可能是错误的。这是什么？

此外，关于最佳情况、最坏情况和平均情况，我们能说些什么？看起来最好和最坏的情况是一样的，因为它每次都会遍历两个结构中的所有元素。这是正确的还是错误的？另外，这对一般情况意味着什么？在这个特定示例中，平均情况是否与最佳和最差情况相同？

Answer 1

您的直觉是正确的 - 将其称为 Θ(n * m) 实现是有效的，假设内部循环的主体需要恒定时间(并且执行实际迭代的时间是微不足道的)。

至于最佳/最差/平均情况:同样，假设内部循环的主体花费常数时间，然后在一个常数因子内，它们都将是相同的。