如何计算使用API方法时的时间复杂度？以String类indexOf()方法的应用场景为例

Great question! Calculating time complexity when relying on built-in APIs can feel opaque at first—let's break this down clearly, starting with the indexOf method you're confused about, then moving to the full code.

First: Time Complexity of String.indexOf(String target) #

In Java, the indexOf method for strings works by checking every possible starting position in the source string to see if the target substring matches. In the worst case, this means comparing each character of the target to characters in the source string for every valid starting index.

For a source string of length m and target substring of length k, this results in a time complexity of O(m * k).

Note: If the target is a prefix of the source string (which is what your code is ultimately trying to check), indexOf will exit early once it confirms the first k characters match, so that specific call would be O(k) instead of O(m*k). But we have to account for the worst-case scenario where the target isn't a prefix, requiring full checks.

Breaking Down Your Code #

Let's define a few variables to make this concrete:

• n: The number of strings in the strs array
• L: The length of the first string strs[0] (the initial value of prefix)
• M: The maximum length of any string in strs

Now let's walk through the logic:

1. Initialization: We start with prefix = strs[0], which takes O(1) time.
2. Outer For Loop: This runs n-1 times (once for each string after the first).
3. Inner While Loop: For each string strs[i], we repeatedly shorten prefix by one character until strs[i].indexOf(prefix) == 0 (meaning prefix is now a prefix of strs[i]).

Worst-Case Scenario #

The worst case happens when there is no common prefix across all strings (so prefix gets shortened all the way to an empty string). Here's how the time adds up:

• For the first string we process (strs[1]), we enter the while loop L times (shortening prefix from length L down to 0). Each iteration calls indexOf with a target of length k (starting at L, then L-1, ..., 1).
  • The total time for these L calls is O(ML + M(L-1) + ... + M1) = O(M * L(L+1)/2) ≈ O(M*L²). Since L ≤ M, this simplifies to O(M²).
• For all subsequent strings (strs[2] to strs[n-1]), prefix is already an empty string. indexOf("") always returns 0 immediately, so the while loop doesn't run. Each of these iterations takes O(1) time (or O(M) in the absolute worst case, but this is negligible compared to the O(M²) cost from the first iteration).

Adding it all together, the worst-case time complexity is O(n*M²).

Best-Case Scenario #

The best case is when all strings share the exact same prefix as strs[0]. In this case, the while loop never runs—we just call indexOf(prefix) once per string, which exits early after checking the first L characters. This results in a time complexity of O(n*M) (since each indexOf call takes O(L) time, and L ≤ M).

Key Takeaway #

When analyzing code with built-in APIs, always reason through the API's underlying complexity—don't assume it's O(1). For string operations like indexOf, substring comparisons dominate the cost, so we have to account for the lengths of both the source string and the target substring.

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