分析嵌套for循环的运行时

Question

我有一些问题，确定这个嵌套的for循环是在O(n)还是O(n^2)中运行。

假设我有一个表演P的列表，每个表演都有一个持续时间(小时数)。

P = [P1, P2, ...., Pn]
for p in P:
    for hour in p.hours:
        //do stuff here
    end
end

什么是运行时间呢？我知道执行的总数是每个性能或O(totalHours)中所有小时的总和，但这是线性的还是多项式的？请记住，小时数可能因性能而异，可以任意大或小。

Answer 1

我可能会说它是O(mn)，其中n是性能的数量，m是每个性能的平均小时数(或者，如您所说的O(totalHours))。

它与总小时数成线性关系。

因为它不仅取决于性能的数量，我不相信你可以说它是线性的(甚至多项式)(即使n的力量在上面的复杂性是1 )(但是这里的观点可能不同)。

Answer 2

它与输入的总小时数成线性关系。如果不能将该数字表示为性能数的函数，则无法将运行时间与性能数量联系起来。