1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD：だからCS50に、我々は、約学びました
ソートや検索の様々な

3
00:00:08,900 --> 00:00:09,442
アルゴリズム。

4
00:00:09,442 --> 00:00:11,400
そして、時にはそれがすることができます
続けるには少しトリッキー

5
00:00:11,400 --> 00:00:14,161
何アルゴリズムのトラックが何を行います。

6
00:00:14,161 --> 00:00:15,910
私たちは本当にだけしました
あまりにも表面を脱脂、

7
00:00:15,910 --> 00:00:18,740
他の多くの検索があります
およびアルゴリズムをソート。

8
00:00:18,740 --> 00:00:21,780
だから、このビデオLETでの
わずか数分かかります

9
00:00:21,780 --> 00:00:24,980
試してみて、各アルゴリズムを蒸留します
その中核的な要素まで

10
00:00:24,980 --> 00:00:27,810
あなたがほとんどを覚えています
それらについての重要な情報

11
00:00:27,810 --> 00:00:31,970
そして、明確することができます
違い、必要に応じて。

12
00:00:31,970 --> 00:00:34,220
>> 最初は、選択ソートです。

13
00:00:34,220 --> 00:00:38,210
選択ソートの基本的な考え方
最小のソートされていない要素を見つけることです

14
00:00:38,210 --> 00:00:42,890
配列内とでそれを交換
その配列の最初のソートされていない要素。

15
00:00:42,890 --> 00:00:46,620
私たちは、最悪の場合のことを言いました
その実行時間をn乗しました。

16
00:00:46,620 --> 00:00:50,060
そして、あなたは理由を呼び出したい場合は、取ります
選択ソートのビデオを見て。

17
00:00:50,060 --> 00:00:54,560
最良の実行時間
また、nは2乗さ。

18
00:00:54,560 --> 00:00:58,910
>> バブルソート、その背後にある考え方
1は、隣接する対を交換することです。

19
00:00:58,910 --> 00:01:01,730
だから、それはあなたを助ける重要なのです
ここでの違いを覚えています。

20
00:01:01,730 --> 00:01:04,920
ソートされているので、これまでの選択、
smallest--バブルを見つけます

21
00:01:04,920 --> 00:01:06,790
ソートスワップ隣接する対です。

22
00:01:06,790 --> 00:01:08,710
私たちは、隣接する対を交換
要素の彼らの場合

23
00:01:08,710 --> 00:01:12,530
これは効果的に、順不同であります
右に大きな要素を泡、

24
00:01:12,530 --> 00:01:17,060
同時に、それはまた始まり
左に小さい要素を移動します。

25
00:01:17,060 --> 00:01:20,180
最悪のケースの場合は、ランタイム
バブルソートのN乗されます。

26
00:01:20,180 --> 00:01:23,476
最良の実行時間
バブルソートのnです。

27
00:01:23,476 --> 00:01:25,350
そのような状況にあるため、
我々はactually--ません

28
00:01:25,350 --> 00:01:27,141
我々はする必要はありません
まったくスワップを行います。

29
00:01:27,141 --> 00:01:31,026
私たちは、1つを行う必要があります
すべてのn個の要素を通過。

30
00:01:31,026 --> 00:01:34,600
>> 挿入ソートでは、
ここでの基本的な考え方は、シフトしています。

31
00:01:34,600 --> 00:01:36,630
つまり、挿入ソートのキーワードです。

32
00:01:36,630 --> 00:01:39,630
我々は、ワンススルーステップになるだろう
左から右に配列。

33
00:01:39,630 --> 00:01:41,670
私たちがそうであるようにと、私たちはしています
要素をシフトするつもり

34
00:01:41,670 --> 00:01:46,260
我々はすでにのためのスペースを作るために見てきました
どこかにフィットする必要が小さいもの

35
00:01:46,260 --> 00:01:48,080
バックそのソートされた部分です。

36
00:01:48,080 --> 00:01:51,600
だから我々は、ソートされた配列を構築1
左から右に時間の要素、

37
00:01:51,600 --> 00:01:54,740
私たちは部屋を作るために物事をシフトします。

38
00:01:54,740 --> 00:01:58,650
の最悪の場合の実行時間
挿入ソートは、n乗されます。

39
00:01:58,650 --> 00:02:02,380
最良の場合の実行時間はNです。

40
00:02:02,380 --> 00:02:05,380
>> キーワードsort--マージ
ここで分割し、マージされています。

41
00:02:05,380 --> 00:02:08,949
私たちは、かどうか、完全な配列を分割
それは6つの要素、8要素ですが、

42
00:02:08,949 --> 00:02:13,790
万elements--我々はそれを分割
半分、半分、半分にダウンして、

43
00:02:13,790 --> 00:02:17,720
我々は、配列の下になるまで、
nは1素子アレイ。

44
00:02:17,720 --> 00:02:19,470
nは1素子アレイのセット。

