1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> ΟΜΙΛΗΤΗΣ: Εντάξει, αυτό είναι CS50.

3
00:00:14,910 --> 00:00:19,020
Αυτό είναι το τέλος των τριών εβδομάδων, και εάν
που δεν έχουν επωφεληθεί ήδη,

4
00:00:19,020 --> 00:00:21,790
γνωρίζουν ότι θα υπάρξει γεύμα
αυτή την Παρασκευή ως συνήθως, όπου

5
00:00:21,790 --> 00:00:25,430
μπορείτε να απολαύσετε καλή κουβέντα
και το φαγητό στο Fire and Ice

6
00:00:25,430 --> 00:00:27,980
με μερικά από τα CS50 του
το προσωπικό και τους συμμαθητές.

7
00:00:27,980 --> 00:00:30,170
Επικεφαλής σε αυτή τη διεύθυνση URL εδώ.

8
00:00:30,170 --> 00:00:33,420
>> Τώρα μπορείτε να ανακαλέσετε ή να σας
μπορεί σύντομα να εξοικειωθούν με,

9
00:00:33,420 --> 00:00:35,970
αυτά τα πράγματα εδώ, η οποία
δίνονται στο τέλος

10
00:00:35,970 --> 00:00:37,850
του εξαμήνου για πολλές κατηγορίες.

11
00:00:37,850 --> 00:00:40,870
Λεγόμενη εξετάσεις μπλε βιβλία, στο οποίο
γράψετε τις απαντήσεις σας σε εξετάσεις.

12
00:00:40,870 --> 00:00:44,240
Τώρα έχω εδώ 26, όπως
μπλε βιβλία, για καθένα από αυτά

13
00:00:44,240 --> 00:00:47,580
είναι γραμμένο ένα όνομα, A έως το Z. Και
Πράγματι, τα ονόματα είναι τόσο απλό, A

14
00:00:47,580 --> 00:00:50,490
μέσω Z. Και ένα από
οι στόχοι στο χέρι σήμερα

15
00:00:50,490 --> 00:00:53,910
πρόκειται να είναι η συνέχιση της
ξεκινήσαμε τη Δευτέρα, η οποία δεν είναι

16
00:00:53,910 --> 00:00:57,830
τόσα πολλά κοιτάζοντας τον κωδικό, αλλά πραγματικά
κοιτάζοντας τις ιδέες και την επίλυση προβλημάτων.

17
00:00:57,830 --> 00:01:00,170
Ένας από τους στόχους και
υποσχέσεις του μαθήματος

18
00:01:00,170 --> 00:01:02,985
είναι να σας διδάξει να σκέφτονται περισσότερο
προσεκτικά, πιο μεθοδικά,

19
00:01:02,985 --> 00:01:05,400
και να λύσει τα προβλήματα πιο αποτελεσματικά.

20
00:01:05,400 --> 00:01:09,526
Και πράγματι, μπορούμε να το κάνουμε αυτό πραγματικά
χωρίς καν να αγγίξει ούτε μια γραμμή κώδικα.

21
00:01:09,526 --> 00:01:12,150
Έτσι έχω ένα ζευγάρι των ελεφάντων
εδώ σήμερα, πορτοκαλί και μπλε,

22
00:01:12,150 --> 00:01:15,780
αν θα μπορούσαμε να πάρουμε έναν εθελοντή,
ίσως από το πιο πίσω από ό, τι συνήθως.

23
00:01:15,780 --> 00:01:18,070
Πόσο περίπου εκεί, έλα κάτω.

24
00:01:18,070 --> 00:01:24,180
Ο στόχος της οποίας πρόκειται να είναι σε
βοηθήσει συν τη διαχείριση αυτού του εξετάσεις εδώ.

25
00:01:24,180 --> 00:01:24,935
Ποιο είναι το όνομά σου;

26
00:01:24,935 --> 00:01:25,768
>> ΚΟΙΝΟ: Μαίρη Μπεθ.

27
00:01:25,768 --> 00:01:27,560
ΟΜΙΛΗΤΗΣ: Μαίρη Μπεθ, έλα επάνω.

28
00:01:27,560 --> 00:01:29,560
Επιτρέψτε μου να πάρει το μικρόφωνο εδώ για εσάς.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Χαίρω πολύ.

31
00:01:32,880 --> 00:01:34,005
>> ΚΟΙΝΟ: Χαίρω πολύ.

32
00:01:34,005 --> 00:01:36,790
ΟΜΙΛΗΤΗΣ: Εντάξει, έτσι έχω
Εδώ μπλε βιβλία Α έως το Ω,

33
00:01:36,790 --> 00:01:41,680
και Πάω να προσποιηθώ ότι
Έχω ένας από τους μαθητές,

34
00:01:41,680 --> 00:01:45,770
και έρχονται σε κάπως τυχαία
στο τέλος του τρεις ώρες μπλοκ εξετάσεις,

35
00:01:45,770 --> 00:01:49,400
έτσι ώστε όπου και αν καταλήξουν σε κάποια
ημι-τυχαία σειρά, όπως αυτό.

36
00:01:49,400 --> 00:01:54,510
Τώρα η δουλειά σας σε μια στιγμή θα
να είναι-- αυτό είναι στην πραγματικότητα το πώς παίρνουν

37
00:01:54,510 --> 00:01:56,820
γύρισε σε κατά το τέλος της
η τάξη, το πιο πιθανό.

38
00:01:56,820 --> 00:02:01,120
Η δουλειά σου τώρα πρόκειται να είναι, αρκετά
Με απλά λόγια, για να ταξινομήσετε αυτά τα μπλε βιβλία για εμάς

39
00:02:01,120 --> 00:02:05,220
από το Α έως το Z.

40
00:02:05,220 --> 00:02:08,400
>> ΚΟΙΝΟ: Ω, αυτό είναι
πρόκειται να πάρει για πάντα.

41
00:02:08,400 --> 00:02:13,747
>> ΟΜΙΛΗΤΗΣ: Και εμείς θα παρακολουθήσουν
όπως μπορείτε να το κάνετε αυτό, δεν υπάρχει πίεση.

42
00:02:13,747 --> 00:02:15,330
ΚΟΙΝΟ: Όχι, δεν υπάρχει πίεση ή οτιδήποτε άλλο.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> ΟΜΙΛΗΤΗΣ: Και για τη διασκέδαση,
ας βάλουμε ένα χρονόμετρο.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> ΚΟΙΝΟ: So much fun, τόσο πολλή διασκέδαση.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> ΟΜΙΛΗΤΗΣ: Μπορώ να κρατήσει το μικρόφωνο για σας.

49
00:02:38,574 --> 00:02:40,240
Εντάξει, έχουμε μόλις διπλασίασε την ταχύτητα μας.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Έτσι, εν τω μεταξύ, επιτρέψτε μου να δημιουργήσει ό, τι είναι
πρόκειται να είναι η ερώτηση για Μαίρη Μπεθ

52
00:02:49,060 --> 00:02:51,540
είναι τι κάνει αυτή, πώς είναι
Πάει για την επίλυση αυτό;

53
00:02:51,540 --> 00:02:54,040
Και στην πραγματικότητα, δεν θα μπορούσε να έχει
ποτέ σκεφτεί κάτι

54
00:02:54,040 --> 00:02:57,440
τόσο απλό, όπως όταν επιλέγετε
μέχρι 26 βιβλία σαν αυτό,

55
00:02:57,440 --> 00:02:59,350
τα οποία έχουν μια φυσική
παραγγελία για να τους.

56
00:02:59,350 --> 00:03:01,335
Ποια είναι η διαδικασία
ότι μπορείτε πραγματικά να χρησιμοποιήσετε;

57
00:03:01,335 --> 00:03:03,770
Είναι μάλλον τυχαία ακριβώς
να πάρει το πρώτο που βλέπετε

58
00:03:03,770 --> 00:03:05,250
και βάζοντας στη θέση του;

59
00:03:05,250 --> 00:03:09,680
Μήπως πρώτα να μετακινήσετε τα χέρια σας γύρω από
ψάχνει για μια συνέχεια ψάχνει για B;

60
00:03:09,680 --> 00:03:11,722
Μην παίρνετε μια ματιά σε ένα
ζεύγος τους δίπλα-δίπλα

61
00:03:11,722 --> 00:03:14,680
και απλώς να πω, περιμένετε ένα λεπτό, αυτό
Δεν είναι σωστό, και στη συνέχεια να ανταλλάξουν τη σειρά;

62
00:03:14,680 --> 00:03:16,960
Είδαμε ήδη τη Δευτέρα
ότι υπάρχει ένας αριθμός τρόπων

63
00:03:16,960 --> 00:03:22,140
στο οποίο μπορούμε να το κάνουμε αυτό, και
Πράγματι, καθώς πλησιάζει το τέλος εδώ,

64
00:03:22,140 --> 00:03:26,360
Θα ήθελα να λάβει γνώση ίσως
από ό, τι Μαίρη Μπεθ κάνει.

65
00:03:26,360 --> 00:03:30,040
Έχουμε μερικά σωρούς φαίνεται, ένα
μεγαλύτερο από ένα, τρία μικρότερα.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> ΚΟΙΝΟ: Είμαι τους παραγγελία
όταν βρω δύο γράμματα

68
00:03:36,415 --> 00:03:39,540
Ξέρω ότι είναι μαζί σε μια σειρά,
Τους έβαλα μαζί έτσι ώστε να μπορώ να μην κάνω

69
00:03:39,540 --> 00:03:42,915
πρέπει να ανησυχείτε για τη διατήρηση
κομμάτι μιας ολόκληρης σειράς βιβλίων.

70
00:03:42,915 --> 00:03:45,706
Είναι απλά, ω, Α είναι η πρώτη,
Έχω αυτό το stack εδώ.

71
00:03:45,706 --> 00:03:47,580
ΟΜΙΛΗΤΗΣ: Έτσι, σχεδόν σαν
ένα τα κομμάτια του παζλ, ότι

72
00:03:47,580 --> 00:03:49,860
έχει το σωστό σχήμα για να
ταιριάζουν με το άλλο.

73
00:03:49,860 --> 00:03:51,026
ΚΟΙΝΟ: Λίγο πολύ, ναι.

74
00:03:51,026 --> 00:03:55,320
ΟΜΙΛΗΤΗΣ: Εντάξει, εξαιρετική.

75
00:03:55,320 --> 00:03:59,850
Και τώρα κάθε μία από αυτές
σωρούς είναι προφανώς ταξινομούνται;

76
00:03:59,850 --> 00:04:00,990
>> ΚΟΙΝΟ: Ναι.

77
00:04:00,990 --> 00:04:09,900
>> ΟΜΙΛΗΤΗΣ: Εντάξει, A έως Z. Όλα
δεξιά, συγχαρητήρια, τα κατάφερες.

78
00:04:09,900 --> 00:04:11,461
Έχετε την επιλογή σας.

79
00:04:11,461 --> 00:04:11,960
Blue;

80
00:04:11,960 --> 00:04:13,530
Εντάξει, σας ευχαριστώ για αυτό.

81
00:04:13,530 --> 00:04:16,679
Έτσι, Μαίρη Μπεθ είχε προτείνει
ποια είναι η προσέγγισή της ήταν,

82
00:04:16,679 --> 00:04:19,720
αλλά αυτό είναι μια άλλη προσέγγιση το πώς θα
θα μπορούσε να πάει για διαλογή αυτά τα πράγματα;

83
00:04:19,720 --> 00:04:21,130
Τι θα κάνατε;

84
00:04:21,130 --> 00:04:24,060
Το ρεκόρ για να νικήσει θα ήταν
ένα λεπτό και 50 δευτερόλεπτα ή έτσι,

85
00:04:24,060 --> 00:04:26,039
συν αυτά που ξέχασα να μετρήσει.

86
00:04:26,039 --> 00:04:27,080
Τι θα κάνατε;

87
00:04:27,080 --> 00:04:27,579
Ναι;

88
00:04:27,579 --> 00:04:28,735
ΚΟΙΝΟ: Πάρτε τη στοίβα.

89
00:04:28,735 --> 00:04:29,776
Ξεκινήστε από την αρχή.

90
00:04:29,776 --> 00:04:32,284
Ελέγξτε τα χαρτιά σας.

91
00:04:32,284 --> 00:04:36,586
Και αν η κορυφή ενός είναι υψηλότερη
ό, τι, ίσως, είναι,

92
00:04:36,586 --> 00:04:38,980
το κάτω μέρος είναι ένα
υψηλότερη, τότε ανάβουν.

93
00:04:38,980 --> 00:04:41,300
>> ΟΜΙΛΗΤΗΣ: Εντάξει, έτσι ξεκινώντας
στην κορυφή και τον πυθμένα,

94
00:04:41,300 --> 00:04:43,716
και, στη συνέχεια, τον τρόπο εργασίας σας
προς τα μέσα έτσι, την εναλλαγή τους;

95
00:04:43,716 --> 00:04:46,580
Εντάξει, έτσι είναι λίγο παρόμοια
στο πνεύμα με bubble sort,

96
00:04:46,580 --> 00:04:49,160
αλλά η επιλογή των άκρων
Δεν τα γειτονικά ζεύγη.

97
00:04:49,160 --> 00:04:52,080
Αλλά η μικρή του είναι ότι δεν υπάρχει
σίγουρα ένα σωρό διαφορετικούς τρόπους

98
00:04:52,080 --> 00:04:54,210
θα μπορούσαμε να το κάνουμε αυτό, και
Ειλικρινά, νομίζω ότι εσύ το είδος της

99
00:04:54,210 --> 00:04:55,700
υιοθέτησε ένα ζευγάρι προσεγγίσεις, σωστά;

100
00:04:55,700 --> 00:05:00,567
Κάνατε το είδος των τεσσάρων ταξινομημένων σωρούς, και
στη συνέχεια να συγχωνευθεί μαζί αποτελεσματικά.

101
00:05:00,567 --> 00:05:02,650
Και αυτό είναι, τολμούσα να πω, ένα άλλο
τεχνική εντελώς.

102
00:05:02,650 --> 00:05:06,950
Δεν το αντιμετωπίζουν ως ένα μεγάλο σωρό,
θα διαιρεθεί το πρόβλημα σε τέσσερα τετράκλινα,

103
00:05:06,950 --> 00:05:09,820
αν θέλετε, και στη συνέχεια με κάποιο τρόπο
συγχωνεύθηκε τους στο τέλος.

104
00:05:09,820 --> 00:05:13,410
>> Έτσι, ας αναλογιστούμε, τελικά,
πώς αλλιώς θα μπορούσαμε να το κάνουμε αυτό.

105
00:05:13,410 --> 00:05:15,860
Εμείς τυποποίησε την έννοια
του bubble sort τελευταία φορά,

106
00:05:15,860 --> 00:05:18,780
και bubble sort ανάκληση ήταν μια
αλγόριθμο που οπτικοποιείται

107
00:05:18,780 --> 00:05:22,640
με οκτώ από τους συμμαθητές σας μέχρι εδώ,
φαινομενικά τυχαία κατατάσσονται στην πρώτη.

108
00:05:22,640 --> 00:05:26,110
Και στη συνέχεια αποφάσισε κατά ζεύγη, εάν
δύο στοιχεία που είναι εκτός λειτουργίας,

109
00:05:26,110 --> 00:05:26,950
απλά να τους swap.

110
00:05:26,950 --> 00:05:28,930
Έτσι, τέσσερις και δύο είναι
προφανώς εκτός λειτουργίας,

111
00:05:28,930 --> 00:05:31,080
έτσι ώστε αυτές οι δύο συμμαθητές
θέσεις μεταγωγής.

112
00:05:31,080 --> 00:05:35,390
Και τότε θα επαναληφθεί με τέσσερα και έξι,
στη συνέχεια, έξι και οκτώ, σε κάθε επανάληψη,

113
00:05:35,390 --> 00:05:36,980
κινείται προς τα δεξιά.

114
00:05:36,980 --> 00:05:42,590
>> Έτσι, δίνεται οκτώ άτομα, πόσα ζεύγη
συγκρίσεις έκανα, ενώ το περπάτημα από

