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

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
}

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

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

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

Answer 1

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

至于 best/worse/average 情况：同样，假设内部循环的主体花费常数时间，然后在一个常数因子内，它们都是相同的。

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

What is the Big Θ analysis of this function?

algorithm

big-o

big-theta