python - Does slicing in startswith and endswith make the time complexity O(n² * m) {where m is the average length of s

admin管理员组

文章数量:1125787

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        n = len(words)
        count = 0
        for i in range(n):
            for j in range(i+1, n):
                if words[j].startswith(words[i]) and words[j].endswith(words[i]):
                    count += 1
        return count        

I analyzed the code, expecting the time complexity to be O(n²) due to nested loops, but I'm unsure if slicing in startswith changes it to O(n² * m) where m is the average length of string in the list.

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        n = len(words)
        count = 0
        for i in range(n):
            for j in range(i+1, n):
                if words[j].startswith(words[i]) and words[j].endswith(words[i]):
                    count += 1
        return count        

I analyzed the code, expecting the time complexity to be O(n²) due to nested loops, but I'm unsure if slicing in startswith changes it to O(n² * m) where m is the average length of string in the list.

• python
• time-complexity
• startswith

Share Improve this question Follow edited 2 days ago Nyctophilic Enigma asked Jan 9 at 3:14 Nyctophilic EnigmaNyctophilic Enigma 2111 silver badge44 bronze badges New contributor Nyctophilic Enigma is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. 2

• 1 As a side-note, you could optimize this (and make it a little easier to read) by using itertools.combination to replace the nested loops. for needle, haystack in itertools.combinations(words, 2):, then if haystack.startswith(needle) and haystack.endswith(needle): would do the same thing, and push a lot more work to the C layer, avoid creating a bunch of unnecessary ints, reduce the indentation, and let you give more useful/descriptive names to variables. It won't affect the big-O at all, but it would reduce the constant factors meaningfully. – ShadowRanger Commented 2 days ago
• @ShadowRanger Micro-optimization fun! With words = list(map(str, range(1000))) I get around 45 ms with theirs, 35 ms with yours, and 15 ms with mine. – Stefan Pochmann Commented 2 days ago

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 3

First, a correction: Neither startswith nor endswith involve slicing; no copies are made. That said, both methods are O(n) in the length of the pre-/|suff-ix(es) to check.

This doesn't make it O(n³) though. It makes it O(n²m), where n is the length of words, while m is the (median?) length of the strings within words. Since the length of words and the length of its component words are independent, it would be inappropriate to describe it as O(n³). Your title seems to recognize this when it refers to O(n²m), but you blurred it together in the body of your question by calling it O(n³).

That said, typically, when you're talking about a list named words, the length of the component strings is de minimis (defining the behavior as the length of a string approaches infinity is meaningless when talking about strings that don't get much longer than 40 characters on a bad day, and average less than 10), and you can treat it as a constant term, so O(n²) remains correct enough if words really does contain individual English words.

本文标签：