115
00:05:42,590 --> 00:05:45,220
αριστερά προς τα δεξιά σε μία τέτοια επανάληψη;

116
00:05:45,220 --> 00:05:48,410
Πόσες συγκρίσεις;

117
00:05:48,410 --> 00:05:49,197
Επτά, σωστά;

118
00:05:49,197 --> 00:05:51,405
Διότι, αν υπάρχουν οκτώ
ανθρώπους, αλλά έχετε το ζεύγος

119
00:05:51,405 --> 00:05:53,880
τους και να σας κρατήσει κινείται
ένα hop προς τα δεξιά,

120
00:05:53,880 --> 00:05:56,060
δεν πρόκειται να έχει οκτώ
συγκρίσεις, επειδή δεν μπορείτε να συγκρίνετε

121
00:05:56,060 --> 00:05:59,226
ένα στοιχείο ενάντια στο ίδιο, ή θα ήταν
απλά είναι άχρηστη, έτσι ώστε να έχουν επτά.

122
00:05:59,226 --> 00:06:01,290
Ή πιο γενικά, αν
έχουμε n άτομα, εμείς

123
00:06:01,290 --> 00:06:04,300
κάνει n μείον 1 συγκρίσεις
με bubble sort.

124
00:06:04,300 --> 00:06:08,150
>> Ας εξετάσουμε τώρα το πόσο καλή ή
κακή bubble sort πραγματικά ήταν, και προσπαθήστε

125
00:06:08,150 --> 00:06:13,570
για να δώσουμε στον εαυτό μας λεξιλόγιο με
η οποία σε αλγόριθμους κριτική, όπως αυτή,

126
00:06:13,570 --> 00:06:14,430
και σύντομα τη δική μας.

127
00:06:14,430 --> 00:06:16,970
Έτσι, το πρώτο πέρασμα μέσω
bubble sort, η πρώτη φορά

128
00:06:16,970 --> 00:06:20,909
Περπάτησα από αριστερά προς τα δεξιά κατά μήκος της
στάδιο, με n μείον 1 συγκρίσεις πήρε.

129
00:06:20,909 --> 00:06:22,950
Και αυτό πρόκειται να μου
μονάδα μέτρησης, σωστά;

130
00:06:22,950 --> 00:06:26,170
Ήμουν είδος μιλάμε και περίπατο,
κάπως γρήγορα, κάπως αργά,

131
00:06:26,170 --> 00:06:29,300
έτσι μετρώντας τον αριθμό μου από δευτερόλεπτα
δεν είναι ιδιαίτερα εύγλωττο,

132
00:06:29,300 --> 00:06:32,260
αλλά μετρώντας τον αριθμό των
επιχειρήσεις που έκανα τη Δευτέρα,

133
00:06:32,260 --> 00:06:35,900
συγκρίνοντας τα δύο άτομα, που αισθάνεται
σαν ένα ωραίο μονάδα μέτρησης.

134
00:06:35,900 --> 00:06:40,980
>> Έτσι n μείον 1 βήματα την πρώτη φορά,
αλλά τότε τι συνέβη μετά από αυτό;

135
00:06:40,980 --> 00:06:46,610
Ποιο είναι το ένα ανάποδα από ένα πέρασμα
μέσω μιας κατά τα άλλα μη ταξινομημένα λίστα;

136
00:06:46,610 --> 00:06:49,840
Τι μπορείτε να μου πείτε σχετικά με το στοιχείο
ο οποίος ήταν σε όλη τη διαδρομή πάνω από εκεί;

137
00:06:49,840 --> 00:06:51,300
Ναι;

138
00:06:51,300 --> 00:06:52,870
Αυτό ήταν το μεγαλύτερο στοιχείο, σωστά;

139
00:06:52,870 --> 00:06:55,710
Αριθμός οκτώ, ακόμη κι αν
ξεκίνησε εδώ, κάθε φορά που

140
00:06:55,710 --> 00:06:57,860
σε σύγκριση με την κατά
ένας γείτονας, συνέχισε

141
00:06:57,860 --> 00:07:00,480
αναβλύζει προς τα δεξιά
πλευρά της λίστας.

142
00:07:00,480 --> 00:07:02,710
Και πράγματι, αυτό είναι όπου
ο αλγόριθμος παίρνει το όνομά του.

143
00:07:02,710 --> 00:07:07,630
>> Τώρα, με αυτή τη λογική, πόσες συγκρίσεις
πρέπει να κάνω για δεύτερη φορά

144
00:07:07,630 --> 00:07:09,800
Κάνω αυτό το πέρασμα από τα αριστερά προς τα δεξιά;

145
00:07:09,800 --> 00:07:10,730
n μείον 2, σωστά;

146
00:07:10,730 --> 00:07:14,297
Θα ήταν απλώς να χάνω τον χρόνο μου, αν μου
κρατήσει σύγκριση οκτώ εναντίον κάποιου

147
00:07:14,297 --> 00:07:16,630
αλλιώς γιατί γνωρίζουμε ήδη
ήταν στο σωστό μέρος.

148
00:07:16,630 --> 00:07:19,760
Έτσι, αυτό είναι ένα κομμάτι από ένα
βελτιστοποίησης, έτσι ώστε το επόμενο πέρασμα

149
00:07:19,760 --> 00:07:23,899
πρόκειται να είναι συν η πλην δύο στάδια,
όπου n είναι ο αριθμός των ανθρώπων.

150
00:07:23,899 --> 00:07:26,940
Τώρα μπορείτε να το είδος της προεκτείνουν, ακόμη
αν δεν είστε ένας επιστήμονας υπολογιστών,

151
00:07:26,940 --> 00:07:27,680
πώς τελειώνει.

152
00:07:27,680 --> 00:07:31,259
Στο τέλος αυτού του αλγορίθμου, πιθανώς
έχετε μόνο μία σύγκριση αριστερά.

153
00:07:31,259 --> 00:07:33,800
Θα πρέπει να καθορίσει το είδος της η
ξεκινώντας από τη λίστα στην περίπτωση δύο

154
00:07:33,800 --> 00:07:36,540
και ένα είναι εκτός λειτουργίας
και θα πρέπει να είναι ένα και δύο,

155
00:07:36,540 --> 00:07:40,330
έτσι ώστε αυτό να κατεβαίνουν από την
συν 1 τελικό σύγκριση.

156
00:07:40,330 --> 00:07:44,500
>> Τώρα η τελεία, τελεία, τελεία είδος των κυμάτων είναι
τα χέρια σε μερικά από τα πιο ζουμερό λεπτομέρειες,

157
00:07:44,500 --> 00:07:46,452
αλλά ας πάμε μπροστά και να απλοποιηθεί.

158
00:07:46,452 --> 00:07:48,660
Αν θυμάστε από την υψηλή
σχολείο, ειλικρινά, πολλοί από εσάς

159
00:07:48,660 --> 00:07:50,340
είχαν βιβλία μαθηματικών που είχε
ένα μικρό σκονάκι

160
00:07:50,340 --> 00:07:52,550
στο μπροστινό κάλυμμα ή ο
πίσω κάλυμμα που σας έδειξα

161
00:07:52,550 --> 00:07:56,400
αθροίσεις ποια σειρά, όπως
Αυτό τελικά προστίθεται μέχρι.

162
00:07:56,400 --> 00:07:59,600
Στη γενική περίπτωση, εάν έχετε μια
μεταβλητή, όπως n, και μάλιστα αυτό,

163
00:07:59,600 --> 00:08:01,634
αν κοίταξε σας
παλιό σχολείο μαθηματικά βιβλίο,

164
00:08:01,634 --> 00:08:04,050
θα δείτε ότι αυτό στην πραγματικότητα
προσθέτει μέχρι και το ποσό αυτό εδώ,

165
00:08:04,050 --> 00:08:07,970
n φορές n μείον 1 όλα διαιρείται δια 2.

166
00:08:07,970 --> 00:08:11,172
Έτσι, για τώρα επιτρέψτε μου να ορίζουν
Αυτό είναι αλήθεια, έτσι για ένα άλμα της πίστης,

167
00:08:11,172 --> 00:08:12,880
αυτό είναι που συνοψίζει αυτό
μέχρι, και θα μπορούσαμε να

168
00:08:12,880 --> 00:08:14,341
αποδεικνύουν ότι σε μια πιο γενική περίπτωση.

169
00:08:14,341 --> 00:08:15,590
Αλλά τώρα ας επεκτείνουν αυτό.

170
00:08:15,590 --> 00:08:19,920
Έτσι, ας πολλαπλασιάσουμε αυτό έξω, έτσι ώστε να είναι
n τετράγωνο, μείον n, όλα διαιρείται δια 2.

171
00:08:19,920 --> 00:08:23,200
Αυτό είναι πραγματικά n τετράγωνο,
διαιρείται δια 2, μείον n πάνω από 2,

172
00:08:23,200 --> 00:08:25,010
έτσι ώστε να είναι όλα ωραία και ενδιαφέρουσα.

173
00:08:25,010 --> 00:08:27,060
Αλλά τι θα συμβεί αν
plug-in αξίας;

174
00:08:27,060 --> 00:08:29,724
Ας υποθέσουμε ότι δεν είχα οκτώ
ανθρώπους, αλλά να πω ένα εκατομμύριο.

175
00:08:29,724 --> 00:08:31,890
Και ένα εκατομμύριο μόνο και μόνο επειδή
Είναι ένα αρκετά μεγάλο αριθμό,

176
00:08:31,890 --> 00:08:34,039
ας συνδέσετε αυτό και να δούμε τι θα συμβεί.

177
00:08:34,039 --> 00:08:39,039
Έτσι, εάν συνδέσετε ένα εκατομμύριο σε αυτό το τύπο
Πάω να πάρει ένα εκατομμύριο τετράγωνο,

178
00:08:39,039 --> 00:08:42,868
διαιρείται δια 2, μείον
εκατομμύρια, διαιρούμενο με το 2.

179
00:08:42,868 --> 00:08:44,159
Τώρα τι που πρόκειται να ισούται;

180
00:08:44,159 --> 00:08:47,354
Έτσι, τα 500 δισεκατομμύρια, μείον 500.000.

181
00:08:47,354 --> 00:08:49,270
Και αν μπορώ πραγματικά να κάνουμε
ότι τα μαθηματικά, αυτό σημαίνει ότι

182
00:08:49,270 --> 00:08:53,920
ότι η διαλογή ένα εκατομμύριο
οι άνθρωποι με το είδος φούσκα

183
00:08:53,920 --> 00:09:01,800
θα μπορούσε να μου πάρει 499999500000
βήματα ή συγκρίσεις στο τέλος,

184
00:09:01,800 --> 00:09:02,900
είμαστε απλά παρέκταση.

185
00:09:02,900 --> 00:09:06,860
>> Αυτό αισθάνεται αρκετά αργή, αλλά ειλικρινά
μετρώντας μία συγκεκριμένη είσοδο

186
00:09:06,860 --> 00:09:09,160
όπως αυτό, δεν είναι όλα αυτά που λέει.

187
00:09:09,160 --> 00:09:14,050
Αλλά πράγματι δεν δείχνουν ότι n
γίνεται όλο και μεγαλύτερο, αυτός ο αλγόριθμος

188
00:09:14,050 --> 00:09:16,280
το είδος του αισθάνεται χειρότερα και
χειρότερα, ή πραγματικά

189
00:09:16,280 --> 00:09:20,450
αρχίζουν να αισθάνονται τον πόνο του ότι
ύψωση σε δύναμη, ώστε ν τετράγωνο,

190
00:09:20,450 --> 00:09:21,770
η οποία προσθέτει επάνω αρκετά γρήγορα.

191
00:09:21,770 --> 00:09:25,340
Και αυτή η λεπτομέρεια δεν είναι
χάνεται στους ανθρώπους, στην πραγματικότητα,

192
00:09:25,340 --> 00:09:29,640
πριν από μερικά χρόνια ένα ορισμένο γερουσιαστής ο οποίος ήταν
εκστρατεία, κάθισε για μια συνέντευξη

193
00:09:29,640 --> 00:09:32,180
με τον Eric της Google
Schmidt, Διευθύνων Σύμβουλος εκείνη την εποχή,

194
00:09:32,180 --> 00:09:36,380
και είχε προσβληθεί με μια ερώτηση
σαν ερευνούμε σήμερα.

195
00:09:36,380 --> 00:09:38,468
Ας ρίξουμε μια ματιά.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEO PLAYBACK]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, Είστε εδώ
στο Google, και μου αρέσει

198
00:09:48,560 --> 00:09:53,382
να σκεφτούμε την προεδρία
ως μια συνέντευξη για δουλειά.

199
00:09:53,382 --> 00:09:56,434
Τώρα, είναι δύσκολο να πάρει
μια δουλειά ως πρόεδρος,

200
00:09:56,434 --> 00:09:58,100
και θα πάμε μέσα από τις ακαμψίες τώρα.

201
00:09:58,100 --> 00:10:01,860
Είναι επίσης δύσκολο να βρουν μια θέση εργασίας στην Google.

202
00:10:01,860 --> 00:10:05,490
Έχουμε ερωτήματα, και εμείς
ζητήσει από τους υποψήφιους ερωτήσεις μας,

203
00:10:05,490 --> 00:10:09,770
και αυτό είναι ένα από Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
Τι-- εσείς ότι είμαι
αστειεύεστε, είναι ακριβώς εδώ.

205
00:10:14,760 --> 00:10:17,930
Ποια είναι η πιο αποτελεσματικός τρόπος για να
ταξινομήσετε ένα εκατομμύριο ακεραίων 32-bit;

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -Συγγνώμη, Maybe--

209
00:10:25,200 --> 00:10:27,400
>> Όχι, όχι, όχι.

210
00:10:27,400 --> 00:10:30,700
Νομίζω ότι το είδος φούσκα
θα ήταν ο λάθος τρόπος να πάει.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> Έλα, που τον είπε αυτό;

213
00:10:38,180 --> 00:10:40,590
Δεν είδα τον υπολογιστή
επιστήμης στο παρασκήνιο σας.

214
00:10:40,590 --> 00:10:42,130
>> -We've Πήρε κατασκόπους μας εκεί.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -εντάξει, Ας ζητήσει μια διαφορετική
Συνέντευξη ερώτημα.

217
00:10:48,444 --> 00:10:49,300
>> [ΤΕΛΟΣ VIDEO PLAYBACK]

218
00:10:49,300 --> 00:10:52,290
>> ΟΜΙΛΗΤΗΣ: Οπότε μιλάμε για
συγκεκριμένους αριθμούς όμως,

219
00:10:52,290 --> 00:10:53,890
δεν πρόκειται να είναι όλα αυτά χρήσιμα.

220
00:10:53,890 --> 00:10:56,810
Δεν είναι ένα μάθημα ζωής που φούσκα
ταξινόμησης, δίνεται ένα εκατομμύριο εισόδους,

221
00:10:56,810 --> 00:10:58,590
μπορεί να πάρει όσο 500 δισεκατομμύρια βήματα.

222
00:10:58,590 --> 00:11:01,120
Δεν μπορεί πραγματικά να γενικεύσουμε
πολύ αποτελεσματικά από ότι

223
00:11:01,120 --> 00:11:03,560
και να κάνει καλές αποφάσεις σχεδιασμού
κατά τη σύνταξη των προγραμμάτων.

224
00:11:03,560 --> 00:11:07,070
Ας επικεντρωθούμε όμως στο πώς
θα μπορούσε να απλοποιήσει αυτό το αποτέλεσμα.

225
00:11:07,070 --> 00:11:11,780
>> Έτσι έχω επισημαίνονται με κίτρινο χρώμα εδώ
το αποτέλεσμα του n τετράγωνο διαιρείται με 2,

226
00:11:11,780 --> 00:11:14,330
έτσι, ένα εκατομμύριο τετράγωνο
διαιρείται με 2, και έπειτα

227
00:11:14,330 --> 00:11:16,710
Έχω υπογράμμισε τι
η τελική απάντηση ήταν

