組み込み開発のためのPython · レッスン 157 / 220
線形探索を行う
線形探索は先頭から順に比較し、整列不要でO(n)時間を要します。小規模データでは単純さが利点となる場合があります。
線形探索は先頭から順に比較し、整列不要でO(n)時間を要します。小規模データでは単純さが利点となる場合があります。 仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。
基本の考え方
線形探索は先頭から順に比較し、整列不要でO(n)時間を要します。小規模データでは単純さが利点となる場合があります。
安全に試すための確認
計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。
コード例
手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。
def find_index(values, target):
for index, value in enumerate(values):
if value == target:
return index
return None
print(find_index([4, 8, 12], 8))手を動かす課題
重複値と未発見値に対する戻り値を定めて、線形探索をテストしてください。