performance - 分析嵌套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 在上面的复杂性中)(但意见可能会有所不同)。