228
00:11:16,710 --> 00:11:20,180
τη στιγμή που θα αφαιρεθεί από n διαιρείται δια 2.

229
00:11:20,180 --> 00:11:24,850
Και ο ισχυρισμός Πάω να κάνει τώρα είναι,
ποιος στο διάολο νοιάζεται αν αφαιρούμε

230
00:11:24,850 --> 00:11:30,060
λίγο παλιό n πάνω από 2, όταν η πρώτη
μέρος αυτού του τύπου είναι πολύ μεγαλύτερο;

231
00:11:30,060 --> 00:11:33,910
Δεσπόζει το άλλο
διάρκειας, n τετράγωνο χωρίζεται από 2

232
00:11:33,910 --> 00:11:37,510
είναι πολύ μεγαλύτερο, με σαφήνεια, όπως
n παίρνει μεγάλες σαν ένα εκατομμύριο,

233
00:11:37,510 --> 00:11:41,450
ότι είναι πραγματικά υπάρχει μια μεγάλη διαφορά στο
το τέλος της ημέρας μεταξύ 500 δισεκατομμύρια

234
00:11:41,450 --> 00:11:45,730
και 499 999 500 000;

235
00:11:45,730 --> 00:11:46,349
Όχι πραγματικά.

236
00:11:46,349 --> 00:11:48,640
Και έτσι αυτό που πρόκειται να
κάνουμε ως επιστήμονες υπολογιστών είναι

237
00:11:48,640 --> 00:11:53,270
αγνοεί τις χαμηλότερες όρους τάξης και
να λάβει κάτι τέτοιο και πραγματικά

238
00:11:53,270 --> 00:11:56,050
απλά για να απλουστευθεί η
όρος που πρόκειται να έχει σημασία.

239
00:11:56,050 --> 00:12:00,315
Τα μεγαλύτερα σύνολα δεδομένων μας πάρει, το μεγαλύτερο
βάσεις δεδομένων μας πάρει, οι περισσότερες ιστοσελίδες

240
00:12:00,315 --> 00:12:02,690
πρέπει να ψάξουμε, το πιο
φίλους έχεις στο Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Καθώς το n μεγαλώνει, είμαστε πραγματικά
πρόκειται να νοιάζονται για το μεγαλύτερο

242
00:12:07,340 --> 00:12:11,560
όρος σε κάθε τέτοια ανάλυση
απόδοση των αλγορίθμων μας.

243
00:12:11,560 --> 00:12:16,230
Και Πάω να πω, ξέρετε τι,
φούσκα είδος είναι της τάξεως των μεγάλων O,

244
00:12:16,230 --> 00:12:18,060
της τάξεως των Ν τετράγωνο.

245
00:12:18,060 --> 00:12:20,090
Δεν είναι ακριβώς n
τετράγωνο, όπως έχουμε δει,

246
00:12:20,090 --> 00:12:22,060
αλλά ποιος νοιάζεται πραγματικά
για τα μικρότερα αυτά όρων,

247
00:12:22,060 --> 00:12:24,390
και ειλικρινά, που πραγματικά
νοιάζεται αν διαιρέσουμε με 2;

248
00:12:24,390 --> 00:12:25,870
Αυτό είναι απλά ένα σταθερό παράγοντα.

249
00:12:25,870 --> 00:12:29,480
Και είναι 500 δισεκατομμύρια, έναντι 250
δισεκατομμύρια πραγματικά ότι οι μεγάλες από μια συμφωνία;

250
00:12:29,480 --> 00:12:32,190
Θα μπορούσα απλά περιμένετε από ένα χρόνο,
αφήστε το laptop μου κυριολεκτικά

251
00:12:32,190 --> 00:12:34,810
πάρει δύο φορές πιο γρήγορα σε hardware,
και αυτό το είδος της διαφοράς

252
00:12:34,810 --> 00:12:36,650
Απλά πηγαίνει μακριά φυσικά την πάροδο του χρόνου.

253
00:12:36,650 --> 00:12:39,300
>> Αυτό που μας νοιάζει είναι
η έκφραση, το τμήμα

254
00:12:39,300 --> 00:12:42,489
της έκφρασης, που πρόκειται να ποικίλουν
ως συμβολή μας γίνεται όλο και μεγαλύτερο.

255
00:12:42,489 --> 00:12:45,280
Και πράγματι, στον πραγματικό κόσμο,
αυτό είναι που συμβαίνει όλο και περισσότερο

256
00:12:45,280 --> 00:12:48,330
είναι οι είσοδοι για τα προβλήματά μας και
αλγόριθμοι παίρνουν μεγαλύτερα.

257
00:12:48,330 --> 00:12:53,470
Τόσο μεγάλη O πρόκειται να είναι ο συμβολισμός,
το ασυμπτωτικό συμβολισμό, ότι εμείς απλά

258
00:12:53,470 --> 00:12:57,160
χρησιμοποιήσετε ως επιστήμονες ηλεκτρονικών υπολογιστών για να περιγράψει
η απόδοση, ή ο χρόνος τρέχει,

259
00:12:57,160 --> 00:12:58,130
ενός αλγορίθμου.

260
00:12:58,130 --> 00:13:00,800
Έτσι ώστε να μπορούμε να συγκρίνουμε αλγορίθμους
σε διαφορετικούς υπολογιστές γραπτή

261
00:13:00,800 --> 00:13:04,170
από διαφορετικούς ανθρώπους, με τη χρήση
μερικά βασικά παρόμοια μετρικό

262
00:13:04,170 --> 00:13:07,557
όπως τον αριθμό των συγκρίσεων είστε
αποφάσεων, ή ίσως και τον αριθμό των swaps

263
00:13:07,557 --> 00:13:08,140
έχετε κάνει.

264
00:13:08,140 --> 00:13:11,910
>> Αυτό που δεν πρόκειται να
καταμέτρηση είναι η ποσότητα του χρόνου

265
00:13:11,910 --> 00:13:13,981
που περνά στο ρολόι
στον τοίχο τυπικά.

266
00:13:13,981 --> 00:13:16,230
Αυτό που δεν πρόκειται να ανησυχείτε
περίπου είναι πόση μνήμη

267
00:13:16,230 --> 00:13:17,820
που χρησιμοποιείτε σήμερα σε
τουλάχιστον, αν αυτό είναι

268
00:13:17,820 --> 00:13:19,370
άλλος πόρος που μπορεί να μετρηθεί.

269
00:13:19,370 --> 00:13:23,610
Εμείς πάμε για να προσπαθήσουμε να βασίζουν τις αναλύσεις μας
σε μόνο τις βασικές λειτουργίες, εκείνοι,

270
00:13:23,610 --> 00:13:25,930
ειλικρινά, που μπορείτε να δείτε πιο οπτικά.

271
00:13:25,930 --> 00:13:30,700
Έτσι, με κάτι σαν μεγάλη O από n
τετράγωνο, εγώ ισχυρίζομαι ότι από O n τετράγωνο

272
00:13:30,700 --> 00:13:35,820
είναι ένα άνω όριο για τη λεγόμενη
χρόνο της bubble sort τρέξιμο.

273
00:13:35,820 --> 00:13:38,820
Με άλλα λόγια, αν
ήθελε να ισχυρίζονται ότι δεν υπάρχει

274
00:13:38,820 --> 00:13:41,370
αυτό το ανώτατο όριο για το πόσες
στάδια ένας αλγόριθμος θα μπορούσε να λάβει,

275
00:13:41,370 --> 00:13:46,240
πρόκειται να είναι το μεγάλο O των n
τετράγωνο σε αυτή την περίπτωση, ένα άνω όριο.

276
00:13:46,240 --> 00:13:49,710
>> Τι θα συμβεί αν, αντί να αλλάξει η
η ιστορία να μην είναι για το bubble sort,

277
00:13:49,710 --> 00:13:50,910
αλλά για αυτό το άνω φράγμα.

278
00:13:50,910 --> 00:13:54,030
Μπορείτε να σκεφτείτε έναν αλγόριθμο
ότι έχουμε εξετάσει ήδη

279
00:13:54,030 --> 00:13:59,530
των οποίων άνω όριο, κατ 'ανώτατο όριο
μέτρηση του χρόνου ή επιχειρήσεις,

280
00:13:59,530 --> 00:14:04,300
θα είπε να οριοθετείται
από n, μια γραμμική συνάρτηση,

281
00:14:04,300 --> 00:14:07,260
δεν είναι μια τετραγωνική ένα καμπύλο;

282
00:14:07,260 --> 00:14:10,780
Τι είναι ένας αλγόριθμος που
παίρνει πάντα περισσότερο

283
00:14:10,780 --> 00:14:12,860
από ό, τι σαν βήματα n, ή
2n βήματα ή τα βήματα 3η;

284
00:14:12,860 --> 00:14:13,360
Ναι;

285
00:14:13,360 --> 00:14:15,030
>> ΚΟΙΝΟ: Η εξεύρεση της
μεγαλύτερο αριθμό σε μια λίστα;

286
00:14:15,030 --> 00:14:16,930
>> ΟΜΙΛΗΤΗΣ: Perfect, βρίσκοντας
ο μεγαλύτερος αριθμός σε έναν κατάλογο.

287
00:14:16,930 --> 00:14:18,940
Αν είμαι δοθεί μια λίστα
άνθρωποι, για παράδειγμα,

288
00:14:18,940 --> 00:14:21,440
καθένα από τα οποία κρατάει έναν αριθμό,
τι είναι ο μέγιστος αριθμός

289
00:14:21,440 --> 00:14:23,770
των βημάτων που πρέπει να με πάρει,
ένα αρκετά έξυπνο άτομο,

290
00:14:23,770 --> 00:14:27,530
για να βρείτε το μεγαλύτερο πρόσωπο στον εν λόγω κατάλογο;

291
00:14:27,530 --> 00:14:28,100
n, σωστά;

292
00:14:28,100 --> 00:14:31,320
Επειδή στη χειρότερη περίπτωση, όπου
ίσως η μεγαλύτερη αξία είναι;

293
00:14:31,320 --> 00:14:32,700
Δεξιά, όλος ο τρόπος στο τέλος.

294
00:14:32,700 --> 00:14:34,575
Έτσι, στη χειρότερη περίπτωση
άνω όριο, θα μπορούσα

295
00:14:34,575 --> 00:14:36,450
πρέπει να πάει όλος ο τρόπος
εδώ και να είναι όπως,

296
00:14:36,450 --> 00:14:39,170
Ω, εδώ είναι ο αριθμός οκτώ,
ή ό, τι η τιμή είναι.

297
00:14:39,170 --> 00:14:41,330
Τώρα αυτό θα ήταν απλά ανόητο
αν συνεχίζαμε, σωστά;

298
00:14:41,330 --> 00:14:43,840
Ψάχνετε για όλο και περισσότερα στοιχεία
εάν η τελευταία από αυτές είναι πάνω εκεί;

299
00:14:43,840 --> 00:14:45,340
Έτσι, σίγουρα, n είναι ένα άνω όριο.

300
00:14:45,340 --> 00:14:47,420
Δεν πρέπει να πάρετε
περισσότερα βήματα από αυτό.

301
00:14:47,420 --> 00:14:51,580
>> Έτσι, ό, τι και αν αντ 'αυτού πρότεινε ότι
υπάρχουν αλγόριθμοι σε αυτόν τον κόσμο ότι

302
00:14:51,580 --> 00:14:57,750
έχουν ένα χρόνο λειτουργίας που είναι
οριοθετείται από μεγάλη O του log n, log n;

303
00:14:57,750 --> 00:15:00,390
Πού έχουμε ξαναδεί κάτι τέτοιο;

304
00:15:00,390 --> 00:15:00,890
Ναι;

305
00:15:00,890 --> 00:15:03,309
>> ΚΟΙΝΟ: Στο πρόβλημα τηλεφωνικό κατάλογο;

306
00:15:03,309 --> 00:15:04,850
ΟΜΙΛΗΤΗΣ: Όπως και το πρόβλημα του τηλεφωνικού καταλόγου.

307
00:15:04,850 --> 00:15:07,754
Ποιο ήταν το μέτρο του πόσο
πολύ χρόνο ή πόσα δάκρυα είναι

308
00:15:07,754 --> 00:15:10,170
πήρε να βρω κάποιον σαν
Mike Smith στον τηλεφωνικό κατάλογο;

309
00:15:10,170 --> 00:15:13,212
Εμείς ισχυρίστηκε ότι ήταν log n, και
ακόμα και αν δεν είναι εξοικειωμένοι ή είναι

310
00:15:13,212 --> 00:15:15,170
λίγο θολό, τι ένα
λογάριθμος ή εκφραστής ήταν,

311
00:15:15,170 --> 00:15:17,650
απλά να θυμάστε ότι log n
αναφέρεται γενικά στην διαδικασία,

312
00:15:17,650 --> 00:15:20,790
στην περίπτωση αυτή, από τη διαίρεση
κάτι το ήμισυ και πάλι, και πάλι,

313
00:15:20,790 --> 00:15:25,790
και ξανά, και ξανά, έτσι ώστε να
γίνεται όλο και πιο μικρά, όπως το κάνετε αυτό.

314
00:15:25,790 --> 00:15:28,470
>> Έτσι log ν αναφέρεται, βέβαια,
για παράδειγμα τηλεφωνικό κατάλογο,

315
00:15:28,470 --> 00:15:32,662
σε δυαδική αναζήτηση στη θεωρία, όταν εμείς
είχε τις εικονικές πόρτες της στο διοικητικό συμβούλιο,

316
00:15:32,662 --> 00:15:34,370
ή όταν ο Sean ήταν
ψάχνουν για κάτι.

317
00:15:34,370 --> 00:15:37,374
Αν είχε χρησιμοποιηθεί δυαδική αναζήτηση, log n
θα είναι το ανώτατο όριο για το πόσο

318
00:15:37,374 --> 00:15:38,040
χρόνο που χρειάζεται.

319
00:15:38,040 --> 00:15:44,027
Αλλά αυτοί οι αλγόριθμοι που έτρεξε σε
log n υποτίθεται τι κλειδί λεπτομέρεια;

320
00:15:44,027 --> 00:15:45,360
Αυτός ο κατάλογος ήταν ταξινομημένο, σωστά;

321
00:15:45,360 --> 00:15:47,789
Αλγόριθμο σας είναι λάθος, αν
εισόδου σας δεν είναι ταξινομημένο,

322
00:15:47,789 --> 00:15:49,830
και όμως είστε με τη χρήση
κάτι σαν δυαδική αναζήτηση

323
00:15:49,830 --> 00:15:51,704
επειδή μπορεί να πηδήσει
ακριβώς πάνω από το στοιχείο

324
00:15:51,704 --> 00:15:53,600
χωρίς να συνειδητοποιούν ότι είναι πράγματι εκεί.

325
00:15:53,600 --> 00:15:55,600
>> Τώρα τι μπορεί να σημαίνει αυτό, μεγάλη O ενός;

326
00:15:55,600 --> 00:15:59,117
Αυτό δεν σημαίνει ότι ο αλγόριθμος σας
διαρκεί ένα και μόνο ένα βήμα,

327
00:15:59,117 --> 00:16:01,200
αυτό σημαίνει απλώς παίρνει μια
σταθερό αριθμό βημάτων.

328
00:16:01,200 --> 00:16:04,060
Ίσως είναι 1, ίσως είναι
10, ίσως είναι 1.000,

329
00:16:04,060 --> 00:16:07,750
αλλά είναι ανεξάρτητο από
το μέγεθος του προβλήματος.

330
00:16:07,750 --> 00:16:10,850
Δεν έχει σημασία πόσο μεγάλο είναι n,
ένα σταθερό αλγόριθμο

331
00:16:10,850 --> 00:16:12,747
λαμβάνει πάντοτε τον ίδιο αριθμό βημάτων.

332
00:16:12,747 --> 00:16:15,080
Λοιπόν, τι θα μπορούσε να είναι ένας αλγόριθμος
έχουμε μιλήσει ή απλά

