pythonの文字列操作のうち、連結、先頭要素の削除、最後の要素の削除について計算量を検証してみました。
これらの操作の計算量が$O(n)$であることを検証します。

きっかけ

ABC298 D問題にて、$N$回のループのなかで長さが$O(N)$の文字列の連結(一文字追加)を行なうと、TLEとなりました。
文字列の代わりにcollections.dequeを使うと制限時間に間に合いました。

今回の検証前は、pythonの文字列は双方向リスト的なもので実装されており、先頭と最後に一文字加える操作では$O(1)$でできるのではないかというイメージを持っていました(事実とは異なります)。

pythonの文字列はイミュータブル

pythonの文字列はイミュータブルであり、文字列オブジェクトに対して他の文字列との連結や要素の削除を行うことはできません。

オブジェクトが mutable かどうかはその型によって決まります。例えば、数値型、文字列型とタプル型のインスタンスは immutable で、dict や list は mutable です。

代わりに、別の文字列との連結結果や、要素を削除した文字列を別のオブジェクトとして生成して返す機能が実装されています。
普段+演算子やスライスで行う文字列操作は、実は丸々コピーしてから渡されています。
従って、次のようなことが言えそうです。

操作	計算量
連結	$O(N＋M)$
先頭・最後の要素の削除	$O(N)$

ただし、元の文字列の長さを$N$、連結する文字列の長さを$M$としています。

上の問題では、長さ$O(N)$の文字列への連結が$N$回起こり、全体で計算量が$O(N^2)$となることで制限時間オーバーとなった模様です。
連結や先頭・最後の要素へのアクセスが頻繁に起きる場合は、双方向キューやリストなどのデータ構造を使うことを検討すべきでしょう。

リストを使う場合は文字列のjoinメソッドで連結できます。

str_list = ["abc", "ABC", "123"]
print("".join(str_list)) # abcABC123

joinの計算量はリストの長さに比例するはずですが、リスト末尾への要素の追加は$O(1)$のはずです。

検証してみる

ここで終わってもいいのですが、「推測するな、計測せよ」という格言にしたがって、せっかくなので計測してみます。

matplotlibを使って、文字列の連結、先頭要素の削除、最後の要素の削除にかかる時間を可視化してみました。

それぞれの文字列長において、かかった時間は100回の平均をとっています。
連結する文字列は1文字にしました。
先頭要素と最後の要素の削除にはスライスを使っています。

import matplotlib.pyplot as plt
import numpy as np
import time


length = [n*10**5 for n in range(10)]

concat_time = []
delete_first_time = []
delete_last_time = []

for l in length:
    string = "a"*l

    # 連結
    t = []
    for _ in range(100):
        start = time.perf_counter()
        _tmp = string + "a"
        t.append(time.perf_counter() - start)
    concat_time.append(np.mean(t))

    # 先頭の削除
    t = []
    for _ in range(100):
        start = time.perf_counter()
        _tmp = string[1:]
        t.append(time.perf_counter() - start)
    delete_first_time.append(np.mean(t))

    # 最後の要素の削除
    t = []
    for _ in range(100):
        start = time.perf_counter()
        _tmp = string[:-1]
        t.append(time.perf_counter() - start)
    delete_last_time.append(np.mean(t))

plt.plot(length, concat_time, label="concat")
plt.plot(length, delete_first_time, label="delete first")
plt.plot(length, delete_last_time, label="delete last")
plt.xlabel("string length")
plt.ylabel("compute time [s]")
plt.legend()
plt.show()

実行環境は以下の通りです。

MacBook Pro (13-inch, M1, 2020)
Python 3.10.5

実行して得られたプロットを次に示します。

concat、delete first、delete lastがそれぞれ連結、最初の要素の削除、最後の要素の削除に対応します。
見ての通り、連結・削除する文字列長が1であるのにもかかわらず、全ての操作において元の文字列長に比例する時間がかかっていることがわかります。

結論

pythonで比較的長い文字列の連結やスライスが必要になったら、リストや双方向キューなどのデータ構造を検討しましょう。

参考