1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Ας ρίξουμε μια ματιά στο είδος επιλογής, ένας αλγόριθμος

2
00:00:09,980 --> 00:00:12,800
για τη λήψη μια λίστα αριθμών και τη διαλογή τους.

3
00:00:12,800 --> 00:00:15,750
Ένας αλγόριθμος, να θυμάστε, είναι απλά ένα βήμα-προς-βήμα

4
00:00:15,750 --> 00:00:18,370
Διαδικασία για την πραγματοποίηση μιας εργασίας.

5
00:00:18,370 --> 00:00:21,470
Η βασική ιδέα πίσω από τέτοια επιλογή είναι να διαιρέσει

6
00:00:21,470 --> 00:00:23,390
κατάλογος μας σε δύο μέρη -

7
00:00:23,390 --> 00:00:26,810
ένα ταξινομημένο τμήμα και ένα τμήμα αδιαχώριστα.

8
00:00:26,810 --> 00:00:30,200
Σε κάθε βήμα του αλγορίθμου, ένας αριθμός μεταφέρεται από το πλαίσιο

9
00:00:30,200 --> 00:00:33,800
αδιαχώριστα τμήμα στο ταξινομημένο τμήμα έως ότου τελικά η

10
00:00:33,800 --> 00:00:35,880
Ολόκληρη η λίστα είναι ταξινομημένο.

11
00:00:35,880 --> 00:00:38,510
Έτσι, εδώ είναι μια λίστα με έξι αριθμούς -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, και 15.

13
00:00:44,010 --> 00:00:47,680
Αυτή τη στιγμή το σύνολο του καταλόγου θεωρείται ότι έχουν υποστεί διαλογή.

14
00:00:47,680 --> 00:00:51,770
Ακόμα κι αν ένας αριθμός στο 16 μπορεί να είναι ήδη στη σωστή του

15
00:00:51,770 --> 00:00:56,040
θέση, ο αλγόριθμος μας δεν έχει καμία δυνατότητα να γνωρίζει ότι μέχρι το

16
00:00:56,040 --> 00:00:57,980
Ολόκληρη η λίστα είναι ταξινομημένο.

17
00:00:57,980 --> 00:01:01,355
Γι 'αυτό και θα εξετάσουμε κάθε αριθμός να ανακατεμένα μέχρι να ταξινομήσετε

18
00:01:01,355 --> 00:01:03,800
μόνοι μας.

19
00:01:03,800 --> 00:01:06,890
Ξέρουμε ότι θέλουμε ο κατάλογος να είναι σε αύξουσα σειρά.

20
00:01:06,890 --> 00:01:10,200
Γι 'αυτό και θα θέλουν να χτίσουν το ταξινομημένο τμήμα του καταλόγου μας

21
00:01:10,200 --> 00:01:13,280
από αριστερά προς τα δεξιά, το μικρότερο στο μεγαλύτερο.

22
00:01:13,280 --> 00:01:17,970
Για να γίνει αυτό, θα πρέπει να βρείτε το ελάχιστο στοιχείο αδιαχώριστα

23
00:01:17,970 --> 00:01:21,350
και να το θέσω στο τέλος της ταξινομημένο τμήμα.

24
00:01:21,350 --> 00:01:25,370
Δεδομένου ότι ο κατάλογος αυτός δεν είναι ταξινομημένο, ο μόνος τρόπος για να γίνει αυτό είναι να

25
00:01:25,370 --> 00:01:29,330
εξετάσουμε κάθε στοιχείο στο τμήμα αδιαχώριστα, θυμόμαστε

26
00:01:29,330 --> 00:01:32,010
στοιχείο το οποίο είναι το χαμηλότερο και συγκρίνοντας

27
00:01:32,010 --> 00:01:33,770
κάθε στοιχείο σε αυτό.

28
00:01:33,770 --> 00:01:36,150
Γι 'αυτό και θα εξετάσουμε πρώτα την 23.

