この記事で学べること
リストの全探索をするときに、要素を一つずつ消しながらやったって、
オーダーは変わらず O(N^2) ですから！
状況
こんな問題を考えます。
要素がN個のリストAが与えられるので、リストAの中に0 ~ N-1がいくつ存在するかを出力してください（簡単化のため、とりあえずN=10にしておきます）。
愚直に解いてみましょう。
解法1: 工夫なしに解く
solution1.py
A = [8, 5, 6, 2, 3, 9, 1, 0, 4, 7]
cnt = 0
for i in range(10):
for j in A:
if i == j:
cnt += 1
break
print(cnt)
>>> 10
ここで、この解法のオーダーを考えてみます。
Aの要素の数だけAを全探索する必要があるので、O(N^2)であることが明らかですね。
でも、私は考えました。
「あれ？Aでヒットした要素をAから消去すればもっと早くなるんじゃない？？」
もしかして、オーダーが減るんじゃないの？！
解法2: 取り出した要素を消しながらソート処理
solution2.py
A = [8, 5, 6, 2, 3, 9, 1, 0, 4, 7]
cnt = 0
for i in range(10):
for j in range(len(A)):
if i == A[j]:
cnt += 1
del A[j] # 消してみた
break
print(cnt)
>>> 10
今回の問題の場合は、0 ~ N-1まで全てAに含まれているので、for文のループ回数が必ず一回ずつ減っていくことになります。従って、計算量は項数Nの等差数列の和になるはずです。
\sum_{k=0}^{n-1}k=\frac{1}{2}n(n+1)=\frac{1}{2}n^2+\frac{1}{2}n
・・・ん？
オーダー記法での計算量の求め方は、最高次数を参考にするって話だったから…
結局、要素を消していこうがいかまいが、 オーダー変わらずO(N^2)じゃん！
まとめ
少しでも計算量減らそうと足掻きますが、要素を一つずつ減らしていったり、途中で計算を打ち切ったりするくらいの小手先では、膨大なNに対しては何の効果もありません。TLEが出たときにはそんなところを気にするんじゃなくて、解答の方針を見直した方が良さそうです。
終わりに
自分用のメモとして記事を作成しましたので、非常に読みづらく、かつミスが多いかと思われます。ミスを発見した際にはスルーしていただくか、お手柔らかにご指摘していただけると嬉しいです。