算法何时是O（n + m）时间？
我在黑客级别上解决了这个问题。我解决问题的算法是：
- 获取所有玩家分数的数组。遍历所有玩家分数并创建一个新数组。总共有n位玩家。
不包含任何重复的玩家得分。让我们将新数组称为playerScores。
- 让爱丽丝演奏的总级别为m。
- 让爱丽丝在第一轮后的得分为S。
- 令爱丽丝的初始等级R为0。
- 从后端开始迭代playerScores数组，直到获得分数小于S的玩家分数。
- 将R设置为在步骤5中找到的玩家等级。
- 将m减1。
- 打印R。
- 现在开始在循环内的所有后续m-1级中处理爱丽丝的分数
- 将S设置为爱丽丝的下一个分数。
- 从等级为R-1的播放器向前端开始迭代playerScores数组。
- 继续迭代，直到获得分数小于S的玩家。
- 将R设置为在上述步骤中找到的玩家的等级。
- 将m减1。
- 打印R。
- 如果还有更多级别需要播放（即m> 0），请转到步骤9.1。
现在，当我开始计算上述算法的Big O时间复杂度时，我意识到应该是O（n），如下所示：
- 需要进行一次扫描才能获得不重复的分数。这有助于因子n。所有分数可能都是唯一的。
- 需要从尾到前进行另一次扫描，以确定每个级别之后的爱丽丝排名。这再次成为因子n。在最坏的情况下，级别数（m）可以等于玩家数（n）。
将以上两个因素相加，时间复杂度为O（n + n）= O（2n）= O（n）。虽然我的朋友声称它是O（n + m），但他不能解释得足够多。如果我的O（n +
n）复杂度公式有缺陷，谁能帮助我理解相同的内容？
回答：
O(n+m)与O(n+n)或O(n)不知道m和之间的关系是不同的n。有时n可能会大于，m而有时m可能会更大，但没有确定的方法。但是，如果您始终知道无论如何，您都n>=m可以说O(n+m)实际上是O(n)。在这种情况下，适用相同的规则。
以上是 算法何时是O（n + m）时间？ 的全部内容， 来源链接： utcz.com/qa/413519.html