29
00:01:36,150 --> 00:01:38,650
Αυτό είναι το πρώτο στοιχείο που έχουμε δει, έτσι θα θυμόμαστε

30
00:01:38,650 --> 00:01:40,050
ως το ελάχιστο.

31
00:01:40,050 --> 00:01:42,320
Στη συνέχεια θα εξετάσουμε στο 42.

32
00:01:42,320 --> 00:01:46,720
42 είναι μεγαλύτερο από 23, οπότε 23 εξακολουθεί να είναι το ελάχιστο.

33
00:01:46,720 --> 00:01:51,210
Επόμενη είναι η 4, η οποία είναι μικρότερη από 23, έτσι θα θυμόμαστε 4

34
00:01:51,210 --> 00:01:52,880
ως το νέο ελάχιστο.

35
00:01:52,880 --> 00:01:56,380
Επόμενο είναι 16 που είναι μεγαλύτερο από 4, έτσι 4

36
00:01:56,380 --> 00:01:57,980
εξακολουθεί να είναι το ελάχιστο.

37
00:01:57,980 --> 00:02:03,670
8 είναι μεγαλύτερο από 4, και 15 είναι μεγαλύτερο από 4, οπότε θα πρέπει να είναι 4

38
00:02:03,670 --> 00:02:05,980
το μικρότερο στοιχείο αδιαχώριστα.

39
00:02:05,980 --> 00:02:09,350
Έτσι ακόμα κι αν οι άνθρωποι μπορούμε να δούμε αμέσως ότι το 4 είναι

40
00:02:09,350 --> 00:02:12,300
το ελάχιστο στοιχείο, ο αλγόριθμος μας θα πρέπει να εξετάσουμε

41
00:02:12,300 --> 00:02:15,710
αδιαχώριστα κάθε στοιχείο, ακόμη και μετά βρήκαμε τα 4 - το

42
00:02:15,710 --> 00:02:16,860
ελάχιστο στοιχείο.

43
00:02:16,860 --> 00:02:19,900
Έτσι, τώρα που βρήκαμε το ελάχιστο στοιχείο, 4, θα ήθελα

44
00:02:19,900 --> 00:02:23,410
για να προχωρήσουμε προς το ταξινομημένο τμήμα του καταλόγου.

45
00:02:23,410 --> 00:02:27,320
Δεδομένου ότι αυτό είναι το πρώτο βήμα, αυτό σημαίνει θέλουμε να θέσουμε σε 4

46
00:02:27,320 --> 00:02:29,680
η αρχή της λίστας.

47
00:02:29,680 --> 00:02:33,040
23 τώρα είναι στην αρχή της λίστας, έτσι

48
00:02:33,040 --> 00:02:36,080
ας ανταλλάξουν το 4 και το 23.

49
00:02:36,080 --> 00:02:38,870
Έτσι τώρα λίστα μας μοιάζει με αυτό.

50
00:02:38,870 --> 00:02:42,710
Γνωρίζουμε ότι το 4 θα πρέπει να είναι στην τελική θέση του, επειδή είναι

51
00:02:42,710 --> 00:02:45,890
τόσο το μικρότερο στοιχείο και το στοιχείο κατά την έναρξη

52
00:02:45,890 --> 00:02:46,960
του καταλόγου.

53
00:02:46,960 --> 00:02:50,650
Έτσι, αυτό σημαίνει ότι δεν θα χρειαστεί ποτέ να το μετακινήσετε πάλι.

54
00:02:50,650 --> 00:02:53,910
Ας επαναλάβετε αυτή τη διαδικασία για να προσθέσετε ένα άλλο στοιχείο για την

55
00:02:53,910 --> 00:02:55,910
ταξινομημένο τμήμα του καταλόγου.

56
00:02:55,910 --> 00:02:58,950
Γνωρίζουμε ότι δεν χρειάζεται να εξετάσουμε το 4, γιατί είναι

57
00:02:58,950 --> 00:03:00,000
ήδη ταξινομημένο.

