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

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Donc, en CS50 nous avons appris à propos
une variété de tri et de recherche

3
00:00:08,900 --> 00:00:09,442
algorithmes.

4
00:00:09,442 --> 00:00:11,400
Et parfois, il peut être
un peu difficile à garder

5
00:00:11,400 --> 00:00:14,161
trace de ce que l'algorithme fait quoi.

6
00:00:14,161 --> 00:00:15,910
Nous avons vraiment seulement
écrémé la surface trop,

7
00:00:15,910 --> 00:00:18,740
il ya beaucoup d'autres recherche
et des algorithmes de tri.

8
00:00:18,740 --> 00:00:21,780
Ainsi, dans cette vidéo nous allons
il suffit de prendre quelques minutes

9
00:00:21,780 --> 00:00:24,980
pour essayer de distiller chaque algorithme
vers le bas à ses éléments essentiels

10
00:00:24,980 --> 00:00:27,810
de sorte que vous pouvez vous rappeler le plus
des informations importantes sur les

11
00:00:27,810 --> 00:00:31,970
et être en mesure d'articuler la
différences, si nécessaire.

12
00:00:31,970 --> 00:00:34,220
>> La première est la sélection sorte.

13
00:00:34,220 --> 00:00:38,210
L'idée de base derrière sélection Trier
est de trouver l'élément non triés plus petit

14
00:00:38,210 --> 00:00:42,890
dans un tableau et échanger avec le
premier élément non triés de ce tableau.

15
00:00:42,890 --> 00:00:46,620
Nous avons dit que le pire des cas
moment de l'exécution de ce n était carré.

16
00:00:46,620 --> 00:00:50,060
Et si vous voulez rappeler pourquoi, prenez
un oeil à la vidéo sélection de tri.

17
00:00:50,060 --> 00:00:54,560
Le temps d'exécution meilleur des cas
est également n carré.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sorte, l'idée derrière ce
on est d'échanger des paires adjacentes.

19
00:00:58,910 --> 00:01:01,730
Voilà donc la clé qui vous aide
rappeler la différence ici.

20
00:01:01,730 --> 00:01:04,920
Sélection tri est, jusqu'ici,
trouver la bulle smallest--

21
00:01:04,920 --> 00:01:06,790
Sort est échanger paires adjacentes.

22
00:01:06,790 --> 00:01:08,710
Nous échangeons des paires adjacentes
d'éléments si elles

23
00:01:08,710 --> 00:01:12,530
sont hors de l'ordre, qui a effectivement
bulles grands éléments vers la droite,

24
00:01:12,530 --> 00:01:17,060
et en même temps il commence aussi
à déplacer les éléments plus petits vers la gauche.

25
00:01:17,060 --> 00:01:20,180
Le pire cas de temps d'exécution
de tri à bulles est n carré.

26
00:01:20,180 --> 00:01:23,476
Le temps d'exécution meilleur des cas
de tri à bulles est n.

27
00:01:23,476 --> 00:01:25,350
Parce que dans cette situation
nous ne actually-- pas

28
00:01:25,350 --> 00:01:27,141
nous ne pourrions pas besoin de
faire des swaps du tout.

29
00:01:27,141 --> 00:01:31,026
Nous avons seulement pour faire un
passer à travers tous les éléments de n.

30
00:01:31,026 --> 00:01:34,600
>> Dans le tri par insertion, la
idée de base est en train de changer.

31
00:01:34,600 --> 00:01:36,630
Voilà le mot-clé pour le tri par insertion.

32
00:01:36,630 --> 00:01:39,630
Nous allons à l'étape une fois à travers
le tableau de gauche à droite.

33
00:01:39,630 --> 00:01:41,670
Et comme nous le faisons, nous sommes
va changer éléments

34
00:01:41,670 --> 00:01:46,260
nous avons déjà vu pour faire place à
plus petits qui doivent correspondre quelque part

35
00:01:46,260 --> 00:01:48,080
Retour dans la partie triés.

36
00:01:48,080 --> 00:01:51,600
Donc, nous construisons le tableau trié un
élément à la fois, de gauche à droite,

37
00:01:51,600 --> 00:01:54,740
et nous changeons des choses à faire de la place.

38
00:01:54,740 --> 00:01:58,650
Le temps d'exécution pire cas de
tri par insertion est n carré.

39
00:01:58,650 --> 00:02:02,380
Le temps meilleur des cas fonctionner est n.

40
00:02:02,380 --> 00:02:05,380
>> Fusionner sort-- le mot-clé
ici est fractionner et fusionner.

41
00:02:05,380 --> 00:02:08,949
Nous avons partagé la gamme complète, que ce soit
il est six éléments, huit éléments,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- nous divisons
diminué de moitié, moitié, moitié,

43
00:02:13,790 --> 00:02:17,720
jusqu'à ce que nous avons en vertu de tableau
n un tableaux élémentaires.

44
00:02:17,720 --> 00:02:19,470
Un ensemble de n un tableaux élémentaires.

45
00:02:19,470 --> 00:02:22,640
Donc, nous avons commencé avec un
Tableau 1000-élément,

