そのため、最近のデータ構造クラスで、アルゴリズム分析と Big-O 分析について学びました。これまでのところ、分析が比較的簡単なソートアルゴリズムにのみ適用しました。より複雑なアルゴリズムを分析する方法に興味がありました。
たとえば、ファイルからすべてのバイトを読み取り、データを分離する 4 バイトのタグを使用してそれらをブロックに分割するために取り組んでいるプログラム用に、この python アルゴリズムを作成しました。各タグは「h」で始まり、4 バイト シーケンスがタグであるかどうかを判断するときに使用する可能性のあるタグの別のリストがあります。アルゴリズムは以下で定義されます
data = file.read()
blocks = []
tagIndexes = []
i = data.index(b'h')
try:
while 1:
if data[i:i+4] in tags:
tagIndexes += [i]
i = data.index(b'h', i+1)
except ValueError:
pass
for j in range(len(tagIndexes) - 1):
index = tagIndexes[j]
nextIndex = tagIndexes[j+1]
blocks += [block(data[index:index+4], data[index+4:nextIndex])]
lastIndex = tagIndexes[len(tagIndexes) - 1]
blocks += [block(data[lastIndex:lastIndex+4], data[lastIndex+4:])]
return blocks
アルゴリズムを改善する方法についてコメントを求めているわけではありません。必要に応じて、後で自分でそれを行うことができます。私の質問は、このアルゴリズムの最悪のシナリオまたは Big-O 表記をどのように決定するかということです。その中にはいくつかのサブアルゴリズムがあり、ほとんどの小さなアルゴリズムの最悪のケースを簡単に確認できます。たとえば、python の list.index(val) メソッドの最悪のケースは、リストに指定された値がまったくない場合です。この場合、すべてをループしてエラー O(n) を発生させます。ただし、そのメソッドのループの最悪のケースは、すべてのバイトが 'h' O(n) の場合です。しかし、その場合、data.index() への各呼び出しは非常に高速で、すぐに値 O(1) を返します。そして、2 番目のループの最悪のケースは、すべての 4 バイトがタグ O(n/4) である場合です。
部分だけでなく、アルゴリズム全体を含む最悪のケースについてこれを分析するにはどうすればよいですか?