58
00:03:00,000 --> 00:03:03,540
Έτσι, μπορούμε να ξεκινήσουμε από την 42, η οποία θα θυμούνται ως το

59
00:03:03,540 --> 00:03:05,290
ελάχιστο στοιχείο.

60
00:03:05,290 --> 00:03:08,700
Έτσι, το επόμενο θα εξετάσουμε την 23 η οποία είναι μικρότερη από 42, έτσι ώστε να

61
00:03:08,700 --> 00:03:11,620
23 είναι να θυμάστε το νέο ελάχιστο.

62
00:03:11,620 --> 00:03:14,870
Επόμενο βλέπουμε την 16 η οποία είναι μικρότερη από 23, έτσι

63
00:03:14,870 --> 00:03:16,800
16 είναι το νέο ελάχιστο.

64
00:03:16,800 --> 00:03:19,720
Τώρα κοιτάξουμε την 8 η οποία είναι μικρότερη από 16, έτσι

65
00:03:19,720 --> 00:03:21,130
8 είναι το νέο ελάχιστο.

66
00:03:21,130 --> 00:03:25,900
Και τέλος 8 είναι μικρότερη από 15, έτσι ξέρουμε ότι το 8 είναι ένα ελάχιστο

67
00:03:25,900 --> 00:03:27,780
αδιαχώριστα στοιχείο.

68
00:03:27,780 --> 00:03:30,660
Έτσι, αυτό σημαίνει ότι θα πρέπει να προσαρτήσει 8 στην ταξινόμηση

69
00:03:30,660 --> 00:03:32,450
μέρος της λίστας.

70
00:03:32,450 --> 00:03:35,990
Αυτή τη στιγμή 4 είναι το μόνο στοιχείο ταξινομημένο, έτσι θέλουμε να τοποθετήσετε

71
00:03:35,990 --> 00:03:38,410
το 8 δίπλα στο 4.

72
00:03:38,410 --> 00:03:41,920
Από το 42 είναι το πρώτο στοιχείο στην αδιαχώριστων τμήμα του

73
00:03:41,920 --> 00:03:47,260
λίστα, θα θέλετε να ανταλλάξετε το 42 και το 8.

74
00:03:47,260 --> 00:03:49,680
Έτσι τώρα λίστα μας μοιάζει με αυτό.

75
00:03:49,680 --> 00:03:53,830
4 και 8 αντιπροσωπεύουν την ταξινόμηση τμήμα του καταλόγου, και το

76
00:03:53,830 --> 00:03:56,440
υπόλοιποι αριθμοί αντιπροσωπεύουν τη μη ταξινομημένα

77
00:03:56,440 --> 00:03:58,260
μέρος της λίστας.

78
00:03:58,260 --> 00:04:00,630
Ας συνεχίσουμε με μια άλλη επανάληψη.

79
00:04:00,630 --> 00:04:03,850
Ξεκινάμε με 23 αυτή τη φορά, από τη στιγμή που δεν χρειάζεται να εξετάσουμε

80
00:04:03,850 --> 00:04:05,770
το 4 και το 8 πια γιατί έχω

81
00:04:05,770 --> 00:04:07,660
ήδη ταξινομημένο.

82
00:04:07,660 --> 00:04:10,270
16 είναι μικρότερο από 23, έτσι θα θυμόμαστε

83
00:04:10,270 --> 00:04:12,070
16 ως το νέο ελάχιστο.

84
00:04:12,070 --> 00:04:18,149
16 είναι μικρότερη από 42, αλλά 15 είναι μικρότερη από 16, οπότε θα πρέπει να είναι 15

85
00:04:18,149 --> 00:04:20,480
το ελάχιστο στοιχείο αδιαχώριστα.

86
00:04:20,480 --> 00:04:24,580
Έτσι, τώρα θέλουμε να ανταλλάξουν το 15 και το 23 για να

87
00:04:24,580 --> 00:04:26,310
να μας δώσει αυτή τη λίστα.

