算法何时是O(n + m)时间? [英] When is an algorithm O(n + m) time?

问题描述

我正在解决此问题.我解决该问题的算法是:

I was solving this problem on Hacker rank. My algorithm to solve the problem is:

1. 获取所有玩家得分的数组.遍历所有玩家分数并创建一个新数组.总共要有n位玩家.
   不包含任何重复的玩家得分.让我们称呼新的 数组，playerScores.
2. 让爱丽丝演奏的总级别为m.
3. 让爱丽丝在第一轮之后的得分为S.
4. 让爱丽丝的初始排名R为0.
5. 从后端开始迭代playerScores数组，直到获得分数小于S的玩家分数.
6. 将R设置为在步骤5中找到的玩家的排名.
7. 将m减1.
8. 打印R.
9. 现在开始在循环内的所有后续m-1级别中处理Alice的分数

1. Get an array of all the player scores. Iterate through all player scores and create a new array. Let there be n players in all.
   which doesn't contain any repeated player scores. Let us call the new array, playerScores.
2. Let total levels to be played by Alice is m.
3. Let Alice's score after first round be S.
4. Let Alice's initial rank R be 0.
5. Start iterating playerScores array from the rear end until you get a player score whose score is less than S.
6. Set R to rank of the player found in step 5.
7. Reduce m by 1.
8. Print R.
9. Now start processing Alice's score in all subsequent m-1 levels inside a loop

1. 将S设置为爱丽丝的下一个分数.
2. 从等级为R-1的玩家开始朝前端迭代playerScores数组.
3. 继续迭代，直到获得分数小于S的玩家.
4. 将R设置为在上一步中找到的玩家的排名.
5. 将m减1.
6. 打印R.
7. 如果还有更多的要播放的级别(即m> 0)，请转到步骤9.1.

1. Set S to Alice's next level score.
2. Start iterating playerScores array from the player whose rank is R-1 towards the front end.
3. Continue iteration untill you get a player whose score is less than S.
4. Set R to rank of the player found in above step.
5. Reduce m by 1.
6. Print R.
7. Go to step 9.1 if there are more levels left to be played (i. e m>0).

现在，当我开始计算上述算法的Big O时间复杂度时，我意识到它应该是O(n)，如下所示:

Now when I started calculating the Big O time complexity of the above algorithm, I realized that it should be O(n) as below:

1. 需要进行一次扫描才能获得不重复的分数.这有助于因子n.所有分数可能都是唯一的.
2. 还需要从尾到前进行另一次扫描，以确定每个级别之后的爱丽丝排名.这再次成为因子n.在最坏的情况下，级别数(m)可以等于玩家人数(n).

加上以上两个因素，时间复杂度为O(n + n)= O(2n)= O(n).虽然我的朋友声称它是O(n + m)，但他不能解释得足够多.如果我的O(n + n)复杂度公式仍然有缺陷，谁能帮助我理解相同的内容?

Adding above two factors the time complexity comes out to be O(n + n) = O(2n) = O(n). While my friend claims it to be O(n + m) though he isn't able to explain it enough. Can anyone help me understand the same if my formulation of O(n+n) complexity is anyway flawed?

推荐答案

O(n+m)与O(n+n)或O(n)不同.可能有时n可能大于m，而其他时候m可能更大，但是没有确定的方法.但是，如果始终知道n>=m，无论如何，您都可以说O(n+m)实际上是O(n).在这种情况下，同样的规则适用.

O(n+m) is different from O(n+n) or O(n) when you don't know what would be the relation between m and n. It may be that sometimes n might be larger than m and other times m might be larger but there is no definite way to tell. If however, you always know that n>=m no matter what, you can say that O(n+m) will actually be O(n). In this case, same rule apply.

这篇关于算法何时是O(n + m)时间?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！