はてなブックマーク

pythonの文字列操作のうち、連結、先頭要素の削除、最後の要素の削除について計算量を検証してみました。 これらの操作の計算量が$O(n)$であることを検証します。 きっかけ ABC298 D問題にて、$N$回のループのなかで長さが$O(N)$の文字列の連結(一文字追加)を行なうと、TLEとなりました。 文字列の代わりにcollections.dequeを使うと制限時間に間に合いました。 今回の検証前は、pythonの文字列は双方向リスト的なもので実装されており、先頭と最後に一文字加える操作では$O(1)$でできるのではないかというイメージを持っていました(事実とは異なります)。 pythonの文字列はイミュータブル pythonの文字列はイミュータブルであり、文字列オブジェクトに対して他の文字列との連結や要素の削除を行うことはできません。 オブジェクトが mutable かどうかはその型