我在黑客级别上解决了这个问题。我解决问题的算法是:
获取所有玩家分数的数组。遍历所有玩家分数并创建一个新数组。总共有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),如下所示:
将以上两个因素相加,时间复杂度为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)
O(n+n)
O(n)
m
n
n>=m