循环中字符串切片与f-string的时间复杂度分析及wildcards函数Big-O验证

你的结论是正确的，这个函数的时间复杂度确实是O(n²)，具体分析如下：

• 循环次数：函数会执行len(word)次迭代，也就是n次（n为输入字符串word的长度）。
• 单次迭代的时间成本：
  1. 切片操作word[:j]和word[j+1:]：每个切片的时间复杂度与切片长度成正比，分别是O(j)和O(n-j-1)，两者总耗时为O(j + (n-j-1)) = O(n)。
  2. f-string拼接：f"{word[:j]}_{word[j + 1:]}"会生成一个长度为n-1的新字符串，需要把两个切片的字符和下划线全部复制一遍，这一步的时间复杂度是O(n)（最终字符串长度为n-1，属于线性量级）。
     单次迭代的总时间为O(n) + O(n) = O(n)。

将n次迭代的时间累加，整体时间复杂度就是n * O(n) = O(n²)。

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