算法是否为O(n + m)时间？

Question

我在Hacker排名上解决了这个问题.我解决问题的算法是:

1. 获取所有玩家分数的数组.迭代所有玩家得分并创建一个新阵列.总共有n个玩家.
   其中不包含任何重复的玩家分数.让我们调用新的数组,playerScores.
2. 让Alice玩的总等级是m.
3. 让Alice在第一轮比赛后得分为S.
4. 让Alice的初始等级R为0.
5. 从后端开始迭代playerScores数组,直到获得分数小于S的玩家得分.
6. 将R设置为在步骤5中找到的玩家的等级.
7. 将m减少1.
8. 打印R.
9. 现在开始在循环内的所有后续m-1级别中处理Alice的得分
   1. 将S设置为Alice的下一级别分数.
   2. 开始从排名为R-1的玩家向前端迭代playerScores数组.
   3. 继续迭代,直到你得到一个得分低于S的球员.
   4. 将R设置为上一步中找到的玩家的等级.
   5. 将m减少1.
   6. 打印R.
   7. 如果还有更多级别要播放,请转到步骤9.1(即m> 0).

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

1. 需要一次扫描才能获得非重复分数.这有助于因子n.所有分数都可能是唯一的.
2. 从尾部到前部的另一次扫描需要在每个级别之后决定Alice的等级.这再次导致因子n.在最坏的情况下,级别数(m)可以等于玩家数量(n).

加上上述两个因素,时间复杂度为O(n + n)= O(2n)= O(n).虽然我的朋友声称它是O(n + m)虽然他无法解释它.如果我的O(n + n)复杂度的公式无论如何都有缺陷,任何人都可以帮助我理解它吗？

Answer 1

O(n+m)不同于O(n+n)或O(n)何时你不知道m和之间的关系是什么n.可能有时n可能会比较大,m而其他时间m可能会更大,但没有明确的方法可以说明.但是,如果你总是知道n>=m无论如何,你可以说O(n+m)实际上是O(n).在这种情况下,适用相同的规则.