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

Question

**大家好，我对递归关系/大 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。

Answer 1

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

这条语句

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

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

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

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

java

recursion

big-o

recurrence