333
00:16:15,080 --> 00:16:20,418
διαισθητικά ότι έρχεται σε σας ότι
τρέχει πάντα στο λεγόμενο σταθερό χρόνο;

334
00:16:20,418 --> 00:16:20,918
Ναι;

335
00:16:20,918 --> 00:16:22,001
>> ΚΟΙΝΟ: Προσθέστε δύο αριθμούς.

336
00:16:22,001 --> 00:16:25,320
ΟΜΙΛΗΤΗΣ: Προσθέστε δύο αριθμούς,
2 συν 2 ισούται με 4, γίνεται.

337
00:16:25,320 --> 00:16:27,227
Έτσι, ότι θα μπορούσε να λειτουργήσει, τι άλλο;

338
00:16:27,227 --> 00:16:28,560
Τι θα λέγατε για πιο πραγματικό κόσμο, ναι;

339
00:16:28,560 --> 00:16:30,686
>> ΚΟΙΝΟ: Η εξεύρεση της
το πρώτο πράγμα που σε μια λίστα.

340
00:16:30,686 --> 00:16:32,810
ΟΜΙΛΗΤΗΣ: Ψάχνοντας το πρώτο
στοιχείο σε μια λίστα, σίγουρα.

341
00:16:32,810 --> 00:16:34,540
Έχουμε πράγματι να μιλάμε
σχετικά με συστοιχίες ήδη,

342
00:16:34,540 --> 00:16:36,540
πώς μπορείτε να πάρετε κατά τη
πρώτο στοιχείο σε μία συστοιχία,

343
00:16:36,540 --> 00:16:40,465
Δεν έχει σημασία πόσο καιρό η
πίνακας είναι σε κώδικα C;

344
00:16:40,465 --> 00:16:43,090
Μπορείτε απλά να χρησιμοποιήσετε σαν τον βραχίονα
μηδέν σημειογραφία, μπαμ, είστε εκεί.

345
00:16:43,090 --> 00:16:46,120
Και πράγματι συστοιχίες, όπως ένα μέρος,
κάτι υποστήριξης γενικά γνωστό

346
00:16:46,120 --> 00:16:49,240
ως τυχαίας προσπέλασης, τυχαίας προσπέλασης
μνήμη, επειδή μπορείτε κυριολεκτικά

347
00:16:49,240 --> 00:16:50,284
μεταβείτε σε οποιαδήποτε θέση.

348
00:16:50,284 --> 00:16:52,700
Μπορούμε να το κάνουμε αυτό ακόμα πιο απλά
μπορούμε να rewind στην εβδομάδα μηδέν

349
00:16:52,700 --> 00:16:53,900
όταν κάναμε Scratch.

350
00:16:53,900 --> 00:16:59,707
Πόσο χρόνο θα πάρει για την
λένε μπλοκ σε Scratch να εκτελέσει;

351
00:16:59,707 --> 00:17:00,790
Απλά συνεχή φορά, σωστά;

352
00:17:00,790 --> 00:17:03,960
Πες κάτι, πες
κάτι, δεν έχει σημασία

353
00:17:03,960 --> 00:17:07,359
πόσο μεγάλο γρατσουνιές κόσμο είναι, είναι πάντα
πρόκειται να λάβει το ίδιο χρονικό διάστημα

354
00:17:07,359 --> 00:17:08,490
απλά να πω κάτι.

355
00:17:08,490 --> 00:17:11,089
>> Έτσι, αυτό είναι το σταθερό χρόνο,
αλλά ποια είναι η άλλη πλευρά;

356
00:17:11,089 --> 00:17:13,030
Αν αυτό ήταν ανώτερο
φράγματα, τι αν θέλουμε

357
00:17:13,030 --> 00:17:17,089
για να περιγράψει τα χαμηλότερα όρια
των αλγορίθμων μας τρέχει χρόνο;

358
00:17:17,089 --> 00:17:19,852
Σχεδόν μια καλύτερη περίπτωση
ενδεχομένως, αν θέλετε,

359
00:17:19,852 --> 00:17:23,060
αν οι όροι αυτοί θα μπορούσαν να εφαρμοστούν με τον καλύτερο
περιπτώσεις, χειρότερες περιπτώσεις, κατά μέσο όρο περισσότερες περιπτώσεις

360
00:17:23,060 --> 00:17:26,359
γενικά, αλλά ας επικεντρωθούμε
σε χαμηλότερα όρια γενικότερα.

361
00:17:26,359 --> 00:17:31,920
Τι είναι ένας αλγόριθμος που έχει
ένα κατώτερο όριο των βημάτων n,

362
00:17:31,920 --> 00:17:33,350
ή 2n βήματα ή τα βήματα 3η;

363
00:17:33,350 --> 00:17:36,241
Μερικά παράγοντας των βημάτων n,
αυτό είναι χαμηλότερο όριό του.

364
00:17:36,241 --> 00:17:36,740
Ναι;

365
00:17:36,740 --> 00:17:37,910
>> ΚΟΙΝΟ: Bubble sort;

366
00:17:37,910 --> 00:17:41,610
>> ΟΜΙΛΗΤΗΣ: Bubble sort χρειάζεται
σας βήματα ελάχιστα n, γιατί;

367
00:17:41,610 --> 00:17:42,279
Γιατί συμβαίνει αυτό;

368
00:17:42,279 --> 00:17:45,320
Γιατί θα πρέπει η αρχή να έρθει σε σας
διαισθητικά, ακόμη και αν δεν το κάνει μόνο

369
00:17:45,320 --> 00:17:46,530
ακόμα;

370
00:17:46,530 --> 00:17:47,030
Ναι;

371
00:17:47,030 --> 00:17:47,990
>> ΚΟΙΝΟ: [δεν ακούγεται].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
ΟΜΙΛΗΤΗΣ: Ακριβώς.

374
00:17:52,360 --> 00:17:55,810
Με τον καλύτερο δυνατό σενάριο
bubble sort, και πολλοί αλγόριθμοι,

375
00:17:55,810 --> 00:17:58,769
αν έχετε παραδώσει οκτώ άτομα
που έχουν ήδη ταξινομηθεί,

376
00:17:58,769 --> 00:18:00,560
θα ήταν ανόητο
για σας, ο αλγόριθμος,

377
00:18:00,560 --> 00:18:02,202
για να πάει μπροστά και πίσω
περισσότερο από μία φορά, σωστά;

378
00:18:02,202 --> 00:18:04,285
Επειδή το συντομότερο
με τα πόδια μέσα από τη λίστα μια φορά,

379
00:18:04,285 --> 00:18:08,090
θα πρέπει να συνειδητοποιήσουν, oh, έκανα κανένα
swaps, αυτή η λίστα είναι ταξινομημένη, την έξοδο.

380
00:18:08,090 --> 00:18:09,700
Αλλά αυτό δεν πρόκειται να σας πάρει n βήματα.

381
00:18:09,700 --> 00:18:12,033
>> Και αντιστρόφως, τι άλλο
τρόπος σκέψης σχετικά με αυτό;

382
00:18:12,033 --> 00:18:15,240
Bubble sort είναι ένα ωμέγα,
να το πω έτσι, του n,

383
00:18:15,240 --> 00:18:19,050
γιατί αν κοιτάξετε
λιγότερα από n στοιχεία, τι

384
00:18:19,050 --> 00:18:23,009
είναι το βασικό θέμα εκεί;

385
00:18:23,009 --> 00:18:24,550
Δεν ξέρω αν αυτό είναι ταξινομημένα, σωστά.

386
00:18:24,550 --> 00:18:26,800
Εμείς οι άνθρωποι θα μπορούσε ματιά σε οκτώ
ανθρώπους και να είναι όπως, OH, αυτό είναι ταξινομημένα,

387
00:18:26,800 --> 00:18:28,430
ότι δεν με n βήματα πάρει, αλλά το έκανε.

388
00:18:28,430 --> 00:18:30,810
Τα μάτια σας, ακόμα κι αν το είδος
της έχει ένα μεγάλο οπτικό πεδίο,

389
00:18:30,810 --> 00:18:33,184
Σας κοίταξε οκτώ στοιχεία,
κοίταξε σε οκτώ ανθρώπους,

390
00:18:33,184 --> 00:18:34,610
ότι είναι οκτώ βήματα αποτελεσματικά.

391
00:18:34,610 --> 00:18:38,612
Και μόνο αν πάω με τα πόδια μέσα από το σύνολο του
να κάνουμε λίστα Αντιλαμβάνομαι, ναι, ταξινομούνται.

392
00:18:38,612 --> 00:18:41,320
Αν μπορώ να σταματήσω στα μισά του δρόμου σκέψης, όλα
Εντάξει, αυτό είναι αρκετά ταξινομηθεί μέχρι στιγμής,

393
00:18:41,320 --> 00:18:42,520
ποιες είναι οι πιθανότητες δεν είναι ταξινομημένα;

394
00:18:42,520 --> 00:18:44,186
Αυτό δεν αλγόριθμοι πρόκειται να είναι σωστό.

395
00:18:44,186 --> 00:18:46,250
Θα μπορούσε να είναι πιο γρήγορα, αλλά λανθασμένη.

396
00:18:46,250 --> 00:18:48,500
>> Μέχρι τώρα έχουμε έναν τρόπο
περιγράφει ένα κατώτερα όρια,

397
00:18:48,500 --> 00:18:49,710
και τι γίνεται με σταθερό χρόνο;

398
00:18:49,710 --> 00:18:54,565
Τι είναι ένας αλγόριθμος που έχει ένα χαμηλότερο
δεσμεύεται για το χρόνο λειτουργίας του ενός;

399
00:18:54,565 --> 00:18:58,350
1 βήμα, 2 στάδια, 10 βήματα, αλλά
σταθερή, ανεξάρτητα από Ν,

400
00:18:58,350 --> 00:18:59,310
το μέγεθος της εισόδου;

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Ναι, στο πίσω μέρος.

403
00:19:04,600 --> 00:19:05,309
>> ΚΟΙΝΟ: printf;

404
00:19:05,309 --> 00:19:06,183
ΟΜΙΛΗΤΗΣ: Τι είναι αυτό;

405
00:19:06,183 --> 00:19:07,184
ΚΟΙΝΟ: printf;

406
00:19:07,184 --> 00:19:07,850
ΟΜΙΛΗΤΗΣ: printf.

407
00:19:07,850 --> 00:19:08,400
Εντάξει, σίγουρα.

408
00:19:08,400 --> 00:19:10,720
Γι 'αυτό χρειάζεται ένα σταθερό αριθμό βημάτων.

409
00:19:10,720 --> 00:19:13,170
Και εγώ πρέπει να now-- τώρα ότι
μιλάμε για κώδικα C

410
00:19:13,170 --> 00:19:16,040
και δεν Scratch, κάτι
όπως για παράδειγμα, με την printf,

411
00:19:16,040 --> 00:19:17,710
θα πρέπει να αρχίσουμε να πάρει προσεκτικοί.

412
00:19:17,710 --> 00:19:21,090
Επειδή printf δεν λαμβάνει
εισόδου, είναι ένα string,

413
00:19:21,090 --> 00:19:23,220
και έγχορδα δεν είναι τεχνικώς έχουν μήκος.

414
00:19:23,220 --> 00:19:25,530
Έτσι, αν θέλουμε τώρα να πάρει
σε σας, αν δεν σας πειράζει,

415
00:19:25,530 --> 00:19:29,430
τεχνικά θα μπορούσε να ισχυριστεί ότι η printf
έχει λάβει μια μεταβλητή εισόδου μήκους,

416
00:19:29,430 --> 00:19:32,270
και σίγουρα θα μπορούσε να διαρκέσει περισσότερο
χρόνο για να τυπώσει μια συμβολοσειρά αυτό το διάστημα,

417
00:19:32,270 --> 00:19:33,560
από αυτή τη μακρά.

418
00:19:33,560 --> 00:19:36,570
>> Έτσι, ό, τι και αν λάβουμε υπόψη μόνο η
διαλογή και ψάχνουν παραδείγματα;

419
00:19:36,570 --> 00:19:40,450
Τι γίνεται με τον Mike Smith στο τηλέφωνο
βιβλίο, ή δυαδική αναζήτηση γενικότερα;

420
00:19:40,450 --> 00:19:42,220
Στην καλύτερη περίπτωση, τι θα μπορούσε να συμβεί;

421
00:19:42,220 --> 00:19:45,577
Ανοίγω το βιβλίο του τηλεφώνου και, μπαμ,
υπάρχει αριθμός Mike Smith.

422
00:19:45,577 --> 00:19:46,660
Μπορώ να τον καλέσετε αμέσως.

423
00:19:46,660 --> 00:19:49,390
>> Πήρε ένα βήμα, ίσως και δύο βήματα,
αλλά ένα σταθερό αριθμό βημάτων

424
00:19:49,390 --> 00:19:50,230
αν ήμουν τυχερός.

425
00:19:50,230 --> 00:19:52,570
Και ειλικρινά, είδαμε την
Δευτέρα συμμαθητή σας

426
00:19:52,570 --> 00:19:54,710
πάρετε αρκετά τυχεροί δύο φορές στη σειρά.

427
00:19:54,710 --> 00:19:57,050
Και αυτό ήταν πράγματι σταθερές
φορά σε χαμηλότερα όρια

428
00:19:57,050 --> 00:20:01,280
σχετικά με την εν λόγω αλγόριθμος για την εύρεση
ο αριθμός 50 πίσω από αυτά τα κλειστά

429
00:20:01,280 --> 00:20:01,830
πόρτες.

430
00:20:01,830 --> 00:20:06,400
>> Τώρα, ως ένα μέρος, αν ανακαλύψετε
ότι τόσο μεγάλη O, το άνω όριο,

431
00:20:06,400 --> 00:20:09,310
και το ωμέγα, το κατώτερο όριο,
είναι ένα με τον ίδιο, ότι

432
00:20:09,310 --> 00:20:11,830
είναι η ίδια φόρμουλα σε
παρενθέσεις, μπορείτε επίσης να

433
00:20:11,830 --> 00:20:15,170
λένε, απλά να είναι φανταχτερό,
ότι κάτι είναι σε θήτα

434
00:20:15,170 --> 00:20:18,270
από Ν ή θήτα από κάποια άλλη τιμή.

435
00:20:18,270 --> 00:20:20,661
Αυτό απλά σημαίνει ότι όταν μεγάλη
O και ωμέγα είναι τα ίδια.

436
00:20:20,661 --> 00:20:21,910
Τώρα τι γίνεται με το είδος επιλογής;

437
00:20:21,910 --> 00:20:23,400
Ας χρησιμοποιήσουμε αυτό το νέο λεξιλόγιο.

438
00:20:23,400 --> 00:20:27,407
Σε τέτοια επιλογή, ό, τι ήμασταν
κάνει ξανά, και ξανά, και ξανά;

439
00:20:27,407 --> 00:20:29,990
Ήμουν πηγαινοέρχονται μέσα
η λίστα, ψάχνει για ποιον;

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
Ο μικρότερος αριθμός.

442
00:20:34,730 --> 00:20:37,560
>> Έτσι, πόσα βήματα, πώς
πολλές συγκρίσεις έκανα

443
00:20:37,560 --> 00:20:43,250
πρέπει να κάνουν ώστε να καταλάβω ποιος
το μικρότερο στοιχείο στη λίστα ήταν;

444
00:20:43,250 --> 00:20:44,437
n μείον 1, σωστά;

445
00:20:44,437 --> 00:20:47,770
Διότι αν εγώ μόλις ξεκινήσει με τη μία είμαι
δίνεται και αρχίζω να τον ή την σύγκριση,

446
00:20:47,770 --> 00:20:49,519
Στη συνέχεια το άτομό του, τον
ή της, αυτόν ή αυτήν, I

447
00:20:49,519 --> 00:20:52,010
μπορεί να αντιστοιχιστεί μόνο στοιχεία
μαζί n μείον 1 φορές.

448
00:20:52,010 --> 00:20:55,630
Έτσι, η επιλογή γίνεται είδος ομοίως
n μείον 1 βήματα την πρώτη φορά.

