シーヶンスサーチ

3151 ワード
python algorithm テキストリンク

シーヶンスサーチ


  • 一連の資料を順番に検索する方法
  • 最も簡単で直感的な検索方法
  • は、順序付けされたデータ構造で必要なアイテムを検索する場合に便利です.
  • アルゴリズムは簡単で実施しやすいが、検索対象が多いと実行時間が急激に増加し、効率が低下する

  • サーチプロセス
  • の最初の要素から、検索オブジェクトとキー値が同じ要素を順に検索します.
    • 値が
  • の同じ要素が見つかった場合、その要素のインデックスが返されます.
  • 資料構造の最後まで、検索対象が見つからない場合は検索を終了します.

  • 検索する要素の順序に基づいて比較回収を決定
  • 最初の要素を検索するときに1回比較し、2番目の要素を検索するときに2回比較する
    • .
  • 未ソートデータにおけるシーケンス検索の平均比較回収
  • (1/n)*(1+...+n) = (n+1)/2\

  • 時間複雑度:O(n)

  • 整列時
  • のソートであるため、検索に失敗した場合、平均比較回数は半分に減少します.
  • 時間複雑度:O(n)
    • def sequentialSearch(lst,n,key):
    i = 0
    while i <n and a[i] !=key :
        i += 1 
    if i<n : 
        return i
   	else :
        return -1 
    def sequentialSearch2(lst,n,key) :
    i = 0
    while i<n and a[i]<key :
        i +=1 
    if i<n and a[i] == key:
        return i
   	else :
        return -1
    [実施]2020 KACA実習-公式最大化
    ソートの選択