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

在进行一些面试时，我一直在做一些练习上的问题，我对此有些好奇。例如说以下算法

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

因此，遍历每个朋友都是O（n），因为我们正在遍历所有朋友。但是子循环呢？有些朋友可能没有购买任何东西，有些朋友却购买了很多东西。您如何用Big O表示法描述运行时间？

谢谢

最佳答案

这是指定n是重要的情况之一。该算法可以定义为O（n），其中n代表购买的总数，而不是朋友的总数。

如果要将n定义为好友数，则仅n变量是不够的。迭代次数不仅取决于有多少个朋友。您可以用多种不同的方式来描述迭代次数。一种方式是说该算法为O（n * m），其中n是朋友的数量，而m是每个朋友的平均购买数量。 （如果已知m较小，例如说小于某个固定值，则可以将其转换为O（n），声称m是常数，但通常情况下并非如此。）

关于c# - 具有不同大小子循环的Big O分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25251713/