449
00:20:55,630 --> 00:20:59,540
>> Πόσα βήματα μου πάρει να
βρείτε το δεύτερο μικρότερο στοιχείο;

450
00:20:59,540 --> 00:21:02,920
n μείον 2, επειδή είμαι είσαι άλαλος
αν συνεχίσετε να ψάχνετε στα ίδια άτομα

451
00:21:02,920 --> 00:21:06,280
και πάλι, αν έχω ήδη τον επιλεγμένο
ή της και να τους βάλει στη θέση τους.

452
00:21:06,280 --> 00:21:09,270
Και το τρίτο βήμα, n
μείον 3, τότε το η μείον 4.

453
00:21:09,270 --> 00:21:11,020
Έχουμε δει αυτό το μοτίβο
πριν, και μάλιστα

454
00:21:11,020 --> 00:21:13,460
Η επιλογή του είδους ομοίως
έχει ένα άνω φράγμα

455
00:21:13,460 --> 00:21:16,210
από n τετράγωνο αν κάνουμε μέχρι αυτό το άθροισμα.

456
00:21:16,210 --> 00:21:19,790
Τι είναι το κάτω όριο, το είδος της επιλογής;

457
00:21:19,790 --> 00:21:25,350
Ελάχιστα, πόσο επιλογής must χρόνο
ταξινόμησης λάβει, όπως την ορίσαμε τη Δευτέρα;

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Προτείνει δύο επιλογές.

460
00:21:30,490 --> 00:21:32,360
Ίσως είναι n, όπως και πριν.

461
00:21:32,360 --> 00:21:35,040
Ίσως αυτό είναι n τετράγωνο, όπως
είναι τώρα ως το ανώτερο όριο.

462
00:21:35,040 --> 00:21:35,874
>> ΚΟΙΝΟ: n τετράγωνο.

463
00:21:35,874 --> 00:21:36,664
ΟΜΙΛΗΤΗΣ: n τετράγωνο.

464
00:21:36,664 --> 00:21:37,368
Γιατί;

465
00:21:37,368 --> 00:21:40,060
>> ΚΟΙΝΟ: Επειδή έχετε
να καθορίσει [δεν ακούγεται].

466
00:21:40,060 --> 00:21:41,510
>> ΟΜΙΛΗΤΗΣ: Ακριβώς.

467
00:21:41,510 --> 00:21:45,077
Τουλάχιστον όπως ορίζεται είδος επιλογής
ήταν αρκετά αφελής, συνεχίζω,

468
00:21:45,077 --> 00:21:46,160
βρείτε το μικρότερο στοιχείο.

469
00:21:46,160 --> 00:21:47,770
Πήγαινε πάλι, βρείτε το μικρότερο στοιχείο.

470
00:21:47,770 --> 00:21:49,490
Πήγαινε πάλι, βρείτε το μικρότερο στοιχείο.

471
00:21:49,490 --> 00:21:51,700
Δεν υπάρχει κανένα είδος
βελτιστοποίηση εκεί που

472
00:21:51,700 --> 00:21:54,350
θα μπορούσε να επιτρέψτε μου να εγκαταλείψετε μετά
ακριβώς n ή έτσι τα βήματα.

473
00:21:54,350 --> 00:21:57,080
Έτσι, πράγματι, η επιλογή
είδος, το ωμέγα n τετράγωνο.

474
00:21:57,080 --> 00:22:00,667
>> Τι γίνεται με το είδος εισαγωγής, όπου πήρα
που μου δόθηκε, και στη συνέχεια θα τον plopped

475
00:22:00,667 --> 00:22:01,750
ή της στο σωστό μέρος;

476
00:22:01,750 --> 00:22:04,958
Στη συνέχεια, θα προχωρήσει στο δεύτερο πρόσωπο,
αυτόν ή αυτήν plopped στο σωστό μέρος.

477
00:22:04,958 --> 00:22:07,910
Στη συνέχεια, το επόμενο πρόσωπο, plopped
αυτόν ή αυτήν στο σωστό μέρος.

478
00:22:07,910 --> 00:22:10,537
Σημειώστε ότι αυτό είναι πολύ
γραμμική, να το πω έτσι.

479
00:22:10,537 --> 00:22:12,620
Είμαι μια ευθεία γραμμή, είμαι
δεν πηγαίνει πέρα ​​δώθε,

480
00:22:12,620 --> 00:22:16,080
Δεν έχω κοιτάζοντας πίσω στην πραγματικότητα, αλλά
τι συμβαίνει όταν τον τοποθετήσετε

481
00:22:16,080 --> 00:22:20,302
ή της μέσα από την έναρξη της
ο κατάλογος όπως κάναμε τη Δευτέρα;

482
00:22:20,302 --> 00:22:21,010
Τι συμβαίνει;

483
00:22:21,010 --> 00:22:21,510
Ναι;

484
00:22:21,510 --> 00:22:23,122
ΚΟΙΝΟ: [δεν ακούγεται].

485
00:22:23,122 --> 00:22:24,830
ΟΜΙΛΗΤΗΣ: Ναι, ότι
ήταν η σύλληψη, έτσι δεν είναι;

486
00:22:24,830 --> 00:22:26,746
Θα θυμάστε ίσως από
συμμαθητές σας, εάν

487
00:22:26,746 --> 00:22:29,670
είχαν προβεί σε οποιαδήποτε κίνηση με
πόδια τους, ότι ήταν μια πράξη.

488
00:22:29,670 --> 00:22:33,610
Έτσι, αν υπήρχαν τρεις άνθρωποι εδώ και
το νέο πρόσωπο ανήκε τρόπο εκεί,

489
00:22:33,610 --> 00:22:37,360
σε μια μεγάλη σκηνή, όπως αυτή, βέβαια, ο ίδιος
ή θα μπορούσε απλά να πάει μέχρι το τέλος.

490
00:22:37,360 --> 00:22:40,074
Αλλά αν σκεφτόμαστε ένα
υπολογιστής και μια συστοιχία μνήμης,

491
00:22:40,074 --> 00:22:41,990
αυτοί οι άνθρωποι θα
να χρειαστεί να ανακατέψετε πάνω

492
00:22:41,990 --> 00:22:43,260
για να κάνει χώρο για το εν λόγω πρόσωπο.

493
00:22:43,260 --> 00:22:46,930
Και έτσι ώστε n μείον 1 shufflings,
n μείον 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
μείον 3 shufflings είναι ακριβώς το είδος της
συμβαίνει πίσω μου, όχι μπροστά μου

495
00:22:50,660 --> 00:22:52,710
όπως και πριν, κατά κάποιο τρόπο.

499
00:22:52,557 --> 00:22:54,640
Τώρα, ως ένα μέρος, και ως
μπορεί να έχετε δει σε απευθείας σύνδεση

500
00:22:54,640 --> 00:22:57,699
αν ξεκινήσετε σπρώχνει γύρω για
είδη, υπάρχουν τόσα πολλά διαφορετικά μέρη

501
00:22:57,699 --> 00:22:59,490
εκεί έξω, μερικοί από αυτούς
καλύτερα από άλλα.

502
00:22:59,490 --> 00:23:02,200
Πράγματι, bogosort είναι ένα
αυτό είναι το είδος της διασκέδασης να κοιτάζω προς τα πάνω.

503
00:23:02,200 --> 00:23:06,650
Bogosort παίρνει ένα σύνολο από
αριθμούς ή να πω μια τράπουλα,

504
00:23:06,650 --> 00:23:09,870
τους ανακατεύει, και
ελέγχους αν είναι ταξινομημένα.

505
00:23:09,870 --> 00:23:12,130
Και αν όχι, το κάνει ξανά.

506
00:23:12,130 --> 00:23:14,140
Και αν όχι, το κάνει ξανά.

507
00:23:14,140 --> 00:23:15,440
Αν όχι, θα το κάνει ξανά.

508
00:23:15,440 --> 00:23:17,060
Απίστευτα ηλίθια.

509
00:23:17,060 --> 00:23:19,520
>> Και πράγματι, αν μπορείτε να διαβάσετε
όπως το άρθρο της Wikipedia,

510
00:23:19,520 --> 00:23:21,200
ψευδώνυμο του είναι ηλίθιο είδος.

511
00:23:21,200 --> 00:23:25,180
Είναι τελικά θα λειτουργήσει,
ελπίζουμε, αρκετό χρόνο,

512
00:23:25,180 --> 00:23:28,240
αλλά αυτή η ποσότητα του χρόνου
θα μπορούσε να πάρει αρκετό χρόνο.

513
00:23:28,240 --> 00:23:31,650
Έτσι, αν θα μπορούσα να, ας τα πράγματα ταχύτητας
up από το παράδειγμα Μαίρη Μπεθ νωρίτερα,

514
00:23:31,650 --> 00:23:35,150
έχοντας λίγα περισσότερα στοιχεία,
αλλά δύο περισσότερους επεξεργαστές.

515
00:23:35,150 --> 00:23:37,100
Δύο άνθρωποι, αν
Δεν θα με πείραζε να συνεργαστούν μαζί μου.

516
00:23:37,100 --> 00:23:40,972
Πόσο περίπου 1 εδώ, και
ας go-- κανείς εκεί;

517
00:23:40,972 --> 00:23:41,722
Κανείς εκεί πέρα;

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
Μπορείτε με το μαύρο
shirt, ναι, έλα κάτω.

520
00:23:44,190 --> 00:23:45,000
Εντάξει, αυτό είναι το όνομά σου;

521
00:23:45,000 --> 00:23:45,720
>> ΚΟΙΝΟ: Peter.

522
00:23:45,720 --> 00:23:46,100
>> ΟΜΙΛΗΤΗΣ: Τι είναι αυτό;

523
00:23:46,100 --> 00:23:46,766
>> ΚΟΙΝΟ: Peter.

524
00:23:46,766 --> 00:23:49,450
ΟΜΙΛΗΤΗΣ: Peter, David, χαίρομαι που σε γνωρίζω.

525
00:23:49,450 --> 00:23:53,670
Εντάξει, έχουμε Peter εδώ, αν
θέλουν να έρθουν στο τραπέζι εδώ.

526
00:23:53,670 --> 00:23:54,550
Και τι είναι το όνομά σας;

527
00:23:54,550 --> 00:23:55,216
>> ΚΟΙΝΟ: Έλενα.

528
00:23:55,216 --> 00:23:55,970
ΟΜΙΛΗΤΗΣ: Έλενα.

529
00:23:55,970 --> 00:23:57,030
Εντάξει, ωραίο να σας γνωρίσουμε.

530
00:23:57,030 --> 00:23:58,060
Έλενα συναντήστε τον Πίτερ.

531
00:23:58,060 --> 00:23:59,170
Peter, Έλενα.

532
00:23:59,170 --> 00:24:02,290
Και θα πρέπει Andrew
μέχρι εδώ καλά, παρακαλώ.

533
00:24:02,290 --> 00:24:06,107
Και πρόκληση σας θα
να είναι να ταξινομήσετε μια τράπουλα.

534
00:24:06,107 --> 00:24:08,190
Και αν δεν είναι εξοικειωμένοι, κατάστρωμα
των καρτών θα πρέπει τελικά

535
00:24:08,190 --> 00:24:11,064
να ταξινομηθούν λίγο κάτι σαν
Αυτό που θα κάνουμε τα σωματεία, τότε

536
00:24:11,064 --> 00:24:13,660
τα φτυάρια, τότε οι καρδιές και
διαμάντια, από άσσο ως ένα,

537
00:24:13,660 --> 00:24:15,570
σε όλη τη διαδρομή μέχρι το βασιλιά.

538
00:24:15,570 --> 00:24:20,890
>> Οι κάρτες Πάω να σας δώσω
πρόκειται να είναι 52 σε ποσότητα.

539
00:24:20,890 --> 00:24:23,160
Εμείς πάμε για να ομοίως
χρόνο σας, ακριβώς σε μια στιγμή.

540
00:24:23,160 --> 00:24:26,410
Εμείς πάμε για να ρίξει Andrew
επάνω στην οθόνη εδώ,

541
00:24:26,410 --> 00:24:28,170
έτσι ώστε να παρακολουθήσουν το κάνετε αυτό.

542
00:24:28,170 --> 00:24:31,070
Και έτσι ώστε όλα αυτά
είναι το πιο ορατό,

543
00:24:31,070 --> 00:24:33,490
αυτά είναι τα χαρτιά που πήρα για την Amazon.

544
00:24:33,490 --> 00:24:42,861
Έτσι είναι ήδη τυχαία
ταξινομούνται, και θα πάμε να έχετε χρόνο.

545
00:24:42,861 --> 00:24:44,610
Και θα πάμε να
κρατήσει το πραγματικό αυτή τη φορά,

546
00:24:44,610 --> 00:24:47,820
έτσι θα πάμε να προσπαθήσουμε να σε πιέσω
γιατί αλλιώς αυτό θα πάρει κουραστικό

547
00:24:47,820 --> 00:24:48,460
γρήγορα.

548
00:24:48,460 --> 00:24:53,860
Αν θα μπορούσε να προχωρήσει για να ταξινομήσετε 52
στοιχεία μαζί με κάποια μέσα, τώρα.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> Και πάλι, όπως θα δούμε σε αυτά
παιδιά κάνουν ό, τι, στο τέλος

551
00:25:07,180 --> 00:25:10,200
πρόκειται να παραχθεί μια προφανή
αποτέλεσμα, σκεφτείτε πραγματικά

552
00:25:10,200 --> 00:25:12,962
πώς είστε καθένα να κάνει,
πώς θα μπορούσε να το περιγράψει.

553
00:25:12,962 --> 00:25:15,045
Επειδή πάλι, αυτές είναι
όλες οι διαδικασίες, οι αλγόριθμοι

554
00:25:15,045 --> 00:25:17,090
ότι παίρνουμε ως δεδομένο ως άνθρωπο.

555
00:25:17,090 --> 00:25:22,349
Αλλά ίσως έχετε καιρό
διαίσθηση, πολύ πριν ακόμη

556
00:25:22,349 --> 00:25:24,390
σκεφτεί τη λήψη ενός
επιστήμη των υπολογιστών τάξη σας

557
00:25:24,390 --> 00:25:27,223
θα μπορούσε να είχε την διαίσθηση με
το οποίο για την επίλυση προβλημάτων όπως αυτό.

558
00:25:27,223 --> 00:25:29,560
Αλλά τη στιγμή που θα αναγνωρίζουν
τα σχέδια και να αρχίσει

559
00:25:29,560 --> 00:25:32,407
να επισημοποιήσει τα βήματα με τα οποία
είστε επίλυση των προβλημάτων αυτών,

560
00:25:32,407 --> 00:25:35,490
θα διαπιστώσετε ότι μπορείτε να λύσετε πολλά
πιο ενδιαφέρουσα και πολύ πιο περίπλοκη

561
00:25:35,490 --> 00:25:39,190
προβλήματα γρήγορα.

562
00:25:39,190 --> 00:25:42,351
Έτσι, κάποιος από το ακροατήριο, τι είναι
τουλάχιστον ένα στοιχείο του αλγορίθμου

563
00:25:42,351 --> 00:25:43,350
ότι χρησιμοποιούν εδώ;

564
00:25:43,350 --> 00:25:44,275
>> ΚΟΙΝΟ: [δεν ακούγεται]

565
00:25:44,275 --> 00:25:45,150
ΟΜΙΛΗΤΗΣ: Τι είναι αυτό;

566
00:25:45,150 --> 00:25:47,062
ΚΟΙΝΟ: Με κοστούμι.

567
00:25:47,062 --> 00:25:47,770
ΟΜΙΛΗΤΗΣ: Με κοστούμι.

568
00:25:47,770 --> 00:25:50,630
Έτσι, η πρώτη που συσπειρώνονται
όλα τα διαμάντια μαζί

569
00:25:50,630 --> 00:25:52,560
φαίνεται, όλα τα
καρδιές μαζί, φαίνεται,