88
00:04:26,310 --> 00:04:30,500
Η ταξινόμηση τμήμα του κατάλογος αποτελείται από 4, 8 και 15, και

89
00:04:30,500 --> 00:04:33,210
Τα στοιχεία αυτά εξακολουθούν να έχουν υποστεί διαλογή.

90
00:04:33,210 --> 00:04:36,900
Αλλά είναι ακριβώς έτσι συμβαίνει ότι το επόμενο στοιχείο αδιαχώριστα, 16,

91
00:04:36,900 --> 00:04:38,480
είναι ήδη ταξινομημένο.

92
00:04:38,480 --> 00:04:42,060
Ωστόσο, δεν υπάρχει κανένας τρόπος για τον αλγόριθμο μας να γνωρίζουμε ότι 16

93
00:04:42,060 --> 00:04:45,230
είναι ήδη σε σωστή θέση του, γι 'αυτό πρέπει ακόμα να

94
00:04:45,230 --> 00:04:47,870
επαναλάβετε ακριβώς την ίδια διαδικασία.

95
00:04:47,870 --> 00:04:53,750
Έτσι βλέπουμε ότι το 16 είναι μικρότερη από 42, και 16 είναι μικρότερη από 23, έτσι

96
00:04:53,750 --> 00:04:56,230
16 πρέπει να είναι το ελάχιστο στοιχείο.

97
00:04:56,230 --> 00:04:59,010
Είναι αδύνατο να ανταλλάξετε το στοιχείο αυτό με τον εαυτό του, ώστε να μπορούμε να

98
00:04:59,010 --> 00:05:01,780
απλά αφήστε το σε αυτήν τη θέση.

99
00:05:01,780 --> 00:05:04,660
Έτσι, χρειαζόμαστε ένα ακόμα πέρασμα του αλγορίθμου μας.

100
00:05:04,660 --> 00:05:09,370
42 είναι μεγαλύτερη από 23, οπότε 23 πρέπει να είναι η

101
00:05:09,370 --> 00:05:10,970
αδιαχώριστα ελάχιστο στοιχείο.

102
00:05:10,970 --> 00:05:17,410
Μόλις έχουμε ανταλλάξει το 23 και το 42, θα καταλήξουμε με την τελική μας

103
00:05:17,410 --> 00:05:18,530
ταξινομημένη λίστα -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Γνωρίζουμε 42 πρέπει να είναι στη σωστή θέση, δεδομένου ότι είναι η

106
00:05:26,830 --> 00:05:30,210
μόνο στοιχείο που έφυγε, και αυτό είναι το είδος επιλογής.

107
00:05:30,210 --> 00:05:32,100
Ας επισημοποιήσει τώρα αλγόριθμος μας με κάποια

108
00:05:32,100 --> 00:05:34,540
ψευδοκώδικα.

109
00:05:34,540 --> 00:05:37,760
On line ένα, μπορούμε να δούμε ότι πρέπει να ενσωματωθούν σε

110
00:05:37,760 --> 00:05:39,530
κάθε στοιχείο της λίστας.

111
00:05:39,530 --> 00:05:42,150
Εκτός από το τελευταίο στοιχείο, δεδομένου ότι το στοιχείο 1

112
00:05:42,150 --> 00:05:44,230
κατάλογος είναι ήδη ταξινομημένο.

113
00:05:44,230 --> 00:05:48,100
On line δύο, θεωρούμε ότι το πρώτο στοιχείο της μη διαχωρισμένων

114
00:05:48,100 --> 00:05:51,080
τμήμα του πίνακα να είναι η ελάχιστη, όπως κάναμε με μας

115
00:05:51,080 --> 00:05:53,750
παράδειγμα, έτσι ώστε να έχουμε κάτι να συγκριθεί με.

116
00:05:53,750 --> 00:05:57,260
Γραμμή τρία αρχίζει μια δεύτερη θηλιά στην οποία θα επαναλάβει πάνω

