５．サーチ

UP 1 Level

内容

  1. スライド　1 ５．サーチ
  2. スライド　2 サーチ問題
  3. スライド　3 探索（サーチ）
  4. スライド　4 キーがない場合
  5. スライド　5 サーチ問題の重要性
  6. スライド　6 サーチアルゴリズムの種類
  7. スライド　7 ５-１：線形探索 （逐次探索）
  8. スライド　8 線形探索
  9. スライド　9 線形探索の動き
  10. スライド　10 線形探索の動き２ （データが無い場合）
  11. スライド　11 線形探索の実現
  12. スライド　12 命題LS１（linear_seachの正当性１）
  13. スライド　13 線形探索の最悪計算量
  14. スライド　14 線形探索の平均計算量
  15. スライド　15 線形探索の注意事項
  16. スライド　16 間違い
  17. スライド　17 配列を超えて走査するバグ
  18. スライド　18 番兵付の線形探索
  19. スライド　19 番兵付の線形探索
  20. スライド　20 番兵
  21. スライド　21 番兵(キーが無い場合）
  22. スライド　22 番兵付線形探索の実現
  23. スライド　23 命題BAN1（banpei_seachの停止性）
  24. スライド　24 番兵付線形探索の計算量
  25. スライド　25 ５-2：２分探索
  26. スライド　26 ２分探索
  27. スライド　27 ２分探索の動き (キーが存在する場合）
  28. スライド　28 ２分探索の動き (キーが存在しない場合）
  29. スライド　29 ２分探索の原理
  30. スライド　30 2分探索のイメージ
  31. スライド　31 練習
  32. スライド　32 2分探索の注意
  33. スライド　33 ２分探索の実現（繰り返し版）
  34. スライド　34 命題LBS１　（loop_b_searchの正当性１）
  35. スライド　35 証明
  36. スライド　36 とする。
  37. スライド　37 命題LBS２　（loop_b_searchの正当性２）
  38. スライド　38 命題LBS３　（loop_b_searchの停止性）
  39. スライド　39 間違った実装
  40. スライド　40 無限ループになる例
  41. スライド　41 ２分探索の実現（再帰版）
  42. スライド　42 rec_b_searchの正当性および停止性は、 loop_b_searchと...
  43. スライド　43 ２分探索の最悪計算量
  44. スライド　44 よって、最悪時間計算量は、
  45. スライド　45 ２分探索の平均計算量
  46. スライド　46 よって、平均反復回数　　　　　は次式を満たす。
  47. スライド　47 また、入力サイズが一般的な場合も次のように解析できる。
  48. スライド　48 最大反復回数より、
  49. スライド　49 ５-3．ハッシュ
  50. スライド　50 線形探索と２分探索の問題点
  51. スライド　51 ハッシュとは
  52. スライド　52 ハッシュのイメージ
  53. スライド　53 具体的なハッシュ関数
  54. スライド　54 アスキーコード
  55. スライド　55 ハッシュ関数の構成例１
  56. スライド　56 名前とハッシュ関数の構成例
  57. スライド　57 ハッシュ値の計算例
  58. スライド　58 このハッシュ値をもとに配列に保存する。
  59. スライド　59 練習
  60. スライド　60 ハッシュ関数の定義域と値域
  61. スライド　61 次に値域は、
  62. スライド　62 関数のイメージ
  63. スライド　63 ハッシュ関数への要求
  64. スライド　64 衝突
  65. スライド　65 衝突のイメージ１
  66. スライド　66 衝突例
  67. スライド　67 衝突のイメージ２
  68. スライド　68 衝突への対処
  69. スライド　69 このハッシュ関数を用いると、abe-> okuの順にデータが挿入された場合、次の...
  70. スライド　70 衝突の対処
  71. スライド　71 ハッシュ表への検索
  72. スライド　72 ハッシュ表からの検索
  73. スライド　73 ハッシュ表からの検索(衝突時）
  74. スライド　74 ハッシュテーブルへのデータ挿入 (衝突が無い場合）
  75. スライド　75 ハッシュ表からの検索 （衝突が無い場合）
  76. スライド　76 ハッシュテーブルへのデータ挿入 (衝突がある場合）
  77. スライド　77 ハッシュ表からの検索 （衝突がある場合）
  78. スライド　78 ハッシュ法を用いた計算量 （衝突が定数回の場合）
  79. スライド　79 衝突がある場合の 平均計算量解析
  80. スライド　80 このとき、　　　　　　　　　　　　により求められる最初のセルがふさがっている確率...
  81. スライド　81 これは、空きセルを見つけるための失敗の回数を表している。これに、空きセルの発見（...
  82. スライド　82 これは、１回の挿入の際に調べるセルの期待値である。したがって、ハッシュ表にＮ個の...
  83. スライド　83 したがって、一回あたりの平均計算量は、次式で表される。
  84. スライド　84 ？
  85. スライド　85 内部ハッシュ関数の計算量の概形
  86. スライド　86 ハッシュ法のまとめ
  87. スライド　87 衝突が生じる場合： ハッシュ表の大きさＭとしては、データ数の２倍以上にしておく...
  88. スライド　88 他のハッシュ関数
Converted from Powerpoint Presentation to HTML by PPT2HTML AddIn.
PPT2HTML : by AGATASHI