570
00:25:52,560 --> 00:25:56,520
και ούτω καθεξής, χωρίς σεβασμό
για τους αριθμούς στις κάρτες.

571
00:25:56,520 --> 00:26:00,900
Και τώρα εμφανίζονται, για παράδειγμα,
να τους διαλογή με αριθμό.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Πολύ καλό.

574
00:26:08,910 --> 00:26:12,370
>> Εντάξει, έτσι τι πρόκειται να
είναι το τελικό βήμα, τότε εδώ;

575
00:26:12,370 --> 00:26:16,950
Μόλις έχουμε τέσσερις ταξινομημένο κοστούμια, τι
εμείς πρέπει να κάνουμε για τις τέσσερις στήλες

576
00:26:16,950 --> 00:26:20,059
προκειμένου να επιτευχθεί ένα
ταξινομούνται κατάστρωμα, πολύ απλά;

577
00:26:20,059 --> 00:26:21,350
Πρέπει, λοιπόν, να τα συγχωνεύσει και πάλι.

578
00:26:21,350 --> 00:26:25,160
>> Έτσι, υπάρχει μια ενδιαφέρουσα ιδέα ότι
και πάλι, daresay, είναι πολύ διαισθητική, ακόμη και

579
00:26:25,160 --> 00:26:28,140
αν θα μπορούσαν ποτέ να έχουν χαστούκισε
αυτό το είδος της ετικέτας για αυτό.

580
00:26:28,140 --> 00:26:31,900
Αυτή η θεμελιώδης έννοια της διαίρεσης
το πρόβλημα δεν στο μισό αυτού του χρόνου,

581
00:26:31,900 --> 00:26:33,410
αλλά τουλάχιστον σε τέσσερα κομμάτια.

582
00:26:33,410 --> 00:26:36,810
Επίλυση λίγο πολύ
ουσιαστικά πανομοιότυπα προβλήματα

583
00:26:36,810 --> 00:26:40,480
σε απομόνωση μεταξύ τους,
και στη συνέχεια τη συγχώνευση των αποτελεσμάτων.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
Και, εξαιρετική, κάνει.

586
00:26:50,140 --> 00:26:52,140
Εντάξει, μια μεγάλη στρογγυλή
χειροκροτήματα, αν μπορούσαμε.

587
00:26:52,140 --> 00:26:56,480
>> [Χειροκρότημα]

588
00:26:56,480 --> 00:26:59,740
>> ΟΜΙΛΗΤΗΣ: Δεν έχω καμία ιδέα για το τι θα
κάνει με αυτά, αλλά εδώ θα πάτε.

589
00:26:59,740 --> 00:27:01,690
Σας ευχαριστώ πολύ.

590
00:27:01,690 --> 00:27:04,660
Ας δούμε, λοιπόν, δύο λεπτά
και οκτώ δευτερόλεπτα,

591
00:27:04,660 --> 00:27:07,490
αν θέλετε να προκαλέσετε τους φίλους σας.

592
00:27:07,490 --> 00:27:12,160
Τι, λοιπόν, πρόκειται να
είναι ένα πάρει μακριά από αυτό

593
00:27:12,160 --> 00:27:13,830
ότι μπορούμε να αξιοποιήσουν γενικότερα;

594
00:27:13,830 --> 00:27:16,080
Λοιπόν, σκεφτείτε ότι πίσω σε
αυτή η σειρά των αριθμών,

595
00:27:16,080 --> 00:27:19,060
και ότι πίσω τώρα σε ορισμένα από τα
pseudocode έχουμε γράψει και στο παρελθόν,

596
00:27:19,060 --> 00:27:22,080
και αυτή ήταν η ψευδοκώδικα για
την επίλυση του προβλήματος του τηλεφωνικού καταλόγου.

597
00:27:22,080 --> 00:27:25,150
Όπου σε ψευδοκώδικα I
απαρίθμησε έναν πιο μεθοδικό τρόπο

598
00:27:25,150 --> 00:27:28,400
που περιγράφει πώς έκανα ένα πολύ έξυπνο
ανθρώπινη αλγόριθμο της διαίρεσης του τηλεφώνου

599
00:27:28,400 --> 00:27:31,650
βιβλίο στη μέση, επανάληψη, επαναλαμβάνω, επαναλαμβάνω,
μέχρι να βρω κάποιον σαν τον Mike Smith,

600
00:27:31,650 --> 00:27:33,790
αν είναι όντως στον τηλεφωνικό κατάλογο.

601
00:27:33,790 --> 00:27:37,610
>> Αλλά το είδος του χρησιμοποίησε αυτό θα καλέσω
ένα πολύ επαναληπτική προσέγγιση εδώ,

602
00:27:37,610 --> 00:27:42,160
ειδικότερα ανακοίνωση της γραμμής 8 και η γραμμή 11.

603
00:27:42,160 --> 00:27:46,750
Αυτά είναι ενδείξεις μιας επαναληπτικής
προσέγγιση, μια προσέγγιση looping,

604
00:27:46,750 --> 00:27:49,040
γιατί αυτό είναι ακριβώς
η συμπεριφορά που επιφέρουν.

605
00:27:49,040 --> 00:27:52,910
Οι γραμμές και οι δύο λένε πηγαίνετε στο
γραμμή τρία, και μπορείτε να το είδος της

606
00:27:52,910 --> 00:27:55,140
σκεφτείτε ότι σας
μάτι, ως ένας βρόχος.

607
00:27:55,140 --> 00:27:59,080
Θα σας λέει να πάει πίσω μέχρι και το βήμα
τρεις και επαναλάβετε ξανά και ξανά,

608
00:27:59,080 --> 00:28:00,010
και πάλι.

609
00:28:00,010 --> 00:28:04,410
>> Αλλά τι θα γινόταν αν εμείς αξιοποιήσουμε μία βασική ιδέα
εδώ που κάναμε δεν είναι η τελευταία φορά,

610
00:28:04,410 --> 00:28:10,280
και την απλούστευση της γραμμής 8 και
γραμμή 11 και τους γείτονές τους

611
00:28:10,280 --> 00:28:12,840
, όπως ακριβώς αυτό, σε κίτρινο.

612
00:28:12,840 --> 00:28:16,480
Δεν είναι ουσιαστικά συντόμευση
η pseudocode πολύ,

613
00:28:16,480 --> 00:28:20,530
αλλά είναι θεμελιωδώς αλλαγή
η φύση του αλγόριθμου μου.

614
00:28:20,530 --> 00:28:24,220
Αυτό που είμαι τώρα λέγοντας
στο βήμα 7, στο βήμα 10,

615
00:28:24,220 --> 00:28:29,140
είναι να ψάξει για Mike
με τον ίδιο ακριβώς τρόπο,

616
00:28:29,140 --> 00:28:31,580
αλλά μόνο στην αριστερή
το μισό ή το δεξί μισό.

617
00:28:31,580 --> 00:28:33,420
>> Έτσι με άλλα λόγια, εάν
Ξεκινώ από το πρώτο βήμα,

618
00:28:33,420 --> 00:28:36,150
σηκώστε τηλεφωνικό κατάλογο, ανοιχτό σε μέση
του τηλεφωνικού καταλόγου, να δούμε τα ονόματα,

619
00:28:36,150 --> 00:28:39,010
αν Smith είναι μεταξύ
Το όνομά του, καλέστε Mike, αλλιώς

620
00:28:39,010 --> 00:28:44,340
αν Smith είναι νωρίτερα στο βιβλίο, βήμα επτά
αναζήτηση για Mike στο αριστερό μισό του βιβλίου.

621
00:28:44,340 --> 00:28:47,130
Αλλά αυτό το είδος του αισθάνεται όπως
αυτό είναι μου αφήνοντας κρέμονται, σωστά;

622
00:28:47,130 --> 00:28:49,240
Σε κίτρινο, είναι ένα
διδασκαλίας, αλλά πώς μπορώ να κάνω

623
00:28:49,240 --> 00:28:51,870
αναζήτηση για Mike στο αριστερό
το ήμισυ του τηλεφωνικού καταλόγου;

624
00:28:51,870 --> 00:28:54,210
Πού μπορώ να έχουν μια
αλγόριθμο με τον οποίο θα

625
00:28:54,210 --> 00:28:57,100
να ψάξετε για κάποιον σαν τον Mike Smith;

626
00:28:57,100 --> 00:28:58,980
Λοιπόν, αυτό είναι μας κοιτάζει επίμονα στο πρόσωπο.

627
00:28:58,980 --> 00:29:03,090
I κυριολεκτικά να χρησιμοποιούν την ίδια ακριβώς
πρόγραμμα εφαρμόζεται αποτελεσματικά ανεβαίνοντας στην κορυφή

628
00:29:03,090 --> 00:29:06,490
ξανά και εκ νέου λειτουργία
οι ίδιες γραμμές κώδικα.

629
00:29:06,490 --> 00:29:10,610
>> Έτσι, ακόμη και αν αυτό θα πρέπει να αισθάνονται
σαν ένα κομμάτι από ένα κυκλικό ορισμό

630
00:29:10,610 --> 00:29:13,480
Όπου και αν απάντηση είναι κάποιος
ερώτηση ακριβώς το είδος της ερώτησης

631
00:29:13,480 --> 00:29:15,990
το ίδιο ερώτημα και πάλι,
όπως γιατί, γιατί, γιατί;

632
00:29:15,990 --> 00:29:21,580
Η πραγματικότητα είναι, γιατί έχουμε σκληρά κωδικοποιημένους
ένα ζευγάρι από ειδικές γραμμές, βαθμίδα 4,

633
00:29:21,580 --> 00:29:25,320
το οποίο είναι ένα, αν και το βήμα 12, το οποίο
Είναι ουσιαστικά ένα άλλο υποκατάστημα,

634
00:29:25,320 --> 00:29:30,120
γιατί έχουμε αυτά τα μέτρα προσωρινή λύση,
Ο αλγόριθμος αυτός θα τερματίσει αν

635
00:29:30,120 --> 00:29:32,050
βρείτε Mike, ή αν δεν το κάνουμε.

636
00:29:32,050 --> 00:29:36,810
Αλλά στο βήμα 7 και 10 τώρα, έχουμε
τι θα καλέσετε έναν αναδρομικό αλγόριθμο.

637
00:29:36,810 --> 00:29:40,420
Και αναδρομή είναι πράγματι μια ισχυρή ιδέα
Αυτό είναι λίγο μυαλό κάμψης στην πρώτη,

638
00:29:40,420 --> 00:29:42,500
ότι μπορούμε τώρα να εφαρμόζονται ως εξής.

639
00:29:42,500 --> 00:29:46,600
>> Συγχώνευση του είδους θα είναι το τελευταίο είδος, ότι
κοιτάξουμε, τουλάχιστον στην κατηγορία επίσημα.

640
00:29:46,600 --> 00:29:50,040
Και είναι θεμελιωδώς διαφορετική
από αυτά τα τρία τελευταία, και σίγουρα

641
00:29:50,040 --> 00:29:52,140
τελευταία τέσσερα αν συμπεριλάβουμε bogosort.

642
00:29:52,140 --> 00:29:54,810
Εδώ είναι η ψευδοκώδικα για τη συγχώνευση ταξινόμησης.

643
00:29:54,810 --> 00:30:00,170
Κατά την είσοδο των n στοιχείων, δεδομένης
μια σειρά μεγέθους n, αν το η είναι μικρότερο από 2,

644
00:30:00,170 --> 00:30:01,040
επιστροφή.

645
00:30:01,040 --> 00:30:03,610
Έτσι, γιατί έχω ότι
λογικότητα ελέγξτε πρώτα;

646
00:30:03,610 --> 00:30:09,477
Ποια είναι η επίπτωση αν το χέρι σας
μια συστοιχία των οποίων το μήκος η είναι μικρότερη από 2;

647
00:30:09,477 --> 00:30:11,060
Είναι ήδη ταξινομηθεί, προφανώς, σωστά;

648
00:30:11,060 --> 00:30:13,640
Επειδή ο κατάλογος είτε έχει
ένα στοιχείο, το οποίο είναι κοινότοπα

649
00:30:13,640 --> 00:30:15,180
ταξινομούνται γιατί είναι
το μόνο πράγμα εκεί.

650
00:30:15,180 --> 00:30:18,138
Ή, είναι του μεγέθους που σημαίνει μηδέν
δεν υπάρχει τίποτα για να ταξινομήσετε, τόσο από τη φύση

651
00:30:18,138 --> 00:30:18,720
αυτό είναι ταξινομημένο.

652
00:30:18,720 --> 00:30:20,410
Δεν υπάρχει απολύτως τίποτα λάθος εκεί.

653
00:30:20,410 --> 00:30:22,310
Έτσι, αυτό είναι το λεγόμενο βασικό σενάριο μας.

654
00:30:22,310 --> 00:30:24,440
>> Αυτό είναι παρόμοιο σε πνεύμα
σε ό, τι κάναμε με τον Mike.

655
00:30:24,440 --> 00:30:26,023
Αν Mike στο βιβλίο του τηλεφώνου, να τον καλέσει.

656
00:30:26,023 --> 00:30:27,740
Αν δεν είναι εκεί, να τα παρατήσουμε.

657
00:30:27,740 --> 00:30:31,240
Είναι το λεγόμενο βασικό σενάριο, για να βεβαιωθείτε ότι
ο αλγόριθμος αυτός, στο τέλος της ημέρας

658
00:30:31,240 --> 00:30:33,540
θα σταματήσει σε ορισμένες περιπτώσεις.

659
00:30:33,540 --> 00:30:37,890
>> Αλλά εδώ είναι το άλμα της πίστης τώρα, αλλιώς,
ταξινομήσετε το αριστερό μισό των στοιχείων,

660
00:30:37,890 --> 00:30:39,740
Στη συνέχεια ταξινομήσετε το δικαίωμα
ήμισυ των στοιχείων,

661
00:30:39,740 --> 00:30:41,189
και, στη συνέχεια, να συγχωνεύσει τα ταξινομημένα μισά.

662
00:30:41,189 --> 00:30:43,230
Και εδώ είναι που αισθάνεται
όπως είμαστε copping έξω.

663
00:30:43,230 --> 00:30:46,900
Σας έχω ζητήσει να ταξινομήσετε
n στοιχεία, και είμαι

664
00:30:46,900 --> 00:30:50,712
λέει, εντάξει, δεν είναι από τη διαλογή
η αριστερά και η διαλογή του δικαιώματος.

665
00:30:50,712 --> 00:30:52,420
Αλλά εγώ λέω ένα
άλλο πράγμα, και αυτό

666
00:30:52,420 --> 00:30:55,530
είναι το βασικό θέμα φαίνεται
στη διαίσθηση μέχρι στιγμής,

667
00:30:55,530 --> 00:30:57,380
υπάρχει αυτό το τρίτο βήμα της συγχώνευσης.

668
00:30:57,380 --> 00:31:00,430
Που ακόμα κι αν
Φαίνεται τόσο χαζή σε πνεύμα,

669
00:31:00,430 --> 00:31:02,320
όπως ακριβώς η συγχώνευση πράγματα
μαζί, φαίνεται

670
00:31:02,320 --> 00:31:05,380
να είναι ένα σημαντικό βήμα προς την
επανασυναρμολόγηση των δύο προβλημάτων που

671
00:31:05,380 --> 00:31:07,330
χωρίστηκαν τελικά στο μισό.

672
00:31:07,330 --> 00:31:12,090
>> Έτσι συγχώνευση είδος, ας το κάνουμε αυτό, αν θα
το χιούμορ μου, με μια επιπλέον απόδειξη,

673
00:31:12,090 --> 00:31:14,730
ακριβώς έτσι ώστε να έχουμε κάποια
αριθμούς για να εργαστεί με.

674
00:31:14,730 --> 00:31:19,470
Μπορώ να ανταλλάξουν οκτώ στρες
μπάλες για οκτώ άτομα;

675
00:31:19,470 --> 00:31:29,320
Εντάξει, πώς για σας τρεις, τέσσερις σας
σε αυτή την ενότητα, πέντε, έξι, και ας

