编程竞赛代码的嵌套循环Big-O时间复杂度分析咨询

Let's break down why this implementation runs in O(n + m) time, where n is the length of the scores array and m is the length of the alice array.

Key Observations About the Traversal #

The critical detail here is how lastRankIndex eliminates redundant work:

• Every call to findRank starts traversing scores from lastRankIndex - 1, moving leftward (from higher indices to lower ones).
• After each call, we update lastRankIndex to ranks.back() - 1—this sets our next starting point to the position immediately after where we stopped in scores during this call.

Counting Total Operations #

Let's tally up the work done:

1. Outer loop: We iterate over all m elements in alice—that's m iterations, each with constant overhead (outside of the findRank calls).
2. Inner traversal of scores: Here's the key efficiency win: each element in scores is checked at most once. Once we move past an index in scores (by traversing left), we never revisit it again. Even if scores is much larger than alice, the total number of elements we check across all findRank calls will never exceed n.

For example:

• If alice has 5 elements and scores has 1000, we might traverse 300 elements of scores for the first alice element, 200 for the second, and so on—but the sum of all those traversals will never hit more than 1000.

Why It's Not O(n*m) #

You might initially worry about nested loops leading to O(n*m) time, but that only happens if we re-traverse parts of scores for each alice element. Since lastRankIndex ensures we only ever move left through scores and never repeat checks, we avoid that worst-case scenario entirely.

Final Verdict #

Adding the two components together: the m iterations over alice plus the maximum n traversals of scores gives us an overall time complexity of O(n + m).

内容的提问来源于stack exchange，提问作者Toundey