Return to Video

18-15 Worst Case Solution

  • 0:00 - 0:04
    答えは最後の2つです
  • 0:04 - 0:06
    どちらもインデックスの要素数だけ
    ループを行う必要があります
  • 0:06 - 0:13
    インデックスにない言葉の場合
    テストは常にFalseになります
  • 0:13 - 0:15
    ループが終了になり何も返しません
  • 0:15 - 0:19
    追加された最後の言葉の場合は
    要素数だけループを続けます
  • 0:19 - 0:22
    そして一致を見つけた最後の時に
  • 0:22 - 0:25
    その要素を返します この解析の仮定の1つとして
  • 0:25 - 0:30
    ループに費やされる時間は
    実際に渡したキーワードに左右されません
  • 0:30 - 0:33
    この同等比較はキーワードやエントリが何であっても
  • 0:33 - 0:38
    同じだけの時間が必要になると仮定します
  • 0:38 - 0:43
    キーワードが何であれこの比較を行う時間は同じです
  • 0:43 - 0:46
    文字列やPythonでも同じことです
  • 0:46 - 0:50
    この文字列の比較をとても速く行うことができます
  • 0:50 - 0:53
    文字列が不変的だからです
    つまり2つの文字列を比較するために
  • 0:53 - 0:56
    文字列にあるすべての文字を調べる必要は
    ないということです
  • 0:56 - 1:02
    ダブルイコールはすべての文字列を
    調べる必要がない時に使えます
  • 1:02 - 1:05
    文字列は異なる文字列として
    生成されたことを知っています
  • 1:05 - 1:09
    同じ文字列として生成された場合は
    同じ文字列になります
  • 1:09 - 1:12
    以上からループの他のすべての動作に
  • 1:12 - 1:19
    定数時間があると言えます
    それは入力サイズに左右されない速い動作です
  • 1:19 - 1:22
    時間を把握する点で重要なことはインデックスを
  • 1:22 - 1:25
    1つずつ調べる回数です
    もし皆さんが次のコースを受講するなら
  • 1:25 - 1:28
    受講してもらいたいですがね
    もっと形式的な方法でアルゴリズムを
  • 1:28 - 1:31
    どう解析するのか理解できます
  • 1:31 - 1:35
    今の目標は直感を高めることです
    直感はループを行う回数によって
  • 1:35 - 1:37
    実行時間が左右することを理解するために
    重要なものです
  • 1:37 - 1:41
    ループ内で行うことはすべて定数時間です
  • 1:41 - 1:43
    要素のサイズに左右されることはありません
Cím:
18-15 Worst Case Solution
Leírás:

18-15 Worst Case Solution

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS101 - Intro to Computer Science
Duration:
01:44

Japanese subtitles

Felülvizsgálatok