676
00:31:29,320 --> 00:31:30,720
Δεν 7, 8, έλα επάνω.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
Εντάξει, ναι OK.

679
00:31:36,520 --> 00:31:38,640
Μείον 8, εκεί πάμε, συν 1.

680
00:31:38,640 --> 00:31:39,150
Εξαιρετική.

681
00:31:39,150 --> 00:31:42,000
Εντάξει, έλα επάνω, ας
γρήγορα θα δώσει αριθμούς.

682
00:31:42,000 --> 00:31:50,800
Αριθμός δύο, νούμερο τρία, τέσσερα τον αριθμό,
τον αριθμό πέντε, έξι, επτά, οκτώ.

683
00:31:50,800 --> 00:31:52,140
Έκανα οκτώ σωστά αυτή τη φορά.

684
00:31:52,140 --> 00:31:56,390
>> OK, ώστε να προχωρήσει αν μπορούσε, και
ας ταξινομήσετε κατά την αρχική σειρά

685
00:31:56,390 --> 00:31:59,810
ότι είχαμε χθες που φαινόταν
όπως αυτό, αν δεν σε πειράζει.

686
00:31:59,810 --> 00:32:03,620
Και ας το κάνουμε μπροστά από το τραπέζι.

687
00:32:03,620 --> 00:32:06,510
Εντάξει, έτσι συγχώνευση ταξινόμησης.

688
00:32:06,510 --> 00:32:08,820
Αυτό είναι όπου πρόκειται
για να πάρει το είδος της ενδιαφέρον,

689
00:32:08,820 --> 00:32:12,800
γιατί μου φαίνεται να δίνει ο ίδιος
έτσι πολύ λιγότερες πληροφορίες σήμερα.

690
00:32:12,800 --> 00:32:15,149
>> Έτσι συγχώνευση είδος πρώτα απ 'όλα
την είσοδο των n στοιχείων,

691
00:32:15,149 --> 00:32:18,440
και προφανώς δεν είναι μικρότερη από δύο, είναι
οκτώ, οπότε έχω κάποια δουλειά να κάνουμε.

692
00:32:18,440 --> 00:32:21,140
Μέχρι τώρα διανοητικά εμείς ως τάξη
είναι τώρα στο υποκατάστημα άλλο,

693
00:32:21,140 --> 00:32:22,540
πράγμα που σημαίνει τρία βήματα.

694
00:32:22,540 --> 00:32:25,017
Πρώτον, πρέπει να ταξινομήσετε το
αριστερό ήμισυ των στοιχείων.

695
00:32:25,017 --> 00:32:26,350
Λοιπόν, πώς μπορώ να το κάνουμε αυτό;

696
00:32:26,350 --> 00:32:28,950
Λοιπόν, θα πάω με το είδος της
διανοητικά χωρίζουν τη λίστα εδώ,

697
00:32:28,950 --> 00:32:30,700
δεν χρειάζεται να
μετακινήστε με φυσικό τρόπο, και είμαι

698
00:32:30,700 --> 00:32:33,180
πρόκειται να επικεντρωθεί μόνο στην
αριστερό ήμισυ από τα στοιχεία εδώ.

699
00:32:33,180 --> 00:32:36,770
Λοιπόν, πώς μπορώ να πάω για διαλογή
μια λίστα τώρα από το μέγεθος τέσσερα;

700
00:32:36,770 --> 00:32:38,730
Τι είναι ο αλγόριθμος μου;

701
00:32:38,730 --> 00:32:42,580
Πρώτα να ελέγξω είναι n λιγότερο από δύο, όχι,
γι 'αυτό προχωρήστε στο μπλοκ άλλο πάλι.

702
00:32:42,580 --> 00:32:43,900
Ταξινόμηση αριστερό μισό των στοιχείων.

703
00:32:43,900 --> 00:32:45,608
>> Μέχρι τώρα πάλι, διανοητικά,
και αυτό είναι όπου

704
00:32:45,608 --> 00:32:49,550
θα πρέπει να προκύψουν πολλά
διανοητική ιστορία, αν θέλετε.

705
00:32:49,550 --> 00:32:51,940
Τώρα είμαι διαλογής το αριστερό
ήμισυ του αριστερού ημίσεως.

706
00:32:51,940 --> 00:32:57,000
Εντάξει, έτσι και τώρα καλώ ίδια της συγχώνευσης μου
διαλογής αλγόριθμος, είναι n λιγότερο από δύο;

707
00:32:57,000 --> 00:33:00,590
Όχι, δεν είναι δύο, γι 'αυτό πρέπει να ταξινομήσετε
το αριστερό μισό, και το δεξί μισό.

708
00:33:00,590 --> 00:33:02,042
Πάμε λοιπόν, να ταξινομήσετε το αριστερό μισό.

709
00:33:02,042 --> 00:33:03,750
Γιατί δεν κάνουν απλά
πάρτε ένα βήμα προς τα εμπρός.

710
00:33:03,750 --> 00:33:04,415
Ποιο είναι το όνομά σου;

711
00:33:04,415 --> 00:33:04,860
>> ΚΟΙΝΟ: Darren.

712
00:33:04,860 --> 00:33:05,260
>> ΟΜΙΛΗΤΗΣ: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan έχει κάνει βήματα μπροστά.

714
00:33:06,040 --> 00:33:06,748
>> ΚΟΙΝΟ: Darren.

715
00:33:06,748 --> 00:33:09,000
ΟΜΙΛΗΤΗΣ: Darren, γίνεται.

716
00:33:09,000 --> 00:33:10,090
Μήπως λέτε Darren ή Dan;

717
00:33:10,090 --> 00:33:10,550
>> ΚΟΙΝΟ: Darren.

718
00:33:10,550 --> 00:33:11,216
>> ΟΜΙΛΗΤΗΣ: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren έχει ενισχυθεί
προς τα εμπρός και είναι τώρα ταξινομούνται.

720
00:33:14,422 --> 00:33:16,130
Και αυτό είναι σχεδόν μια
ανόητος ισχυρισμός, σωστά;

721
00:33:16,130 --> 00:33:18,862
Δεν φαίνεται πραγματικά να επιτευχθεί
τίποτα, αλλά ας προχωρήσουμε.

722
00:33:18,862 --> 00:33:20,820
Τώρα, επιτρέψτε μου να ταξινομήσετε το δικαίωμα
ήμισυ των στοιχείων.

723
00:33:20,820 --> 00:33:21,200
Ποιο είναι το όνομά σου;

724
00:33:21,200 --> 00:33:21,690
>> ΚΟΙΝΟ: Luke.

725
00:33:21,690 --> 00:33:22,273
>> ΟΜΙΛΗΤΗΣ: Luke.

726
00:33:22,273 --> 00:33:23,400
Έλα, βήμα προς τα εμπρός.

727
00:33:23,400 --> 00:33:25,640
Τέλος, έχω ταξινομούνται Λουκά.

728
00:33:25,640 --> 00:33:28,570
Το αριστερό μισό είναι τώρα ταξινομούνται και
το δεξί μισό τώρα ταξινομούνται,

729
00:33:28,570 --> 00:33:30,770
αλλά και πάλι, υπάρχει ένα βασικό βήμα εδώ.

730
00:33:30,770 --> 00:33:32,940
Τι μπορώ να κάνω το επόμενο πρέπει να κάνουμε;

731
00:33:32,940 --> 00:33:33,941
Συγχώνευση τα ταξινομημένα μισά.

732
00:33:33,941 --> 00:33:36,648
Τώρα θα πάμε να έχουν μόνο
όλοι εμπρός και πίσω με τον τρόπο αυτό,

733
00:33:36,648 --> 00:33:38,620
γιατί το είδος του πρέπει
κάποιο διάστημα το μηδέν.

734
00:33:38,620 --> 00:33:40,411
Είναι σχεδόν σαν αυτά
οι τύποι είναι σε ένα τραπέζι,

735
00:33:40,411 --> 00:33:42,460
και χρειάζομαι κάποια δωμάτια
να τα μετακινήσετε γύρω από την.

736
00:33:42,460 --> 00:33:44,170
Έτσι, Πάω να συγχωνεύσει
εσείς κοιτάζοντας

737
00:33:44,170 --> 00:33:45,960
στο αριστερό μισό και το δεξί μισό.

738
00:33:45,960 --> 00:33:48,740
Και που προφανώς έρχεται πρώτη,
αριστερό μισό ή δεξιά ημίχρονο;

739
00:33:48,740 --> 00:33:52,710
Έτσι ακριβώς το μισό, οπότε ας προχωρήσουμε Luke πάνω
εδώ στην αρχική θέση του Ντάρεν.

740
00:33:52,710 --> 00:33:57,640
Και τώρα να συγχωνεύσει το αριστερό μισό σε,
Darren πρόκειται να προχωρήσουμε εκεί.

741
00:33:57,640 --> 00:33:59,750
>> Έτσι μοιάζει σχεδόν
ένα φαινόμενο bubble sort,

742
00:33:59,750 --> 00:34:02,482
αλλά τα θεμελιώδη αλγόριθμο μου,
πολύ διαφορετικά αυτή τη φορά.

743
00:34:02,482 --> 00:34:04,815
Αλλά τώρα είναι όπου τα πράγματα παίρνουν μια
λίγο ενοχλητικό γιατί

744
00:34:04,815 --> 00:34:06,810
Πρέπει να rewind διανοητικά
όπου άφησα off.

745
00:34:06,810 --> 00:34:09,893
Έχω μόλις συγχωνεύτηκαν τα ταξινομημένα μισά,
πράγμα που σημαίνει ότι είμαι όπου με αλγόριθμο μου;

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Θα πρέπει να ταξινομήσετε το δεξί μισό, σωστά;

748
00:34:13,770 --> 00:34:15,910
>> Αν πίσω, κυριολεκτικά
για το βίντεο, εσείς θα

749
00:34:15,910 --> 00:34:18,339
δείτε ότι φτάσαμε σε αυτό το
σημείο του Λουκά και Darren

750
00:34:18,339 --> 00:34:21,370
ταξινομώντας το αριστερό
ήμισυ του αριστερού ημίσεως.

751
00:34:21,370 --> 00:34:23,430
Στη συνέχεια συγχωνεύθηκαν εκείνες
ταξινομημένα μισά, το οποίο

752
00:34:23,430 --> 00:34:27,941
σημαίνει ότι το επόμενο βήμα είναι το είδος της
δεξί μισό του αριστερό μισό.

753
00:34:27,941 --> 00:34:29,649
Εντάξει, ας
το κάνουμε αυτό πιο γρήγορα.

754
00:34:29,649 --> 00:34:33,282
Εντάξει, έξι, Πάω να διεκδικήσει
μπορείτε τώρα ταξινομούνται, έλα προς τα εμπρός.

755
00:34:33,282 --> 00:34:33,990
Ποιο είναι το όνομά σου;

756
00:34:33,990 --> 00:34:34,589
>> ΚΟΙΝΟ: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> ΟΜΙΛΗΤΗΣ: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano τώρα ταξινομούνται.

759
00:34:36,010 --> 00:34:36,450
Και τι είναι το όνομά σας;

760
00:34:36,450 --> 00:34:37,080
>> ΚΟΙΝΟ: Alex.

761
00:34:37,080 --> 00:34:38,379
>> ΟΜΙΛΗΤΗΣ: Alex τώρα ταξινομούνται.

762
00:34:38,379 --> 00:34:40,750
Αριστερό μισό, δεξί μισό,
Ποιο είναι το τελικό βήμα;

763
00:34:40,750 --> 00:34:41,250
Συγχώνευση.

764
00:34:41,250 --> 00:34:44,310
Αρκετά ασήμαντο, έτσι είμαι
πρόκειται να συγχωνευθούν σε έξι,

765
00:34:44,310 --> 00:34:46,930
κάνουμε ένα βήμα πίσω,
οκτώ, κάνουμε ένα βήμα πίσω.

766
00:34:46,930 --> 00:34:49,530
Και σήμερα παρατηρούμε ότι αυτό είναι
ένα χρήσιμο πακέτο, τι

767
00:34:49,530 --> 00:34:53,930
είναι πλέον αλήθεια για το αριστερό μισό της
λίστα, ανεξάρτητα από το πώς ξεκινήσαμε;

768
00:34:53,930 --> 00:34:55,090
Θα είναι ταξινομημένο.

769
00:34:55,090 --> 00:34:57,750
>> Τώρα αυτό δεν είναι ταξινομημένα σε
το μεγάλο σχέδιο των πραγμάτων,

770
00:34:57,750 --> 00:35:00,250
αλλά είναι ταξινομημένο ανεξάρτητα
από το άλλο μισό.

771
00:35:00,250 --> 00:35:04,100
Τώρα ποιο στάδιο είμαι στο αν κρατώ
κουρδίζεται το πώς ξεκίνησε η ιστορία;

772
00:35:04,100 --> 00:35:05,680
Τώρα έχω να ταξινομήσετε το δεξί μισό.

773
00:35:05,680 --> 00:35:07,630
Μέχρι τώρα είμαστε πολύ πίσω σε
η αρχή της ιστορίας,

774
00:35:07,630 --> 00:35:08,921
και ας το κάνουμε αυτό πιο γρήγορα.

775
00:35:08,921 --> 00:35:11,320
Έτσι, Πάω να ταξινομήσετε τα
δεξί μισό του όλη τη λίστα.

776
00:35:11,320 --> 00:35:13,060
Ποιο είναι το επόμενο βήμα;

777
00:35:13,060 --> 00:35:15,840
Ταξινομήστε το αριστερό μισό του δεξί μισό.

778
00:35:15,840 --> 00:35:18,715
Ταξινομήστε το αριστερό μισό της
αριστερό μισό του δεξί μισό.

779
00:35:18,715 --> 00:35:19,590
Και τι είναι το όνομά σας;

780
00:35:19,590 --> 00:35:20,230
>> ΚΟΙΝΟ: Omar.

781
00:35:20,230 --> 00:35:21,970
>> ΟΜΙΛΗΤΗΣ: Omar, βήμα προς τα εμπρός, γίνεται.

782
00:35:21,970 --> 00:35:22,860
Αριστερό μισό είναι ταξινομημένο.

783
00:35:22,860 --> 00:35:23,330
Και τι είναι το όνομά σας;

784
00:35:23,330 --> 00:35:23,820
>> ΚΟΙΝΟ: Chris.

785
00:35:23,820 --> 00:35:25,620
>> ΟΜΙΛΗΤΗΣ: Chris, κάνουμε ένα βήμα
προς τα εμπρός, που τώρα ταξινομούνται.

786
00:35:25,620 --> 00:35:27,010
Ποιο είναι το βασικό βήμα τώρα;

787
00:35:27,010 --> 00:35:27,510
Συγχώνευση.

788
00:35:27,510 --> 00:35:30,509
Έτσι, κανείς δεν πρόκειται να συγχωνευθούν σε θέση
εδώ, αν θα μπορούσατε να πάρετε ένα βήμα πίσω,

789
00:35:30,509 --> 00:35:32,930
και τρεις πρόκειται να
κάνουμε ένα βήμα πίσω, συγχώνευση.

790
00:35:32,930 --> 00:35:38,080
Έτσι, το αριστερό μισό της
δεξί μισό, τώρα ταξινομούνται.

791
00:35:38,080 --> 00:35:41,747
Ειλικρινά, ο αλγόριθμος αυτός αισθάνεται σαν να
σπαταλάτε τον τρόπο περισσότερο χρόνο από ό, τι πριν,

792
00:35:41,747 --> 00:35:44,830
αλλά αν το κάναμε αυτό σε πραγματικό χρόνο, εμείς θα
δείτε τι τα φαστ φουντ πρόκειται να είναι.

793
00:35:44,830 --> 00:35:47,970
Τώρα είμαι εδώ, σωστά
μισό του δεξιού μισού,

794
00:35:47,970 --> 00:35:50,170
επιτρέψτε μου να πάει μπροστά και να ταξινομήσετε το αριστερό μισό.

