从我的旧算法中找出大 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 = 初始用户可通过任意数量的边到达的唯一节点数。
**大家好, 我对递归关系/大 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 = 初始用户可通过任意数量的边到达的唯一节点数。