什么时候算法是 O(n + m) 时间？
When is an algorithm O(n + m) time?
我正在 this problem 解决 Hacker 等级问题。我解决问题的算法是：
- 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.
- Let total levels to be played by Alice is m.
- Let Alice's score after first round be S.
- Let Alice's initial rank R be 0.
- Start iterating playerScores array from the rear end until you get a player score whose score is less than S.
- Set R to rank of the player found in step 5.
- Reduce m by 1.
- Print R.
- Now start processing Alice's score in all subsequent m-1 levels inside a loop
- Set S to Alice's next level score.
- Start iterating playerScores array from the player whose rank is R-1 towards the front end.
- Continue iteration untill you get a player whose score is less than S.
- Set R to rank of the player found in above step.
- Reduce m by 1.
- Print R.
- Go to step 9.1 if there are more levels left to be played (i. e m>0).
现在当我开始计算上述算法的Big O时间复杂度时，我意识到它应该是O(n)如下：
- 需要一次扫描才能获得不重复的分数。这有助于因素 n。有可能所有分数都是唯一的。
- 需要从尾到前再扫描一次，以确定爱丽丝在每个级别后的排名。这再次影响因素 n。在最坏的情况下，级别数 (m) 可以等于玩家数 (n)。
将以上两个因素相加，时间复杂度为 O(n + n) = O(2n) = O(n)。虽然我的朋友声称它是 O(n + m)，但他无法解释清楚。如果我对 O(n+n) 复杂度的表述有缺陷，谁能帮我理解同样的问题？
当您不知道 m 和 n 之间的关系时，O(n+m) 不同于 O(n+n) 或 O(n)。可能有时 n 可能比 m 大，有时 m 可能更大，但没有明确的方法可以判断。但是，如果您无论如何都知道 n>=m，那么您可以说 O(n+m) 实际上就是 O(n)。在这种情况下，同样的规则适用。
我能够从相关人员那里得到回复。引用 Ryan Fehr 的话：
For this problem, O(n+n) and O(n+m) are essentially the same thing,
because they both have the same upper bound. I decided to go for the
O(n+m) representation because it makes sure that it is apparent that
my solution is dependent on the number of levels Alice beat that is
represented by m in this case.
An example where this differentiation is important is when we have a
small value for n like 10 and a large value for m like 10^5. In this
case the dependency on m is really important to the complexity of the
problem. This is also an issue with representing it as O(n +m) because
if m is small in this case and n is large then we will again see a
misrepresentation of the complexity of the problem with my provided
notation.
However, the good thing about Big-O notation is that it represents the
worst case for all, so the worst case for O(n+n) is the same as O(n+m)
and therefore they are quite equivalent. At this point it is just a
matter of preference as to how you want to represent the dependency on
m as an input variable(if you have such a dependency).
Of course if you don't have any dependency on m as an input then I
think that O(n+n) => O(n) is a much better representation of the
problem then what I gave.
我正在 this problem 解决 Hacker 等级问题。我解决问题的算法是：
- 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.- Let total levels to be played by Alice is m.
- Let Alice's score after first round be S.
- Let Alice's initial rank R be 0.
- Start iterating playerScores array from the rear end until you get a player score whose score is less than S.
- Set R to rank of the player found in step 5.
- Reduce m by 1.
- Print R.
- Now start processing Alice's score in all subsequent m-1 levels inside a loop
- Set S to Alice's next level score.
- Start iterating playerScores array from the player whose rank is R-1 towards the front end.
- Continue iteration untill you get a player whose score is less than S.
- Set R to rank of the player found in above step.
- Reduce m by 1.
- Print R.
- Go to step 9.1 if there are more levels left to be played (i. e m>0).
现在当我开始计算上述算法的Big O时间复杂度时，我意识到它应该是O(n)如下：
- 需要一次扫描才能获得不重复的分数。这有助于因素 n。有可能所有分数都是唯一的。
- 需要从尾到前再扫描一次，以确定爱丽丝在每个级别后的排名。这再次影响因素 n。在最坏的情况下，级别数 (m) 可以等于玩家数 (n)。
将以上两个因素相加，时间复杂度为 O(n + n) = O(2n) = O(n)。虽然我的朋友声称它是 O(n + m)，但他无法解释清楚。如果我对 O(n+n) 复杂度的表述有缺陷，谁能帮我理解同样的问题？
m 和 n 之间的关系时，O(n+m) 不同于 O(n+n) 或 O(n)。可能有时 n 可能比 m 大，有时 m 可能更大，但没有明确的方法可以判断。但是，如果您无论如何都知道 n>=m，那么您可以说 O(n+m) 实际上就是 O(n)。在这种情况下，同样的规则适用。
我能够从相关人员那里得到回复。引用 Ryan Fehr 的话：
For this problem, O(n+n) and O(n+m) are essentially the same thing, because they both have the same upper bound. I decided to go for the O(n+m) representation because it makes sure that it is apparent that my solution is dependent on the number of levels Alice beat that is represented by m in this case.
An example where this differentiation is important is when we have a small value for n like 10 and a large value for m like 10^5. In this case the dependency on m is really important to the complexity of the problem. This is also an issue with representing it as O(n +m) because if m is small in this case and n is large then we will again see a misrepresentation of the complexity of the problem with my provided notation.
However, the good thing about Big-O notation is that it represents the worst case for all, so the worst case for O(n+n) is the same as O(n+m) and therefore they are quite equivalent. At this point it is just a matter of preference as to how you want to represent the dependency on m as an input variable(if you have such a dependency).
Of course if you don't have any dependency on m as an input then I think that O(n+n) => O(n) is a much better representation of the problem then what I gave.