c# - 具有不同大小子循环的大 O 分析

Question

我一直在为即将到来的一些面试做一些练习题，我对一些事情很好奇。比如说，在下面的算法中

foreach(User friend in friends) 
{
    foreach(Purchase purchase in friend.Purchases)
    {
        allFriendsPurchases.Add(purchase);
    }
}

因此，遍历每个 friend 的时间复杂度为 O(n)，因为我们要遍历所有 friend 。但是子循环呢？有些 friend 可能什么都没买，有些 friend 已经买了很多。你会如何描述大 O 表示法中的运行时间？

谢谢

Answer 1

这是指定n 是什么很重要的情况之一。该算法可以定义为 O(n) ，其中 n 表示购买总数，而不是好友总数。

如果您想将n 定义为 friend 的数量，那么仅n 是不够的变量。迭代次数不仅取决于有多少 friend 。您可以通过不同的方式来描述迭代次数；一种方式是说此算法是 O(n*m)，其中 n 是 friend 的数量，m 是每个 friend 的平均购买次数。 (如果已知 m 很小，比如说小于某个固定值，那么您可以将其转换为 O(n)，声称 m 是常量，但那不是在一般情况下是正确的。)