117
00:05:57,260 --> 00:05:59,170
κάθε στοιχείο αδιαχώριστα.

118
00:05:59,170 --> 00:06:02,150
Γνωρίζουμε ότι μετά από i επαναλήψεις, το ταξινομημένο τμήμα

119
00:06:02,150 --> 00:06:05,330
του καταλόγου μας θα πρέπει να έχουν i στοιχεία σε αυτό, δεδομένου ότι κάθε βήμα

120
00:06:05,330 --> 00:06:06,890
ταξινομεί ένα στοιχείο.

121
00:06:06,890 --> 00:06:11,770
Έτσι, το πρώτο στοιχείο αδιαχώριστα πρέπει να είναι σε θέση i συν 1.

122
00:06:11,770 --> 00:06:15,440
On line τέσσερα, συγκρίνουμε το τρέχον στοιχείο στο ελάχιστο

123
00:06:15,440 --> 00:06:17,750
στοιχείο που έχουμε δει μέχρι τώρα.

124
00:06:17,750 --> 00:06:20,560
Εάν το τρέχον στοιχείο είναι μικρότερη από την ελάχιστη

125
00:06:20,560 --> 00:06:23,870
στοιχείου, τότε θυμόμαστε το τρέχον στοιχείο ως νέα

126
00:06:23,870 --> 00:06:26,250
ελάχιστο στη γραμμή πέντε.

127
00:06:26,250 --> 00:06:29,900
Τέλος, στις γραμμές έξι και επτά, έχουμε ανταλλάξει το ελάχιστο

128
00:06:29,900 --> 00:06:33,080
στοιχείου με το πρώτο στοιχείο αδιαχώριστα, έτσι

129
00:06:33,080 --> 00:06:36,990
προσθήκη του στην ταξινόμηση μέρος της λίστας.

130
00:06:36,990 --> 00:06:40,030
Μόλις έχουμε έναν αλγόριθμο, ένα σημαντικό ερώτημα που τίθεται

131
00:06:40,030 --> 00:06:43,370
τους εαυτούς μας ως προγραμματιστές είναι πόσο καιρό έκανε να πάρει;

132
00:06:43,370 --> 00:06:46,970
Θα ρωτήσω πρώτα το ερώτημα πόσο καιρό παίρνει για αυτό

133
00:06:46,970 --> 00:06:50,070
αλγόριθμο για να τρέξει στη χειρότερη περίπτωση;

134
00:06:50,070 --> 00:06:51,640
Ανάκληση εμείς εκπροσωπούμε την λειτουργία

135
00:06:51,640 --> 00:06:55,060
χρόνο με μεγάλο συμβολισμό O.

136
00:06:55,060 --> 00:06:58,650
Προκειμένου να προσδιορισθεί η ελάχιστη αδιαχώριστα στοιχείου, εμείς

137
00:06:58,650 --> 00:07:01,880
ουσιαστικά έπρεπε να συγκρίνει κάθε στοιχείο στη λίστα για να

138
00:07:01,880 --> 00:07:04,040
κάθε άλλο στοιχείο στη λίστα.

139
00:07:04,040 --> 00:07:08,430
Διαισθητικά, αυτό ακούγεται σαν ένα O n τετράγωνο του λειτουργία.

140
00:07:08,430 --> 00:07:12,050
Κοιτάζοντας ψευδοκώδικα μας, έχουμε επίσης ένα βρόχο ένθετα στο εσωτερικό

141
00:07:12,050 --> 00:07:14,420
άλλο βρόχο, η οποία μάλιστα ακούγεται σαν O

142
00:07:14,420 --> 00:07:16,480
κ τετράγωνο λειτουργίας.

143
00:07:16,480 --> 00:07:19,250
Ωστόσο, να θυμάστε ότι δεν χρειάζεται να κοιτάξουν πέρα ​​από το

144
00:07:19,250 --> 00:07:23,460
Ολόκληρη η λίστα για τον καθορισμό της ελάχιστης αδιαχώριστα στοιχείο;

