一尘不染

算法何时是O(n + m)时间?

algorithm

我在黑客级别上解决了这个问题。我解决问题的算法是:

  1. 获取所有玩家分数的数组。遍历所有玩家分数并创建一个新数组。总共有n位玩家。
    不包含任何重复的玩家得分。让我们将新数组称为playerScores。
  2. 让爱丽丝演奏的总级别为m。
  3. 让爱丽丝在第一轮后的得分为S。
  4. 令爱丽丝的初始等级R为0。
  5. 从后端开始迭代playerScores数组,直到获得分数小于S的玩家分数。
  6. 将R设置为在步骤5中找到的玩家等级。
  7. 将m减1。
  8. 打印R。
  9. 现在开始在循环内的所有后续m-1级中处理爱丽丝的分数
    1. 将S设置为爱丽丝的下一个分数。
    2. 从等级为R-1的播放器向前端开始迭代playerScores数组。
    3. 继续迭代,直到获得分数小于S的玩家。
    4. 将R设置为在上述步骤中找到的玩家的等级。
    5. 将m减1。
    6. 打印R。
    7. 如果还有更多级别需要播放(即m> 0),请转到步骤9.1。

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

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

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


阅读 468

收藏
2020-07-28

共1个答案

一尘不染

O(n+m)O(n+n)O(n)不知道m和之间的关系是不同的n。有时n可能会大于,m而有时m可能会更大,但没有确定的方法。但是,如果您始终知道无论如何,您都n>=m可以说O(n+m)实际上是O(n)。在这种情况下,适用相同的规则。

2020-07-28