大O分析与不同大小的子循环

Question

我一直在为一些采访做一些练习问题,我对某些事感到好奇.例如,在以下算法中说

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

所以,通过每个朋友是O(n),因为我们正在遍历所有的朋友.但是子循环怎么样？有些朋友可能没有购买任何东西,有些朋友已经购买了很多东西.您如何描述Big O Notation中的运行时间？

谢谢

Answer 1

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

如果你想定义n为朋友的数量,那么n单独的变量是不够的.迭代次数不仅取决于有多少朋友.您可以通过不同的方式描述迭代次数; 一种方法是说这个算法是O(n*m),其中n是朋友的数量,m是每个朋友的平均购买数量.(如果m已知是小的,比如说小于某个固定值,则可以将其转换为O(n),声称这m是常数,但在一般情况下则不然.)