45
00:02:19,470 --> 00:02:22,640
だから我々は1で開始
1000要素の配列、

46
00:02:22,640 --> 00:02:26,550
我々は我々のポイントを取得
千一素子アレイを持っています。

47
00:02:26,550 --> 00:02:30,990
その後、我々はそれらのサブ配列をマージし始め
バック一緒に正しい順序です。

48
00:02:30,990 --> 00:02:34,860
だから我々は2つ​​の1要素の配列を取ります
そして、2要素の配列を作成します。

49
00:02:34,860 --> 00:02:38,180
我々は2つ​​の2素子アレイを取ります
そして、4素子配列を作成

50
00:02:38,180 --> 00:02:43,900
などというように、我々はするまで
再び、1つのN要素の配列を再構築。

51
00:02:43,900 --> 00:02:48,410
>> の最悪の場合の実行時間
ISマージソートn回のnを記録します。

52
00:02:48,410 --> 00:02:52,390
我々は、n個の要素を有するが、
この再結合過程

53
00:02:52,390 --> 00:02:56,960
ログ取りのnを取得するための手順
完全な配列にバックします。

54
00:02:56,960 --> 00:03:01,160
時間を実行する最良の場合も、n個のログです
nは、このプロセスは本当にないので、

55
00:03:01,160 --> 00:03:04,090
アレイがあったかどうか気に
ソートやないで開始します。

56
00:03:04,090 --> 00:03:07,590
プロセスは同じですが、あります
短絡事に方法はありません。

57
00:03:07,590 --> 00:03:11,610
だからN N最悪の場合にログインすると、
N N最良のケースでログインします。

58
00:03:11,610 --> 00:03:13,960
>> 我々は2つ​​の話を
検索アルゴリズム。

59
00:03:13,960 --> 00:03:16,230
だから、線形検索が反復処理についてです。

60
00:03:16,230 --> 00:03:19,500
私たちは、アレイ全体進みます
一度、左から右に、

61
00:03:19,500 --> 00:03:21,950
番号を検索しようとしています
私たちは、探していること。

62
00:03:21,950 --> 00:03:24,550
最悪の場合の実行時間は、n個の大Oです。

63
00:03:24,550 --> 00:03:27,610
これは、繰り返し処理私たちがかかる場合があります
一つ一つの素子の両端

64
00:03:27,610 --> 00:03:30,660
我々が探している要素を検索します
以下のため、いずれかの最後の位置で、

65
00:03:30,660 --> 00:03:31,630
ではない、またはまったく。

66
00:03:31,630 --> 00:03:34,720
しかし、我々はそれまでを確認することはできません
我々はすべてのものを見てきました。

67
00:03:34,720 --> 00:03:36,730
ベスト・ケースをM、我々はすぐに見つけます。

68
00:03:36,730 --> 00:03:41,060
の最良の実行時間
線形探索は1のオメガです。

69
00:03:41,060 --> 00:03:43,689
>> 最後に、二分探索がありました、
これは各種の配列を必要とします。

70
00:03:43,689 --> 00:03:45,605
それは非常にです忘れないでください
考慮すべき重要なこと

71
00:03:45,605 --> 00:03:47,155
二分探索で作業する場合。

72
00:03:47,155 --> 00:03:50,180
それはit--使用するための前提条件です
あなたが探している配列を介して

73
00:03:50,180 --> 00:03:52,160
ソートする必要があります。

74
00:03:52,160 --> 00:03:54,500
それ以外の場合は、キーワード
分割統治です。

75
00:03:54,500 --> 00:03:58,310
半分に配列を分割し、
要素の半分をなくします

76
00:03:58,310 --> 00:04:00,780
あなたを介して進むようたびに。

77
00:04:00,780 --> 00:04:04,330
このため、分割統治の
半アプローチで分割のもの、

78
00:04:04,330 --> 00:04:07,450
最悪の場合の実行時間
バイナリサーチの

79
00:04:07,450 --> 00:04:11,730
実質的にこれは、nはログ
線形検索のnよりも優れています。

80
00:04:11,730 --> 00:04:13,570
最良の実行時間はまだ一つです。

81
00:04:13,570 --> 00:04:17,010
>> 我々はすぐにそれを見つけるかもしれません
初めて我々は、分裂を作るが、

82
00:04:17,010 --> 00:04:19,339
再び、ということを覚えています
バイナリ検索があるが、

83
00:04:19,339 --> 00:04:24,030
線形検索よりも実質的に良好
ログであることのおかげでN N対、

84
00:04:24,030 --> 00:04:27,110
あなたが仕事を通過する必要がある場合があります
、最初にあなたの配列をソートします

85
00:04:27,110 --> 00:04:32,010
応じて、それはあまり効果的になるかもしれません
ソートされた反復の大きさ。

86
00:04:32,010 --> 00:04:35,250
>> 私はダグロイドだけど、これはCS50です。

87
00:04:35,250 --> 00:04:36,757