Python中字符串`+=`的复杂度是多少

Question

因为它是不可变的，所以理论上应该是 O(n)，不过在背后有一些优化（可以参考其他的StackOverflow帖子，比如这个 https://stackoverflow.com/a/70499811/11092636）。

但是，既不是 O(1) 也不是 O(n)（来源于我下面做的基准测试），那它的复杂度到底是什么呢？有没有官方的资料可以参考？

重现的最小可运行示例：

import time
import matplotlib.pyplot as plt

def average_time_to_append(length):
    total_time = 0
    for _ in range(20000):  # Repeat 20000 times
        test_string = 'a' * length
        start_time = time.time()
        test_string += 'a'
        end_time = time.time()
        total_time += end_time - start_time
    return total_time / 20000  # Return the average time taken

lengths = list(range(10, 5*10**5))

# Measure
times = [average_time_to_append(length) for length in lengths]

# Plot
plt.figure(figsize=(10, 6))
plt.plot(lengths, times, marker='o')
plt.xlabel('String Length')
plt.ylabel('Time to append (seconds)')
plt.title('Benchmark: Time to Append \'a\' to a String')
plt.grid(True, which="both", ls="--")
plt.savefig("test.png")