从我的旧算法中找出大 O Notation/Recurrence 关系

Figuring out The Big O Notation/Recurrence Relation From My Old Algorithm

**大家好, 我对递归关系/大 O 表示法有疑问。我得到了一项家庭作业,要求我给出我为以前的家庭作业提出的一些旧代码/算法的大 O 符号。可悲的是,我还没有上过有限数学课程;所以这对我来说是新的。我设法弄清楚了我使用的四种算法中的三种。但是,我坚持使用第四种算法。该方法为递归方法,编码为Java。我真的花了好几个小时试图解决这个问题,而且我看了很多视频并阅读了很多关于大 O 表示法的文章,但遗憾的是我无法理解。任何帮助都会很棒!!! 这是代码:

ArrayList<FacebookUser> getRecommendations(FacebookUser e) {
    FacebookUser rootUser = userCallForList.get(0);


    if(rootUser.getFriends().isEmpty() || e.getFriends().isEmpty()){
        return returnHash();
    }

    for(FacebookUser hold : e.getFriends()){
        if( !hold.equals(rootUser) && addHash(hold)){
            getRecommendations(hold);   
        }
    }

    return returnHash();
}

代码注意事项: 该方法将 FacebookUser 作为参数。方法 returns 一个 ArrayList,其中包含传递给它的 FacebookUser 的所有朋友,以及对该 FacebookUser 的所有朋友调用相同的 getRecommendations 方法的结果。它不会将任何人添加到推荐列表中,如果它们已经在推荐列表中,并且不会添加调用它的 FacebookUser (E.I rootUser);因为这可能会导致无限循环。我使用 HashSet 作为我的集合,然后我必须将它改回 ArrayList。

如果我对你的代码的理解是正确的,那么这不是传统的递归,因为 n(输入大小)在每次递归调用时都会发生变化,但不一定会变小,即它不是分而治之的算法。

这条语句

for(FacebookUser hold : e.getFriends()){
        if( !hold.equals(rootUser) && addHash(hold)){
            getRecommendations(hold);   
        }
    }

为未指定数量的朋友调用 getRecommendations(),然后为每个朋友的朋友调用它。在我看来,如果您将此方法视为图问题,网络中的每个朋友或每个节点都会调用此方法。这对我来说意味着 运行 时间 O(k),其中 k = 初始用户可通过任意数量的边到达的唯一节点数。