46
00:02:22,640 --> 00:02:26,550
et nous arrivons au point où nous
avoir 1.000 à un élément tableaux.

47
00:02:26,550 --> 00:02:30,990
Puis nous commençons à fusionner ces sous-réseaux
retour ensemble dans le bon ordre.

48
00:02:30,990 --> 00:02:34,860
Donc, nous prenons deux tableaux à un élément
et créer un tableau à deux éléments.

49
00:02:34,860 --> 00:02:38,180
Nous prenons deux tableaux à deux éléments
et de créer un réseau de quatre éléments

50
00:02:38,180 --> 00:02:43,900
et ainsi de suite et ainsi de suite jusqu'à ce que nous avons
nouveau reconstruit une matrice n de l'élément.

51
00:02:43,900 --> 00:02:48,410
>> Le temps d'exécution pire cas de
tri par fusion est N fois log n.

52
00:02:48,410 --> 00:02:52,390
Nous avons n éléments, mais
ce processus de recomposition

53
00:02:52,390 --> 00:02:56,960
prend log n étapes pour obtenir
revenir à une gamme complète.

54
00:02:56,960 --> 00:03:01,160
Le meilleur des cas d'exécution est également n log
n parce que ce processus n'a pas vraiment

55
00:03:01,160 --> 00:03:04,090
soucie si le tableau était
triés ou non pour commencer.

56
00:03:04,090 --> 00:03:07,590
Le processus est le même, il ya
aucun moyen de courtes choses circuit.

57
00:03:07,590 --> 00:03:11,610
Alors n log n dans le pire des cas,
n log n dans le meilleur des cas.

58
00:03:11,610 --> 00:03:13,960
>> Nous avons parlé de deux
la recherche des algorithmes.

59
00:03:13,960 --> 00:03:16,230
Donc, la recherche linéaire est d'environ itération.

60
00:03:16,230 --> 00:03:19,500
Nous procédons à travers la matrice
une fois, de gauche à droite,

61
00:03:19,500 --> 00:03:21,950
en essayant de trouver le nombre
que nous recherchons.

62
00:03:21,950 --> 00:03:24,550
Le temps le pire des cas courir est grand O de n.

63
00:03:24,550 --> 00:03:27,610
Il pourrait nous emmener itération
à travers chaque élément

64
00:03:27,610 --> 00:03:30,660
pour trouver l'élément que nous sommes à la recherche
pour, soit en dernière position,

65
00:03:30,660 --> 00:03:31,630
ou pas du tout.

66
00:03:31,630 --> 00:03:34,720
Mais nous ne pouvons pas confirmer que, jusqu'à
nous avons examiné tout.

67
00:03:34,720 --> 00:03:36,730
m le meilleur des cas, nous trouvons immédiatement.

68
00:03:36,730 --> 00:03:41,060
Le temps d'exécution le meilleur des cas de
recherche linéaire est l'oméga de 1.

69
00:03:41,060 --> 00:03:43,689
>> Enfin, il y avait une recherche binaire,
qui exige gamme assortis.

70
00:03:43,689 --> 00:03:45,605
Rappelez-vous que est une très
considération importante

71
00:03:45,605 --> 00:03:47,155
lorsque vous travaillez avec la recherche binaire.

72
00:03:47,155 --> 00:03:50,180
Il est une condition préalable à l'utilisation de it--
le tableau que vous êtes à la recherche par le biais

73
00:03:50,180 --> 00:03:52,160
doit être trié.

74
00:03:52,160 --> 00:03:54,500
Dans le cas contraire, le mot-clé
est diviser pour régner.

75
00:03:54,500 --> 00:03:58,310
Diviser le tableau en deux et
éliminer la moitié des éléments

76
00:03:58,310 --> 00:04:00,780
chaque fois que vous passez à travers.

77
00:04:00,780 --> 00:04:04,330
En raison de cette diviser pour mieux régner
et les choses de fractionnement en demi approche,

78
00:04:04,330 --> 00:04:07,450
le temps d'exécution pire cas
de recherche binaire est

79
00:04:07,450 --> 00:04:11,730
log n, qui est sensiblement
mieux que la n de la recherche linéaire.

80
00:04:11,730 --> 00:04:13,570
Le temps meilleur des cas fonctionner est encore un.

81
00:04:13,570 --> 00:04:17,010
>> Nous pourrions trouver immédiatement le
première fois que nous faisons une division, mais,

82
00:04:17,010 --> 00:04:19,339
encore une fois, rappelez-vous que
Bien que la recherche binaire est

83
00:04:19,339 --> 00:04:24,030
nettement mieux que la recherche linéaire
en vertu d'être log n par rapport à n,

84
00:04:24,030 --> 00:04:27,110
vous pourriez avoir à passer par le travail
de tri votre premier tableau, qui

85
00:04:27,110 --> 00:04:32,010
pourrait rendre moins efficace en fonction
de la taille de l'itération triés.

86
00:04:32,010 --> 00:04:35,250
>> Je suis Doug Lloyd, cela est CS50.

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