145
00:07:23,460 --> 00:07:26,600
Μόλις γνωρίζαμε ότι το 4 ήταν ταξινομημένο, για παράδειγμα, δεν

146
00:07:26,600 --> 00:07:28,170
πρέπει να το δει κανείς και πάλι.

147
00:07:28,170 --> 00:07:31,020
Έτσι το κάνει αυτό κάτω το χρόνο λειτουργίας;

148
00:07:31,020 --> 00:07:34,510
Για την λίστα μας μήκους 6, έπρεπε να κάνω πέντε

149
00:07:34,510 --> 00:07:37,990
συγκρίσεις για το πρώτο στοιχείο, τέσσερις για συγκρίσεις

150
00:07:37,990 --> 00:07:40,750
το δεύτερο στοιχείο, και ούτω καθεξής.

151
00:07:40,750 --> 00:07:44,690
Αυτό σημαίνει ότι ο συνολικός αριθμός των σταδίων είναι το άθροισμα των

152
00:07:44,690 --> 00:07:49,160
οι ακέραιοι από το 1 έως το μήκος του καταλόγου μείον 1.

153
00:07:49,160 --> 00:07:51,005
Μπορούμε να αντιπροσωπεύει αυτό με μια άθροιση.

154
00:07:57,980 --> 00:07:59,910
Δεν θα υπεισέλθω σε αθροίσματα εδώ.

155
00:07:59,910 --> 00:08:04,900
Αλλά φαίνεται ότι αυτή η άθροιση είναι ίσο με n φορές

156
00:08:04,900 --> 00:08:07,540
n μείον 1 σε 2.

157
00:08:07,540 --> 00:08:14,220
Ή ισοδύναμα, n τετράγωνο πάνω από 2 μείον n πάνω από 2.

158
00:08:14,220 --> 00:08:18,860
Όταν μιλάμε για ασυμπτωτική runtime, αυτό το τετράγωνο n όρος

159
00:08:18,860 --> 00:08:22,070
πρόκειται να κυριαρχήσει αυτό το ν όρο.

160
00:08:22,070 --> 00:08:27,850
Έτσι, είναι είδος επιλογή του n O τετράγωνο.

161
00:08:27,850 --> 00:08:31,460
Υπενθυμίζουμε ότι στο παράδειγμά μας, το είδος επιλογής εξακολουθούν να χρειάζονται να

162
00:08:31,460 --> 00:08:33,850
ελέγχει αν ένας αριθμός που ήταν ήδη ταξινομημένο

163
00:08:33,850 --> 00:08:35,450
που απαιτούνται για να μετακινηθούν.

164
00:08:35,450 --> 00:08:38,929
Έτσι, αυτό σημαίνει ότι αν τρέξαμε είδος επιλογής κατά τη διάρκεια μιας ήδη

165
00:08:38,929 --> 00:08:43,070
ταξινομημένο κατάλογο, θα απαιτούσε τον ίδιο αριθμό βημάτων όπως είναι

166
00:08:43,070 --> 00:08:46,340
όταν θα τρέχει πάνω από ένα εντελώς αδιαχώριστα λίστα.

167
00:08:46,340 --> 00:08:51,470
Έτσι, το είδος επιλογής έχει καλύτερη απόδοση περίπτωση του n στο τετράγωνο,

168
00:08:51,470 --> 00:08:56,820
την οποία εμείς εκπροσωπούμε με ωμέγα n τετράγωνο.

169
00:08:56,820 --> 00:08:58,600
Και αυτό είναι το είδος για την επιλογή.

170
00:08:58,600 --> 00:09:00,630
Μόνο ένα από τα πολλά αλγορίθμων μπορούμε

171
00:09:00,630 --> 00:09:02,390
χρησιμοποιήσετε για να ταξινομήσετε μια λίστα.

172
00:09:02,390 --> 00:09:05,910
Το όνομά μου είναι ο Tommy, και αυτό είναι CS50.