795
00:35:50,170 --> 00:35:51,482
Βήμα προς τα εμπρός, ποιο είναι το όνομά σας;

796
00:35:51,482 --> 00:35:52,190
ΚΟΙΝΟ: Ramsey.

797
00:35:52,190 --> 00:35:53,210
ΟΜΙΛΗΤΗΣ: Ramsey τώρα ταξινομούνται.

798
00:35:53,210 --> 00:35:53,570
Ποιο είναι το όνομά σου;

799
00:35:53,570 --> 00:35:54,200
>> ΚΟΙΝΟ: Μαρίνα.

800
00:35:54,200 --> 00:35:57,033
>> ΟΜΙΛΗΤΗΣ: Μαρίνα είναι τώρα ταξινομούνται ως
καλά, αν πάρετε ένα βήμα προς τα εμπρός.

801
00:35:57,033 --> 00:36:00,690
Βασικά βήμα εδώ είναι τώρα συγχωνεύονται, είμαι
πρόκειται να κόβω από δύο λίστες μου,

802
00:36:00,690 --> 00:36:01,720
αριστερά και δεξιά.

803
00:36:01,720 --> 00:36:05,150
Πέντε πρόκειται να έρθει πρώτα,
και επτά πρόκειται να έρθει το επόμενο.

804
00:36:05,150 --> 00:36:06,410
Και πάλι, αυτό είναι σκόπιμη.

805
00:36:06,410 --> 00:36:08,535
Το γεγονός ότι παίρνετε
βήματα προς τα εμπρός και πίσω

806
00:36:08,535 --> 00:36:12,997
έχει ως στόχο να δηλώνετε ότι δεν μπορούμε
κάνει αυτόν τον αλγόριθμο στη θέση του, όπως εύκολα

807
00:36:12,997 --> 00:36:15,830
ως bubble sort, και το είδος επιλογής,
και το είδος εισαγωγής, όπου απλά

808
00:36:15,830 --> 00:36:16,960
φυλάσσονται swapping ανθρώπους.

809
00:36:16,960 --> 00:36:19,940
I κυριολεκτικά χρειάζεται ένα είδος
χαρτί το μηδέν στην οποία

810
00:36:19,940 --> 00:36:21,827
να θέσει αυτά τα παιδιά
ενώ κάνω τη συγχώνευση,

811
00:36:21,827 --> 00:36:23,410
και, στη συνέχεια, μπορώ να τους βάλει στη θέση του.

812
00:36:23,410 --> 00:36:27,260
Και αυτό είναι το κλειδί, επειδή είμαι χρησιμοποιώντας ένα
νέων πόρων, το διάστημα, όχι μόνο χρόνο.

813
00:36:27,260 --> 00:36:28,270
>> Εντάξει, αυτό είναι εκπληκτικό.

814
00:36:28,270 --> 00:36:32,050
Αριστερό μισό είναι ταξινομημένο, δεξί ήμισυ
ταξινομημένο, τώρα ότι κλειδί συγχώνευση βήμα.

815
00:36:32,050 --> 00:36:33,450
Πώς θα πάω να συγχωνεύσει αυτό;

816
00:36:33,450 --> 00:36:35,470
Έτσι, αν θα ακολουθήσει μου
αριστερό χέρι και το δεξί χέρι,

817
00:36:35,470 --> 00:36:38,930
Πάω να επισημάνω το αριστερό μου χέρι
στο αριστερό μισό, μου το δεξί του χέρι

818
00:36:38,930 --> 00:36:42,680
στο δεξιό μισό, και τώρα έχω να
αποφασίσει βήμα προς βήμα το οποίο να συγχωνευθούν σε.

819
00:36:42,680 --> 00:36:44,650
Ποιος προφανώς έρχεται πρώτο;

820
00:36:44,650 --> 00:36:45,150
Νούμερο ένα.

821
00:36:45,150 --> 00:36:47,327
Έτσι, έλα εδώ,
εδώ είναι πρόχειρο μας.

822
00:36:47,327 --> 00:36:49,910
Μέχρι τώρα νούμερο ένα, και ανακοίνωση
τι θα κάνω με το δεξί μου χέρι,

823
00:36:49,910 --> 00:36:54,152
Πάω να μετακινηθείτε προς τα δεξιά το ένα χέρι μου
βήμα πάνω στο σημείο αριθμός τρία,

824
00:36:54,152 --> 00:36:55,860
και τώρα έχω να κάνω
την ίδια απόφαση.

825
00:36:55,860 --> 00:36:58,387
Και πραγματικά να σταθεί σωστά σε
μπροστά από Luke εδώ αν μπορούσα,

826
00:36:58,387 --> 00:36:59,720
γιατί αυτό είναι πρόχειρο μας.

827
00:36:59,720 --> 00:37:00,610
Μέχρι που έρχεται το επόμενο;

828
00:37:00,610 --> 00:37:05,000
Έχουμε Λουκά με αριθμό δύο
ή Chris με τον αριθμό τρία.

829
00:37:05,000 --> 00:37:07,460
Προφανώς Λουκά, τον αριθμό
δύο, έτσι ώστε να έρθει εδώ.

830
00:37:07,460 --> 00:37:11,270
>> Αλλά το αριστερό χέρι μου τώρα πρόκειται να
να αυξάνεται με το σημείο στο Darren,

831
00:37:11,270 --> 00:37:15,160
και εδώ είναι το κλειδί για να πάρει με
συγχώνευση, Πάω να συνεχίσω να το κάνω αυτό,

832
00:37:15,160 --> 00:37:17,340
Προφανώς, αν το είδος
από τη λογική.

833
00:37:17,340 --> 00:37:19,670
Αλλά τα χέρια μου δεν είναι ποτέ
πρόκειται να πάει προς τα πίσω,

834
00:37:19,670 --> 00:37:23,861
πράγμα που σημαίνει ότι είμαι μόνο ποτέ να κινείται
η αριστερά με την διαδικασία συγχώνευσης μου,

835
00:37:23,861 --> 00:37:26,360
και ότι πρόκειται να είναι το κλειδί για την
ανάλυσή μας σε μια στιγμή.

836
00:37:26,360 --> 00:37:27,859
>> Έτσι τώρα ας τελειώσουμε αυτό επάνω γρήγορα.

837
00:37:27,859 --> 00:37:31,650
Έτσι, τρία έρχεται το επόμενο,
Στη συνέχεια τέσσερις έρχεται το επόμενο,

838
00:37:31,650 --> 00:37:38,750
και τώρα πέντε έρχεται δίπλα, στη συνέχεια, έξι,
και επτά, και στη συνέχεια, τελικά οκτώ.

839
00:37:38,750 --> 00:37:42,960
Αίσθηση σαν το πιο αργό αλγόριθμο
ακόμα, αλλά αν δεν είμαστε πραγματικά

840
00:37:42,960 --> 00:37:45,510
τρέξει στο ίδιο είδος
από την ταχύτητα του ρολογιού, έτσι ώστε να

841
00:37:45,510 --> 00:37:48,106
μιλούν, με τον ίδιο
ρολόι που χτυπάει όπως πριν.

842
00:37:48,106 --> 00:37:48,605
Γιατί;

843
00:37:48,605 --> 00:37:51,100
Λοιπόν, ας ρίξουμε μια
δείτε το τελικό αποτέλεσμα.

844
00:37:51,100 --> 00:37:56,990
>> Ας πάμε πίσω εδώ, επιτρέψτε μου να
τραβήξτε μια επίδειξη οπτικά

845
00:37:56,990 --> 00:37:59,030
του τι κάναμε.

846
00:37:59,030 --> 00:38:06,110
Μεγέθυνση εδώ, σε αυτό το
σελίδα εδώ, λέγοντας Firefox

847
00:38:06,110 --> 00:38:08,200
ότι θέλουμε να περιμένω στην ουρά
σε αυτό το πλαίσιο, ας

848
00:38:08,200 --> 00:38:11,260
λένε bubble sort, με την οποία
είμαστε τώρα καλά εξοικειωμένοι,

849
00:38:11,260 --> 00:38:14,130
είδος επιλογής, το οποίο είναι ένα άλλο
αρκετά απλή ένα,

850
00:38:14,130 --> 00:38:18,250
και τώρα η σημερινή συγχώνευση ταξινόμησης, η οποία
θα είναι κλιμακούμενη τέλος μας.

851
00:38:18,250 --> 00:38:21,530
Ο λόγος που πήρε τόσο πολύ περισσότερο
εδώ με τους ανθρώπους και μου προφορικά είναι,

852
00:38:21,530 --> 00:38:23,480
Προφανώς, είμαι εξηγώντας κάθε βήμα.

853
00:38:23,480 --> 00:38:26,920
Αλλά αν μπορείτε απλά να εκτελέσει αυτό, πολύ
όπως κάναμε bubble sort και επιλογή

854
00:38:26,920 --> 00:38:30,890
ταξινόμησης όχι μόνο οπτικά, ρολόι
πόσο πιο αποτελεσματικά

855
00:38:30,890 --> 00:38:33,330
αυτή η μόχλευση των
διαίρεση και κατάκτηση

856
00:38:33,330 --> 00:38:39,150
μπορεί να είναι όταν εφαρμόζεται σε ένα σύνολο δεδομένων που είναι
όχι ακόμη και μέγεθος οκτώ, αλλά ακόμη και πολύ,

857
00:38:39,150 --> 00:38:39,970
πολύ μεγαλύτερο.

858
00:38:39,970 --> 00:38:44,585
Σας δίνω συγχώνευση είδος, πλάι
πλευρά με αυτές τις άλλες αλγόριθμους.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Αυτό πρόκειται να πάρει επώδυνες
γρήγορα, και η κατάληξη

861
00:38:58,530 --> 00:39:00,890
δεν είναι ιδιαίτερα κλιμακούμενη,
το μόνο που καταλήγουν να ταξινομούνται.

862
00:39:00,890 --> 00:39:05,280
Αλλά το κλειδί για να πάρει είναι ότι
κοίτα πόσο πιο γρήγορα συγχώνευση ταξινόμησης

863
00:39:05,280 --> 00:39:08,110
ήταν, αν νομίζετε ότι είμαι
ακριβώς το είδος των πειράξουν μαζί σας.

864
00:39:08,110 --> 00:39:13,100
Αν το κάνουμε αυτό μία τελευταία φορά,
ας αφήσουμε φορτώσετε αυτό, ας πάμε πίσω

865
00:39:13,100 --> 00:39:14,960
και επιλέξτε bubble sort,
και μόνο για πλάκα,

866
00:39:14,960 --> 00:39:17,330
ας επιλέξουν την εισαγωγή
είδος, μόνο για το καλό μέτρο.

867
00:39:17,330 --> 00:39:20,020
Και πάλι αυτή τη φορά, ας
επιλέξετε συγχώνευση ταξινόμησης και ας

868
00:39:20,020 --> 00:39:21,595
λειτουργεί πραγματικά αυτά πλάι-πλάι.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> Και δεν είναι, στην πραγματικότητα, μια απροσδόκητη επιτυχία.

871
00:39:26,930 --> 00:39:31,140
Αυτό που έχω κάνει είναι αποτελεσματικά έχω
χωρίζεται εισόδου μου στο μισό, και πάλι,

872
00:39:31,140 --> 00:39:32,240
και ξανά, και ξανά.

873
00:39:32,240 --> 00:39:35,590
Και υπάρχει μόνο τόσες πολλές φορές μπορείτε να
χωρίζουν τη συμβολή σας στη μέση, αριστερά

874
00:39:35,590 --> 00:39:36,240
και δεξιά.

875
00:39:36,240 --> 00:39:39,425
Τι είναι ο τύπος που κρατάμε βλέπουμε
που περιγράφει τη διαίρεση κατά το ήμισυ

876
00:39:39,425 --> 00:39:41,050
ξανά, και ξανά, και ξανά, και ξανά;

877
00:39:41,050 --> 00:39:41,890
>> ΚΟΙΝΟ: Log n.

878
00:39:41,890 --> 00:39:42,760
>> ΟΜΙΛΗΤΗΣ: Log n.

879
00:39:42,760 --> 00:39:46,300
Στη συνέχεια, όμως υπάρχει ένα άλλο σημαντικό βήμα,
ο αλγόριθμος αυτός δεν είναι log n βήματα.

880
00:39:46,300 --> 00:39:48,992
Αν ήταν μόνο log n βήματα,
θα είναι στο ίδιο πρόβλημα

881
00:39:48,992 --> 00:39:51,200
όπως και πριν, όπου δεν μπορούμε να είμαστε
ότι όλα είναι ταξινομημένα.

882
00:39:51,200 --> 00:39:54,480
Θα πρέπει να κοιτάξουμε ελάχιστα n στοιχεία
για να είστε σίγουροι n Τα στοιχεία ταξινομούνται,

883
00:39:54,480 --> 00:39:55,950
αλλιώς είναι ένα άλμα πίστης.

884
00:39:55,950 --> 00:39:59,810
>> Έτσι είναι ελάχιστα log n βήματα, αλλά
τι γίνεται με αυτό το βασικό βήμα για τη συγχώνευση

885
00:39:59,810 --> 00:40:04,370
όπου συγχωνεύονται αριστερό μισό και το δικαίωμά μου
μισό και περπάτησε κατά μήκος της σκηνής;

886
00:40:04,370 --> 00:40:06,980
Πόσα βήματα είναι ότι για τη συγχώνευση;

887
00:40:06,980 --> 00:40:10,150
Είναι n, αλλά δεν το έκανα μόνο
συγχωνεύσει την τελευταία φορά.

888
00:40:10,150 --> 00:40:15,089
Σε κάθε μία από αυτές τις ένθετες κλήσεις, για κάθε
αυτών των ένθετων συγχωνεύσεις, ακόμα ταξινομηθεί.

889
00:40:15,089 --> 00:40:18,380
Θα συγχωνευθούν αυτά τα δύο παιδιά, τότε αυτά τα δύο
παιδιά, τότε αυτά τα δύο παιδιά και ούτω καθεξής.

890
00:40:18,380 --> 00:40:19,955
>> Έτσι έκανα συγχώνευση ξανά, και ξανά.

891
00:40:19,955 --> 00:40:20,580
Πόσες φορές;

892
00:40:20,580 --> 00:40:23,510
Έτσι, κάθε φορά που διαιρείται το
κατάλογος στο μισό, έκανα μια συγχώνευση.

893
00:40:23,510 --> 00:40:25,460
Χωρίστε τη λίστα στο μισό, κάνει μια συγχώνευση.

894
00:40:25,460 --> 00:40:28,570
Έτσι, αν διαιρώντας τη λίστα
μπορεί να γίνει φορές log n,

895
00:40:28,570 --> 00:40:33,880
και η συγχώνευση παίρνει τελικά n
βήματα, αυτό θα μπορούσε να είναι τώρα το ανώτερο

896
00:40:33,880 --> 00:40:37,000
δεσμεύεται για τη λειτουργία
χρόνου του αλγορίθμου μας;

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> Και πράγματι, αυτό είναι ό, τι
έχουμε επιτύχει εδώ.

899
00:40:40,560 --> 00:40:44,650
Έτσι, η αίσθηση που βλέπετε οπτικά όταν
αυτά τα τρία πράγματα που τρέχουν πλάι-πλάι

900
00:40:44,650 --> 00:40:47,930
είναι n τετράγωνο εναντίον n
τετράγωνο εναντίον n log n.

901
00:40:47,930 --> 00:40:51,010
Που ουσιαστικά θα δούμε,
όχι μόνο σήμερα αλλά και στο μέλλον,

902
00:40:51,010 --> 00:40:52,760
είναι πολύ, πολύ πιο γρήγορα.

903
00:40:52,760 --> 00:40:56,010
Ένα χειροκρότημα για αυτά τα παιδιά,
Θα τους ανταμείψει με μπάλες άγχος.

904
00:40:56,010 --> 00:41:00,260
Ας διακόψουμε εδώ σήμερα, και
εμείς θα δούμε τη Δευτέρα.

905
00:41:00,260 --> 00:41:02,255