1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Εβδομάδα 3, Συνέχεια]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Πανεπιστήμιο του Χάρβαρντ]

3
00:00:04,110 --> 00:00:07,130
>> [Αυτό είναι CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Εντάξει. Καλώς ήρθατε και πάλι. Αυτό είναι CS50 και αυτό είναι το τέλος της εβδομάδας 3.

5
00:00:11,010 --> 00:00:14,680
>> Έτσι, για όσους δεν είναι εξοικειωμένοι, πέρυσι Χάρβαρντ ξεκίνησε αυτό που ονομάζεται το Εργαστήριο Καινοτομίας,

6
00:00:14,680 --> 00:00:18,530
ή i-εργαστήριο, το οποίο είναι ένα θαυμάσιο κτήριο κατά μήκος του ποταμού στην πανεπιστημιούπολη του ΕΟΠ

7
00:00:18,530 --> 00:00:22,640
η οποία είναι ανοικτή σε φοιτητές, σπουδαστές ΓΥΓ, οι μαθητές από όλα σε όλη την πανεπιστημιούπολη,

8
00:00:22,640 --> 00:00:27,000
συμπεριλαμβανομένης της σχολής, και αυτό είναι ένα μέρος για να έρθει μαζί για να εργαστούν σε καινοτόμες πράγματα,

9
00:00:27,000 --> 00:00:29,180
ιδιαίτερα της επιχειρηματικής πράγματα

10
00:00:29,180 --> 00:00:33,410
αν και 0 ή περισσότερους φίλους που σκέφτονται να κάνουν κάτι επιχειρηματικής

11
00:00:33,410 --> 00:00:37,080
είτε κατά τη διάρκεια αυτής της κατηγορίας, μετά από αυτή την κατηγορία, ή πέραν αυτού.

12
00:00:37,080 --> 00:00:41,540
>> Έτσι, ένα από τα πράγματα που κάνουν πάνω από J όρος είναι αυτά τα ταξίδια,

13
00:00:41,540 --> 00:00:44,510
ένα από τα οποία είναι η Νέα Υόρκη, το ένα εκ των οποίων είναι να Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
Το διάστημα είναι πολύ περιορισμένη, αλλά αυτό είναι μια ευκαιρία για να τρίψετε τους ώμους με MBAs

15
00:00:47,530 --> 00:00:52,200
και μεταπτυχιακούς φοιτητές σε όλη την πανεπιστημιούπολη και στην πραγματικότητα περνούν το χρόνο τους στις αντίστοιχες περιοχές

16
00:00:52,200 --> 00:00:55,500
κουβεντιάζοντας μέχρι ξεκινήματα, να κουβεντιάσει επάνω τους επιχειρηματίες και τα παρόμοια.

17
00:00:55,500 --> 00:00:57,870
Έτσι, αν ενδιαφέρεστε, ελέγξτε έξω αυτό το URL εδώ.

18
00:00:57,870 --> 00:01:01,220
Είναι επίσης διαθέσιμο στις διαφάνειες σε απευθείας σύνδεση.

19
00:01:01,220 --> 00:01:04,610
>> Θα μπορούσε να μετριάσει τον ήχο σπίτι μόλις λίγο;

20
00:01:04,610 --> 00:01:08,640
Αν θα θέλατε να ενωθούν μαζί μας για μεσημεριανό αυτή την Παρασκευή, 1:15 μ.μ. στο Fire & Ice, παρακαλώ κεφάλι εκεί.

21
00:01:08,640 --> 00:01:11,390
Συγνώμη αν η φόρμα είναι ήδη γεμάτο από τη στιγμή που θα φτάσετε εκεί.

22
00:01:11,390 --> 00:01:13,750
Αλλά εμείς θα συνεχίσουμε αυτή την παράδοση και μετά.

23
00:01:13,750 --> 00:01:17,350
>> Σήμερα συνεχίζουμε τη συζήτηση υψηλότερο επίπεδο από διάφορα προβλήματα που μπορούμε να λύσουμε,

24
00:01:17,350 --> 00:01:21,330
εστιάζοντας πολύ λιγότερο, σήμερα τουλάχιστον, για κώδικα και πολύ περισσότερο για τις ιδέες.

25
00:01:21,330 --> 00:01:24,720
Έτσι σκέφτονται πίσω στο εβδομάδα 0, όταν έσκισε ένα βιβλίο τηλέφωνο στο μισό,

26
00:01:24,720 --> 00:01:28,260
στόχος της οποίας ήταν να κάνει κάτι, ομολογουμένως, λίγο δραματικό

27
00:01:28,260 --> 00:01:32,360
αλλά να στείλουν το σημείο ότι η έρευνα δεν πρέπει να είναι, κατ 'ανάγκην,

28
00:01:32,360 --> 00:01:35,100
ως προφανές με την πρώτη ματιά, όπως μπορείτε να σκεφτείτε.

29
00:01:35,100 --> 00:01:40,200
Και την επίλυση προβλημάτων σε γενικές γραμμές μπορεί να μην είναι πάντα κατ 'ανάγκην να είναι η καλύτερη -

30
00:01:40,200 --> 00:01:44,130
Η πιο προφανής λύση δεν μπορεί κατ 'ανάγκη να είναι το καλύτερο.

31
00:01:44,130 --> 00:01:47,300
Έτσι είχαμε αυτό το βιβλίο τηλέφωνο και, ειλικρινά, όλοι μας σε αυτό το δωμάτιο είχε τα ένστικτα,

32
00:01:47,300 --> 00:01:51,470
κατά πάσα πιθανότητα, για να αρχίσει στη μέση, όταν ψάχνει για Mike Smith και στη συνέχεια να πάει αριστερά ή δεξιά

33
00:01:51,470 --> 00:01:54,280
με βάση ό, τι γράμμα του αλφαβήτου που έτυχε να καταλήγουν σε.

34
00:01:54,280 --> 00:01:57,560
>> Αλλά αυτή η απλή ιδέα ότι εμείς οι άνθρωποι έχουμε λάβει ως δεδομένο για τόσο πολύ καιρό

35
00:01:57,560 --> 00:02:00,670
πραγματικά θα πρέπει να αρχίσουν να έρχονται στο προσκήνιο του μυαλού σας

36
00:02:00,670 --> 00:02:03,900
επειδή τα προβλήματα παίρνουν πολύ πιο περίπλοκη από ό, τι ένα τηλεφωνικό κατάλογο,

37
00:02:03,900 --> 00:02:07,420
τα ίδια απλή, λαμπρό ιδέες είναι αυτό που θα μας επιτρέψει να

38
00:02:07,420 --> 00:02:10,259
να λύσει πολύ πιο πολύπλοκο και πιο ενδιαφέροντα προβλήματα,

39
00:02:10,259 --> 00:02:12,930
μεταξύ των οποίων και μερικά από τα πράγματα που θεωρούμε δεδομένα ήδη αυτές τις μέρες.

40
00:02:12,930 --> 00:02:15,720
Δισεκατομμύρια ιστοσελίδες εκεί έξω, ακόμη και το Google και το Bing και τα παρόμοια

41
00:02:15,720 --> 00:02:17,660
είναι σε θέση να βρείτε τα πράγματα για εμάς, όπως αυτό.

42
00:02:17,660 --> 00:02:22,300
Αυτό δεν συμβαίνει με τη χρήση γραμμικής αναζήτησης, αναζήτηση με όλες τις πιθανές ιστοσελίδες.

43
00:02:22,300 --> 00:02:25,290
Το Facebook είναι σε θέση να σας πω ποιος όλους τους φίλους σας ή είναι φίλοι των φίλων,

44
00:02:25,290 --> 00:02:28,250
και ότι επίσης μπορεί να γίνει φαινομενικά σε μια στιγμή αυτές τις μέρες

45
00:02:28,250 --> 00:02:30,820
ακόμη κι αν έχουν τα εκατομμύρια των χρηστών.

46
00:02:30,820 --> 00:02:34,250
>> Και έτσι πώς θα λύσει πραγματικά τα προβλήματα σε αυτό το επίπεδο, θα μειώσει τελικά

47
00:02:34,250 --> 00:02:37,830
για τις ιδέες που είδαμε στην εβδομάδα 0 και λίγο περισσότερο σήμερα.

48
00:02:37,830 --> 00:02:42,320
Εμείς δεν θα εκτελέσει εκ νέου αυτόν τον αλγόριθμο, αλλά θυμάμαι ότι έκανε επίσης σε αυτή την εβδομάδα 0 άσκηση

49
00:02:42,320 --> 00:02:44,780
όπου όλοι είχαμε σταθεί, να λάβει τον αριθμό 1,

50
00:02:44,780 --> 00:02:48,720
και στη συνέχεια είχαμε όλοι αυτο-μέτρηση με την αντιστοίχιση off, προσθέτοντας τους αριθμούς σας μαζί,

51
00:02:48,720 --> 00:02:51,930
από το μισό της συμμορίας κάθισε σε κάθε επανάληψη.

52
00:02:51,930 --> 00:02:56,750
Έτσι πήγαμε από 500 σπουδαστές σε 250 έως 125 και ούτω καθεξής.

53
00:02:56,750 --> 00:03:00,080
Αλλά, όπως είπαμε, τη Δευτέρα, η ισχυρή ιδέα εκεί

54
00:03:00,080 --> 00:03:02,460
ήταν ότι εάν διπλασίασε το μέγεθος του προβλήματος

55
00:03:02,460 --> 00:03:06,480
και όλα τα παιδιά από το Δικαστήριο ή EC 10 επέστρεψε στην αίθουσα και ενώθηκαν μαζί μας,

56
00:03:06,480 --> 00:03:09,510
καλά, θα μπορούσαμε να μετράνε πιθανώς όλο αυτό το σύνολο της ομάδας

57
00:03:09,510 --> 00:03:13,380
με μόλις 1 πιο μεγάλο επανάληψη του βρόχου, επειδή ίσως θα ήταν μόνο διπλασιάσει το μέγεθος

58
00:03:13,380 --> 00:03:15,630
ή στην περίπτωση του ΕΚ 10 λίγο περισσότερο από το διπλάσιο από το μέγεθος.

59
00:03:15,630 --> 00:03:18,440
Και γι 'αυτό θα πρέπει να περάσουν λίγο περισσότερο χρόνο,

60
00:03:18,440 --> 00:03:22,000
αλλά εμείς δεν θα πρέπει να δαπανήσει 400 ή 700 περισσότερα βήματα.

61
00:03:22,000 --> 00:03:26,550
>> Ακριβώς για να ζωγραφίσει την εικόνα με έναν τρόπο που είναι λίγο λιγότερο αφηρημένα, ας μην έχουν όλοι σηκωθούν.

62
00:03:26,550 --> 00:03:31,100
Αλλά αν όσοι από εσάς επέλεξε να καθίσει στην ορχήστρα σήμερα δεν θα με πείραζε όρθιοι,

63
00:03:31,100 --> 00:03:34,580
Ας δούμε αν μπορούμε να καταλάβουμε ανάμεσά σας που το ψηλότερο άτομο είναι

64
00:03:34,580 --> 00:03:36,730
κάνοντας το ίδιο είδος της συγκριτικής αλγορίθμου.

65
00:03:36,730 --> 00:03:41,830
Έτσι, εάν κάθεστε στην ορχήστρα, ζητώ συγγνώμη, αλλά το βήμα 1, stand up?

66
00:03:41,830 --> 00:03:44,650
βήμα 2, ζευγάρι από κοντά με κανέναν σας,

67
00:03:44,650 --> 00:03:49,360
καταλάβω ποιος είναι πιο ψηλός, και καθίστε κάτω, αν είναι μικρότερες.

68
00:03:49,360 --> 00:03:51,360
Στη συνέχεια επαναλάβετε.

69
00:03:51,360 --> 00:03:56,280
[Φοιτητές μουρμουρίζοντας]

70
00:04:13,450 --> 00:04:15,320
>> Εντάξει.

71
00:04:15,320 --> 00:04:19,010
Εντάξει. Ένα μένει όρθιο. Ποιο είναι το όνομά σου; Andrew >>.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, που είναι το ψηλότερο άτομο στο τμήμα ορχήστρα σήμερα.

73
00:04:21,959 --> 00:04:28,100
>> Συγχαρητήρια. [Χειροκροτήματα και επευφημίες] Εντάξει. Έχετε ένα κάθισμα. Έτσι βρήκαμε Andrew.

74
00:04:28,100 --> 00:04:30,870
Αλλά πόσο καιρό θα με έχουν ληφθεί υπόψη, για παράδειγμα, για να βρείτε Andrew

75
00:04:30,870 --> 00:04:33,740
σε αυτό το τμήμα της ορχήστρας 50 + ή έτσι οι άνθρωποι;

76
00:04:33,740 --> 00:04:36,900
Θα μπορούσα να είχα πάρει μια αρκετά απλή προσέγγιση και να αρχίσει εδώ.

77
00:04:36,900 --> 00:04:39,270
Και έχω 2 άτομα σηκωθούν και μπορώ να συγκρίνω τους ακριβώς,

78
00:04:39,270 --> 00:04:42,120
και στη συνέχεια να λέω σε όποιον είναι ελαφρώς μικρότερη, "Εντάξει, μπορείτε να καθίσετε,"

79
00:04:42,120 --> 00:04:44,380
και Πάω να θυμόμαστε ποιος είναι ο πιο ψηλός πρόσωπο ήταν.

80
00:04:44,380 --> 00:04:49,030
Στη συνέχεια, επαναλαμβάνω, επαναλαμβάνω, επαναλαμβάνω, και θα κολλήσει πάνω στο ψηλότερο πρόσωπο

81
00:04:49,030 --> 00:04:51,920
μέχρι να βρω κάποιον ελαφρώς ψηλότερο από αυτά, σε ποιο σημείο

82
00:04:51,920 --> 00:04:54,950
η ελαφρώς μικρότερη πρόσωπο στη συνέχεια, πρέπει να καθίσουν.

83
00:04:54,950 --> 00:04:57,690
Αλλά σε αυτό το αλγόριθμο σε αυτήν την ενότητα ορχήστρα, αν υπάρχει n από εσάς,

84
00:04:57,690 --> 00:05:00,480
πόσα βήματα είναι ότι ο αλγόριθμος πρόκειται να πάρει; >> [Φοιτητής] N.

85
00:05:00,480 --> 00:05:03,580
>> Είναι πρόκειται να πάρει n, δεξιά, διότι στη χειρότερη περίπτωση, να το πω έτσι,

86
00:05:03,580 --> 00:05:09,090
το ψηλότερο άτομο είναι το τελευταίο άτομο που έχω ακριβώς από τυχαία κακή τύχη.

87
00:05:09,090 --> 00:05:14,260
Έτσι, στη χειρότερη περίπτωση, ο χρόνος εκτέλεσης του αλγορίθμου είναι γραμμική, είναι n,

88
00:05:14,260 --> 00:05:18,070
όπου n είναι ο συνολικός αριθμός των ατόμων στο χώρο, το μέγεθος του προβλήματος.

89
00:05:18,070 --> 00:05:19,600
Τι θα γίνει με αυτόν τον αλγόριθμο;

90
00:05:19,600 --> 00:05:22,080
Το γεγονός ότι όλοι σηκώθηκαν και στη συνέχεια και πάλι το ήμισυ του που κάθισε,

91
00:05:22,080 --> 00:05:23,950
το ήμισυ του που κάθισε, οι μισοί από εσάς κάθισε.

92
00:05:23,950 --> 00:05:26,070
Πόσα βήματα που θα πρέπει να έχουν λάβει αν υπάρχει n σου εδώ;

93
00:05:26,070 --> 00:05:30,200
[Φοιτητής] Ν log n. >> Αυτό θα ήταν χειρότερα. Σύνδεση n.

94
00:05:30,200 --> 00:05:32,930
>> Έτσι log n, ακόμα κι αν δεν είναι αρκετά θυμάστε τι είναι λογάριθμος,

95
00:05:32,930 --> 00:05:38,410
για τώρα, απλά εκτιμώ ότι σχετίζεται με κάποιο τρόπο με αυτό και μείωση κατά το ήμισυ μείωση κατά το ήμισυ και μείωση κατά το ήμισυ.

96
00:05:38,410 --> 00:05:41,000
Δεν χρειάζεται να είναι ένα παράγοντα 2. Θα μπορούσε να είναι ένας παράγοντας του 3.

97
00:05:41,000 --> 00:05:46,560
Αλλά είναι αυτή η επανάληψη της ίδιας φύσεως του παράγοντα, έτσι ώστε το μέγεθος του προβλήματος ξεκινά εδώ

98
00:05:46,560 --> 00:05:49,620
αλλά αμέσως μετά πηγαίνει εδώ, τότε εδώ, τότε εδώ, τότε εδώ.

99
00:05:49,620 --> 00:05:53,580
Δεν παίρνετε μικρές μπουκιές από το πρόβλημα, είστε πραγματικά τεμαχισμό μακριά σε αυτό

100
00:05:53,580 --> 00:05:56,160
με ένα μεγάλο μονομιάς κάθε φορά.

101
00:05:56,160 --> 00:06:00,810
Έτσι, είχαμε 50 άτομα, τότε 25, τότε 12 ½ ή 13 άτομα όρθια,

102
00:06:00,810 --> 00:06:05,370
τότε 6 ½ και ούτω καθεξής μέχρι που τελικά μόνο Andrew έμεινε όρθια.

103
00:06:05,370 --> 00:06:08,710
Έτσι θα πάμε για να καλέσετε αυτό το αρχείο καταγραφής του n, και μπορείτε να απεικονίσει αυτό ως εξής.

104
00:06:08,710 --> 00:06:12,570
Θυμηθείτε αυτή την εικόνα εδώ όπου ένας γραμμικός αλγόριθμος είναι σαν την κόκκινη γραμμή εκεί,

105
00:06:12,570 --> 00:06:17,520
η κίτρινη γραμμή ήταν η καταμέτρηση από 2s αλγόριθμο που χρησιμοποιείται για τη μέτρηση φοιτητές

106
00:06:17,520 --> 00:06:22,300
στο παρελθόν, αλλά σήμερα το Άγιο Δισκοπότηρο πρόκειται να παραμείνει αυτή η πράσινη γραμμή

107
00:06:22,300 --> 00:06:25,470
όπου αν διπλασιαστεί ο αριθμός των ατόμων στην ενότητα ορχήστρα ή απλά είπε,

108
00:06:25,470 --> 00:06:29,170
κόλαση, ας έχει ο καθένας σε ολόκληρο το δωμάτιο σταθεί, δεν είναι μια τέτοια μεγάλη υπόθεση

109
00:06:29,170 --> 00:06:31,560
γιατί σχεδόν διπλασιαστεί πόσοι άνθρωποι είναι εδώ κάτω,

110
00:06:31,560 --> 00:06:33,500
1 περισσότερα επανάληψη, δεν αποτελεί πρόβλημα.

111
00:06:33,500 --> 00:06:36,200
>> Βρήκαμε Andrew ή όποιος συμβαίνει να είναι ψηλότερο από ό, τι Andrew

112
00:06:36,200 --> 00:06:38,770
στο πατάρι ή στο μπαλκόνι.

113
00:06:38,770 --> 00:06:42,140
Έτσι, αυτή την απλή ιδέα ότι πήραμε τόσο αυτονόητα σε ένα τηλεφωνικό κατάλογο,

114
00:06:42,140 --> 00:06:46,170
συνειδητοποιούν ότι υπάρχουν τόσα πολλά διαφορετικά μέρη στα οποία μπορούμε να την εφαρμόσουμε.

115
00:06:46,170 --> 00:06:50,810
Ακριβώς για να χαστούκι κάποια ορολογία - στην πραγματικότητα, παρά ορολογία πρώτη,

116
00:06:50,810 --> 00:06:52,750
επιτρέψτε μου να πάω σε αυτή την εικόνα εδώ.

117
00:06:52,750 --> 00:06:56,970
Αυτή τη στιγμή μιλήσαμε για n και n / 2 και στη συνέχεια να συνδεθείτε του n,

118
00:06:56,970 --> 00:07:00,500
αλλά σίγουρα μπορούμε να καταλήξουμε σε, όπως θα κατά τη διάρκεια του εξαμήνου,

119
00:07:00,500 --> 00:07:05,130
άλλου είδους μαθηματικούς τύπους για να περιγράψει αυτή τη γενική έννοια του χρόνου λειτουργίας.

120
00:07:05,130 --> 00:07:07,580
Αυτά είναι έξω από το πλαίσιο για τώρα, γιατί θα δούμε σε λίγο

121
00:07:07,580 --> 00:07:09,900
αλγόριθμοι ότι αυτά αντιπροσωπεύουν στην πραγματικότητα.

122
00:07:09,900 --> 00:07:17,990
>> Αλλά παρατηρώ εδώ η γραμμική γραμμή n, η ευθεία γραμμή, είναι στην πραγματικότητα πολύ χαμηλή δείχνει αυτή τη στιγμή.

123
00:07:17,990 --> 00:07:22,950
Αυτό είναι το είδος της μια οπτική ψευδαίσθηση το ότι εμείς απλώς να αλλάξει ό, τι ο άξονας x αντιπροσωπεύει

124
00:07:22,950 --> 00:07:26,130
και ο άξονας y, και μπορούμε να κάνουμε μια ευθεία γραμμή σημείο σε οποιαδήποτε κατεύθυνση που θέλουμε.

125
00:07:26,130 --> 00:07:30,350
Αλλά ο λόγος που είναι τόσο φαινομενικά επίπεδη τώρα

126
00:07:30,350 --> 00:07:35,690
Είναι επειδή χρειαζόμασταν για να κάνει χώρο για αυτό το διάγραμμα για πολύ πιο αργή φορές τρέξιμο.

127
00:07:35,690 --> 00:07:39,030
Προς το παρόν, γνωρίζουμε ότι υπάρχουν ορισμένες πολύ κακές αλγόριθμοι στη ζωή,

128
00:07:39,030 --> 00:07:43,790
μερικά από τα οποία δεν λαμβάνουν μέτρα για ν ή, ακόμα καλύτερα, συνδεθείτε n βήματα, αλλά περισσότερο.

129
00:07:43,790 --> 00:07:48,820
Έτσι, πάνω από τη γραμμή n εδώ στο κάτω μέρος υπάρχει ειδοποίηση n log n φορές,

130
00:07:48,820 --> 00:07:51,410
και θα δούμε τι σημαίνει αυτό πριν από καιρό.

131
00:07:51,410 --> 00:07:56,010
Πάνω απ 'αυτό είναι ν τετράγωνο, και δεν έχουμε δει κανένα n τετράγωνο αλγόριθμοι ακόμα, αλλά είμαστε έτοιμοι να.

132
00:07:56,010 --> 00:07:57,660
Και αυτό φαίνεται πολύ άσχημα.

133
00:07:57,660 --> 00:08:01,610
Υπάρχει 2 του ν, κάτι εκθετική, που αισθάνεται ακόμα χειρότερα.

134
00:08:01,610 --> 00:08:05,760
Και όμως, περιέργως, τότε υπάρχει n κύβους, τα οποία, αν είστε το είδος των σκέφτεται το μέλλον,

135
00:08:05,760 --> 00:08:10,000
αν το είδος του κάνετε τα μαθηματικά, 2 στην n πραγματικά γίνεται πολύ ίσια,

136
00:08:10,000 --> 00:08:15,930
πολύ υψηλότερο από ό, τι μέχρι ν κύβο αν δείτε τους άξονες αρκετά προς τα έξω.

137
00:08:15,930 --> 00:08:19,890
Έτσι, παρατηρούμε τώρα Οι άξονες αυτοί είναι αυθαίρετα 2 έως 10 στον άξονα x.

138
00:08:19,890 --> 00:08:21,770
>> Και τι σημαίνει αυτό;

139
00:08:21,770 --> 00:08:23,890
That σημαίνει 2 άτομα και 10 άτομα σε ένα δωμάτιο.

140
00:08:23,890 --> 00:08:27,200
Αυτό είναι το μόνο μέσο x: το μέγεθος του προβλήματος, όποια και αν είναι το πλαίσιο.

141
00:08:27,200 --> 00:08:30,420
Και ένα κατακόρυφο άξονα τώρα είναι ο αριθμός των δευτερολέπτων ή τον αριθμό των βημάτων -

142
00:08:30,420 --> 00:08:31,840
κάποια μονάδα του χρόνου.

143
00:08:31,840 --> 00:08:34,740
Να σημειωθεί όμως ότι είναι 0 - 60 και 0 έως το 10.

144
00:08:34,740 --> 00:08:38,549
Αλλά αν το είδος του ζουμ έξω, όπως θα μπορούσε στο Excel ή κάποιο λογισμικό χαρτογράφησης,

145
00:08:38,549 --> 00:08:43,370
και πάμε μέχρι 200.000, παρατηρήσετε ότι κάτι σαν 2 του ν

146
00:08:43,370 --> 00:08:47,520
πρόκειται να συντρίψει εντελώς τις τρέχουσες περιόδους n τετράγωνο,

147
00:08:47,520 --> 00:08:50,960
n κύβους, n log n - ό, τι έχουμε μιλήσει μέχρι στιγμής.

148
00:08:50,960 --> 00:08:54,190
Και όμως, η σύλληψη είναι όταν αρχίσουμε να μιλάμε για πράγματα όπως το Facebook

149
00:08:54,190 --> 00:08:57,150
όπου πολλοί, πολλοί, πολλοί άνθρωποι συνδέονται όλα μεταξύ τους,

150
00:08:57,150 --> 00:09:00,650
έχετε n άνθρωποι, καθένας από τους οποίους θα μπορούσε να έχει όσο το n φίλους

151
00:09:00,650 --> 00:09:02,860
αν ο καθένας είναι είδος του φίλος-φίλος του κόσμου,

152
00:09:02,860 --> 00:09:08,100
καλά, αυτό είναι n n φορές ήδη, έτσι ώστε να είναι δυνατή n τετράγωνο φιλίες,

153
00:09:08,100 --> 00:09:10,950
τουλάχιστον σε 1 κατεύθυνση, n τετράγωνο πιθανές φιλίες.

154
00:09:10,950 --> 00:09:15,330
Έτσι, αυτό σημαίνει ότι ήδη ψάχνουν κοινωνικό γράφημα του Facebook, να το πω έτσι,

155
00:09:15,330 --> 00:09:18,090
μπορεί να αρχίσει να εκφράζεται σε αυτά τα είδη των τύπων.

156
00:09:18,090 --> 00:09:19,820
>> Θα επανέλθουμε και να κάνει αυτό πολύ πιο συγκεκριμένη,

157
00:09:19,820 --> 00:09:23,280
αλλά προς το παρόν, ο στόχος για τις επόμενες πολλές εβδομάδες

158
00:09:23,280 --> 00:09:27,170
πρόκειται να είναι βέβαιο ότι δεν θα πάει για την εφαρμογή αλγορίθμων ή κωδικό

159
00:09:27,170 --> 00:09:29,870
που καταλήγουν λήψη όσο χρόνο κάτι τέτοιο.

160
00:09:29,870 --> 00:09:33,110
Αλλά το συναρπαστικό πράγμα σχετικά με την επιστήμη υπολογιστών, αν συνεχίσει σε αυτό το πεδίο

161
00:09:33,110 --> 00:09:38,320
λαμβάνοντας μαθήματα όπως CS121, CS124, δύο από τα οποία είναι θεωρητικά μαθήματα,

162
00:09:38,320 --> 00:09:41,300
είναι ότι υπάρχουν πράγματι κάποια προβλήματα που υπάρχουν σε αυτόν τον κόσμο

163
00:09:41,300 --> 00:09:45,710
ότι ουσιαστικά, όσο γνωρίζουμε, δεν μπορεί να λυθεί οποιαδήποτε γρηγορότερα

164
00:09:45,710 --> 00:09:48,880
από ό, τι το χειρότερο από αυτά τα γραφήματα δείχνουν στην πραγματικότητα.

165
00:09:48,880 --> 00:09:53,660
Έτσι, υπάρχει μια πολύ ανοικτά προβλήματα σε αυτόν τον κόσμο να κάνει πολύ καλύτερα από ό, τι οι άνθρωποι έχουν μέχρι στιγμής.

166
00:09:53,660 --> 00:09:56,130
>> Ας αρχίσουμε λοιπόν με αυτό το παράδειγμα.

167
00:09:56,130 --> 00:09:59,650
Είδαμε τον αγώνα Sean με αυτή την κάμερα, πολύ αδέξια στο βίντεο.

168
00:09:59,650 --> 00:10:05,270
Αλλά η πραγματικότητα ήταν όταν ο Sean ήταν επιφορτισμένη με την εύρεση σε έναν πίνακα όπως αυτή, ο αριθμός 7,

169
00:10:05,270 --> 00:10:10,300
Υπενθυμίζω ότι είπα ότι, "Δεν υπάρχει κάπου πίσω από αυτά τα κομμάτια χαρτιού ή λευκό πόρτες

170
00:10:10,300 --> 00:10:12,570
"Ο αριθμός 7. Sean, θεωρούν ότι είναι για εμάς."

171
00:10:12,570 --> 00:10:14,200
Και ήταν υπέροχα δύσκολο να παρακολουθήσουν

172
00:10:14,200 --> 00:10:15,790
γιατί ήταν πραγματικά αγωνίζονται με αυτό το πρόβλημα.

173
00:10:15,790 --> 00:10:19,720
Αλλά η πραγματικότητα ήταν ο Sean έκανε καθώς ο καθένας στο δωμάτιο θα μπορούσε να έχει γίνει.

174
00:10:19,720 --> 00:10:21,890
Πήρε λίγο περισσότερο από ό, τι ένα τυπικό άτομο μπορεί να έχει,

175
00:10:21,890 --> 00:10:24,760
αλλά υπέθεσε ότι υπήρχε κάποιο τέχνασμα σε αυτό το πρόβλημα,

176
00:10:24,760 --> 00:10:26,590
υπέθεσε ότι κάτι έλειπε.

177
00:10:26,590 --> 00:10:29,320
Και δεν βοηθά ότι εκατοντάδες μάτια καταπάνω του.

178
00:10:29,320 --> 00:10:34,250
>> Αλλά η πραγματικότητα ήταν αν η είσοδος στο πρόβλημα είναι ένα μάτσο τυχαίων αριθμών

179
00:10:34,250 --> 00:10:37,120
και σας ζητείται να βρείτε 1 τέτοιο αριθμό,

180
00:10:37,120 --> 00:10:39,770
το καλύτερο που μπορείτε να κάνετε είναι γραμμική αναζήτηση.

181
00:10:39,770 --> 00:10:44,060
Ξεκινήστε από τα αριστερά, μετακινήστε προς τα δεξιά, ή να ξεκινήσει στα δεξιά, μετακινηθείτε προς τα αριστερά.

182
00:10:44,060 --> 00:10:48,300
Αναδρομικά, θα μπορούσαμε να σκεφτούμε, "Sean, γιατί δεν μπορείτε απλά να αρχίσετε από το άλλο άκρο;"

183
00:10:48,300 --> 00:10:52,120
Λοιπόν, 7 θα μπορούσε να έχει εξίσου εύκολα εδώ τυχαία,

184
00:10:52,120 --> 00:10:54,980
αλλά έβαλα επίτηδες εκεί γιατί σκέφτηκα ότι δεν πρόκειται να ξεκινήσει στο τέλος.

185
00:10:54,980 --> 00:10:59,320
Γι 'αυτό το είδος των χειριστεί την κατάσταση, αλλά με τυχαία πιθανότητα 7 θα μπορούσε να ήταν οπουδήποτε.

186
00:10:59,320 --> 00:11:02,380
Έτσι, ξεκινώντας από το δεξί άκρο θα μπορούσε να ήταν καλύτερη, στη συνέχεια,

187
00:11:02,380 --> 00:11:04,320
αλλά τι γίνεται αν η επόμενη χρονιά θα μεταφέρετε 7 αλλού;

188
00:11:04,320 --> 00:11:06,830
Αυτό δεν είναι μια εντελώς νέα λύση στο πρόβλημα -

189
00:11:06,830 --> 00:11:10,520
ξεκινώντας από την 1 άκρο ή το άλλο - όταν σας δίνεται καμία άλλη υποθέσεις.

190
00:11:10,520 --> 00:11:13,620
Έτσι, Sean άρχισε να ψάχνει μέσα από τους αριθμούς και είπε, "5. Αυτό δεν είναι εδώ."

191
00:11:13,620 --> 00:11:17,280
Στη συνέχεια πήγε εδώ και είδα 19, στη συνέχεια, έκανε μια παύση για περίπου 20 δευτερόλεπτα,

192
00:11:17,280 --> 00:11:22,330
τότε άνοιξε αυτό για 13, και στη συνέχεια έγινε φανερό

193
00:11:22,330 --> 00:11:24,270
ότι δεν φαίνεται να είναι ένα πρότυπο εδώ.

194
00:11:24,270 --> 00:11:28,090
Δεν ήταν 1, 2, 3, 4 ή τα παρόμοια. Υπήρχαν κενά στους αριθμούς, που δεν βοηθούν.

195
00:11:28,090 --> 00:11:32,320
Και επίσης, το γεγονός ότι χρησιμοποίησα αυτά τα φτηνά κομμάτια του χαρτί για να καλύψει τους αριθμούς

196
00:11:32,320 --> 00:11:35,270
Είναι πράγματι σκόπιμη, επειδή αν αφαιρεθούν όλα αυτά τα κομμάτια χαρτιού,

197
00:11:35,270 --> 00:11:38,760
οι περισσότεροι από εμάς, Sean περιλαμβάνονται, κατά πάσα πιθανότητα θα έχουν μια ματιά είδος μακροσκοπικά

198
00:11:38,760 --> 00:11:43,410
στο μαυροπίνακα και είπε: «Ω, 7 είναι προφανώς εκεί." Το κάναμε αμέσως.

199
00:11:43,410 --> 00:11:46,460
>> Και αυτό μπορεί να είναι ο τρόπος που ο ανθρώπινος εγκέφαλος λειτουργεί σε κάποιο βαθμό,

200
00:11:46,460 --> 00:11:50,730
αλλά στην πραγματικότητα, τα μάτια ή το μυαλό του ήταν πιθανώς αποκορύφωση τους αριθμούς από τα δεξιά προς τα αριστερά,

201
00:11:50,730 --> 00:11:55,190
αριστερά προς τα δεξιά, μέσα στο έξω - κάτι συνέβαινε φυσιολογικά

202
00:11:55,190 --> 00:11:57,640
όπως ότι αισθάνθηκε σαν να συνέβαινε αμέσως,

203
00:11:57,640 --> 00:12:01,360
αλλά οι πιθανότητες είναι ακόμα και στο εσωτερικό της υπήρχε κάποια μεθοδολογία για την εύρεση 7.

204
00:12:01,360 --> 00:12:05,160
Και πράγματι, τώρα που μιλάμε για πίνακες και δομές δεδομένων

205
00:12:05,160 --> 00:12:08,780
και μέσα από τη μνήμη ενός υπολογιστή, το μόνο πράγμα που εμείς οι άνθρωποι μπορούμε να κάνουμε

206
00:12:08,780 --> 00:12:13,070
είναι να δούμε σε επιμέρους θέσεις μνήμης 1 κάθε φορά.

207
00:12:13,070 --> 00:12:16,600
>> Έτσι, κάθε άλλη θέση θα μπορούσε κάλλιστα να καλυφθούν με κάποιο κομμάτι χαρτί

208
00:12:16,600 --> 00:12:21,170
επειδή δεν μπορούμε να το δούμε έτσι κι αλλιώς. Μπορούμε να κάνουμε μόνο 1 πράγμα τη φορά.

209
00:12:21,170 --> 00:12:25,030
Έτσι, στην περίπτωση αυτή, στην περίπτωση του Sean, πήγαμε εδώ και στη συνέχεια πήγαμε εδώ

210
00:12:25,030 --> 00:12:31,040
και στη συνέχεια πήγαμε εδώ, εδώ, εδώ, εδώ, πήρε έξυπνος από το τέλος

211
00:12:31,040 --> 00:12:34,450
και ακριβώς το είδος της παραλειφθεί αυτό το ένα αυθαίρετα και βρέθηκαν 7 εκεί.

212
00:12:34,450 --> 00:12:37,470
Αυτός δεν ήταν ιδιαίτερα ξεχωριστή. Είναι πάρα πολύ ήταν έξω από την τάξη.

213
00:12:37,470 --> 00:12:39,530
Αλλά τελικά βρέθηκε 7.

214
00:12:39,530 --> 00:12:45,360
Αλλά τώρα το πακέτο είναι πραγματικά ότι το καλύτερο που μπορείτε να κάνετε όταν δοθεί καμία πληροφορία

215
00:12:45,360 --> 00:12:50,400
εκτός από τυχαία ταξινόμηση αριθμών είναι να ξεκινήσετε από την αριστερά ή να ξεκινήσετε από τα δεξιά.

216
00:12:50,400 --> 00:12:54,950
Ή καλό, μπορείτε να ανοίξει τυχαία πόρτες, αλλά ακόμα και τότε τι σημαίνει να είναι τυχαία;

217
00:12:54,950 --> 00:12:57,220
Λοιπόν, θα είχαμε να επισημοποιήσει με κάποιον τρόπο τι σημαίνει να ξεκινήσει εδώ,

218
00:12:57,220 --> 00:13:01,150
τότε πάμε εδώ, τότε πηγαίνετε εδώ. Sean έκανε μεγάλη, και ήταν απλά διασκεδαστικό να βλέπει κανείς.

219
00:13:01,150 --> 00:13:06,340
Τι θα συμβεί αν αντί να αλλάξουμε το πρόβλημα λίγο και να εμφανιστεί Sean της φετινής χρονιάς, αν θα το κάνει;

220
00:13:06,340 --> 00:13:09,460
Θα μπορούσε κάποιος να είναι άνετα να ανεβαίνει στη σκηνή και την επίλυση μια ελαφρώς διαφορετική πρόβλημα

221
00:13:09,460 --> 00:13:12,330
και εμφανίζονται στην κάμερα;

222
00:13:12,330 --> 00:13:15,720
>> Ας πάμε πέρα ​​από την ορχήστρα, επειδή έχετε παιδιά έχουν αρκετά συμμετέχουν ήδη σήμερα.

223
00:13:15,720 --> 00:13:21,430
Τι θα λέγατε σε ροζ χρώμα, το καπέλο; Έλα κάτω. Ποιο είναι το όνομά σου; >> Αλεξ. >> Αλεξ. Εντάξει.

224
00:13:21,430 --> 00:13:24,580
Έτσι ο Άλεξ θα είναι Sean του τρέχοντος έτους και θα εμφανιστεί στα επόμενα χρόνια

225
00:13:24,580 --> 00:13:27,770
αξίας CS50 διαλέξεις.

226
00:13:27,770 --> 00:13:30,340
Alex, ωραία να σας γνωρίσουμε. >> Χαίρω πολύ.

227
00:13:30,340 --> 00:13:33,470
Η πρόκληση στο χέρι για σας είναι ότι έχετε μια λίγο πιο εύκολη

228
00:13:33,470 --> 00:13:38,950
υπό την έννοια ότι σας λέω τα ίδια νούμερα είναι εδώ, αλλά τώρα είναι ταξινομημένο.

229
00:13:38,950 --> 00:13:41,800
Έτσι, τώρα ο στόχος σας είναι να βρείτε τον αριθμό 7.

230
00:13:41,800 --> 00:13:45,370
Και στην πραγματικότητα, πρέπει να κάνουμε πραγματικά αυτό - Μπορείτε πλέον το είδος της εξαπάτησης, όπως ένας υπολογιστής δεν θα ήταν,

231
00:13:45,370 --> 00:13:47,990
εξετάζοντας τι οι αριθμοί ήταν μια στιγμή πριν.

232
00:13:47,990 --> 00:13:50,360
Με την κιμωλία αυτό είναι στην πραγματικότητα δεν πρόκειται να βοηθήσει τόσο πολύ,

233
00:13:50,360 --> 00:13:52,810
αλλά ας προσποιηθούμε ότι δεν ξέρετε ποια είναι η αρχική σειρά είναι.

234
00:13:52,810 --> 00:13:56,600
Το μόνο που ξέρω είναι ότι τώρα έχετε μια σειρά από αριθμούς ταξινόμηση

235
00:13:56,600 --> 00:14:00,360
που θα μπορούσαν να έχουν κενά μεταξύ τους, και ο στόχος σας είναι να βρείτε τον αριθμό 7.

236
00:14:00,360 --> 00:14:05,080
Πώς θα σας, ένα λογικό άνθρωπο, πηγαίνετε για την εύρεση του αριθμού 7;

237
00:14:05,080 --> 00:14:07,770
>> Μετάβαση από χαμηλό σε υψηλό; Εντάξει >>. Μετάβαση χαμηλή προς υψηλή.

238
00:14:07,770 --> 00:14:10,990
Και μην τους κόψετε. Ας σηκώσει τους ακριβώς επάνω έτσι μπορούμε να τους ξαναχρησιμοποιήσετε.

239
00:14:10,990 --> 00:14:14,730
Εντάξει, έτσι 1. Περιμένετε. Πριν συνεχίσω, αυτό ήταν 1, σαφώς λάθος.

240
00:14:14,730 --> 00:14:17,270
Έτσι, τι περνούσε από το μυαλό σας το επόμενο βήμα; Ποια είναι η επόμενη κίνησή σας;

241
00:14:17,270 --> 00:14:23,250
Το επόμενο. Εντάξει >>. Το επόμενο. Καλή. 3, έτσι εσφαλμένη. Ποια είναι η επόμενη κίνησή σας;

242
00:14:23,250 --> 00:14:27,670
Κρατήστε σε εξέλιξη. >> Εντάξει. Κρατήστε σε εξέλιξη. 5.

243
00:14:27,670 --> 00:14:31,110
Έτσι να συνεχίσουμε να προχωράμε, και επιτρέψτε μου να σας δώσουν αυτό για τις επόμενες γενιές.

244
00:14:31,110 --> 00:14:35,720
7. Εξαιρετική >>. Πολύ καλό. Βρέθηκε ο αριθμός 7. [Χειροκροτήματα]

245
00:14:35,720 --> 00:14:39,720
Έτσι, αυτό ήταν καλό, αλλά Sean βρέθηκαν πολύ τον αριθμό 7.

246
00:14:39,720 --> 00:14:44,490
Και υποστηρίζουν ότι δεν έχουν αξιοποιηθεί πραγματικά αυτή την επιπλέον πληροφορία,

247
00:14:44,490 --> 00:14:47,780
το οποίο είναι ταξινομημένο ότι αυτοί οι αριθμοί.

248
00:14:47,780 --> 00:14:51,520
Έτσι, μπορούμε να κάνουμε καλύτερα; Οποιεσδήποτε προτάσεις εδώ; Ναι, στο πίσω μέρος.

249
00:14:51,520 --> 00:14:54,710
[Φοιτητής] Δυαδική αναζήτηση. >> Δεν έχω καμία ιδέα για το τι είναι η δυαδική αναζήτηση.

250
00:14:54,710 --> 00:14:58,030
>> [Φοιτητής] Έναρξη στη μέση. Ξεκινήστε >> στη μέση. Εντάξει. Ας δούμε αν μπορούμε να φτάσουμε εκεί.

251
00:14:58,030 --> 00:15:02,580
Έτσι, εάν αντί να λένε ξεκίνημα από τη μέση, να προχωρήσει και να ανοίξει την πόρτα μέση.

252
00:15:02,580 --> 00:15:04,580
Υπάρχει 8 από αυτούς, έτσι θα πάμε να πρέπει να επιλέξει αυθαίρετα το ένα

253
00:15:04,580 --> 00:15:09,800
ελαφρώς προς τα αριστερά ή προς τα δεξιά. Εντάξει. 7! [Χειροκροτήματα] Πολύ ωραία.

254
00:15:09,800 --> 00:15:11,410
Εντάξει, αλλά όπου είχαν πάμε με αυτό;

255
00:15:11,410 --> 00:15:14,990
Ας υποθέσουμε απλά για να σπάσει την ισοπαλία που είχε αρχίσει εδώ

256
00:15:14,990 --> 00:15:16,670
διότι αυτό θα μπορούσε να έχει εξίσου συνέβησαν, καθώς και.

257
00:15:16,670 --> 00:15:19,540
Απλά έτυχε να γνωρίζουν ότι το 7 ήταν εκεί. Έτσι, αυτό είναι 13.

258
00:15:19,540 --> 00:15:21,980
Έτσι, αν είναι ταξινομημένο και εμείς μόλις ξεκίνησε στη μέση,

259
00:15:21,980 --> 00:15:24,600
ποια θα ήταν η καλύτερη επόμενη κίνηση ήταν;

260
00:15:24,600 --> 00:15:27,740
Πηγαίνετε το αριστερό. Και έτσι έρχεται εδώ το παράδειγμα βιβλίο τηλέφωνο και πάλι.

261
00:15:27,740 --> 00:15:30,130
Αν 13 είναι εδώ και ξέρουμε ότι ο κατάλογος είναι ταξινομημένο,

262
00:15:30,130 --> 00:15:33,900
τότε όλα αυτά τα κομμάτια χαρτιού χωρίς ενδιαφέρον για μας τώρα

263
00:15:33,900 --> 00:15:37,400
επειδή γνωρίζουμε ήδη ότι το 7 θα πρέπει να είναι προς τα αριστερά

264
00:15:37,400 --> 00:15:39,510
αν οι αριθμοί αυτοί ταξινόμηση και βρήκαμε 13.

265
00:15:39,510 --> 00:15:42,500
>> Λοιπόν, τι είναι η επόμενη κίνησή σας εδώ; >> Μετάβαση προς τα αριστερά. >> Εντάξει, καλά.

266
00:15:42,500 --> 00:15:45,080
Έτσι πηγαίνετε προς τα αριστερά, και - περιμένετε, hey, hey, hey. Αυτό είναι εξαπάτηση.

267
00:15:47,140 --> 00:15:51,350
Έτσι βρέθηκαν 7, αλλά ό, τι ήταν ο αλγόριθμος που μόλις εφαρμοστεί;

268
00:15:51,350 --> 00:15:56,450
Ξεκινήστε στη μέση. Καλή >>. Έτσι ποια είναι η λογική επέκταση της ίδιας ιδέας;

269
00:15:56,450 --> 00:15:58,970
Ω, μόνο για αυτά. Ακριβώς >>. >> Γι 'αυτό και αρχίζουν εδώ. Καλή >>.

270
00:15:58,970 --> 00:16:02,020
Μέχρι τώρα πήγαμε ελαφρώς προς τα αριστερά και πάλι. Είναι 3.

271
00:16:02,020 --> 00:16:05,310
Αλλά το ενδιαφέρον πακέτο είναι τώρα ποια εσείς δεν πρέπει να νοιάζονται για;

272
00:16:05,310 --> 00:16:08,040
Αυτά τα 2. Αυτές >> 2. Έτσι τώρα αυτό μπορεί κανείς να πάει μακριά, αυτό μπορεί κανείς να πάει μακριά.

273
00:16:08,040 --> 00:16:12,330
Τώρα το πρόβλημα που τότε ήταν 8 ήταν 4 μέγεθος είναι τώρα το μέγεθος 2.

274
00:16:12,330 --> 00:16:16,430
Παίρνουμε πολύ κοντά. Και πάλι, πηγαίνετε στο κέντρο αυτών των 2 στοιχείων.

275
00:16:16,430 --> 00:16:20,430
>> Εντάξει. Έτσι είναι το είδος του ατυχές το γεγονός ότι τώρα είμαστε πάντα θα μείνει γιατί είμαστε στρογγυλοποίηση προς τα κάτω.

276
00:16:20,430 --> 00:16:25,150
Αλλά αυτό είναι εντάξει, επειδή τώρα έχουμε ρίξει μακριά αυτό και ό, τι άλλο, αφήνοντας μας με μόνο 7.

277
00:16:25,150 --> 00:16:30,490
Ας δώσουμε ένα χειροκρότημα. Βρήκαμε 7 πάλι. [Χειροκροτήματα] Εντάξει. Σίγουρα.

278
00:16:30,490 --> 00:16:32,220
Περίμενε για περισσότερο μόλις 1 δευτερόλεπτο.

279
00:16:32,220 --> 00:16:36,630
Ακόμη και αν η επόμενη διαδικασία είδος της πήρε λίγο περισσότερο από ό, τι θεωρήσαμε ότι θα ήταν,

280
00:16:36,630 --> 00:16:40,150
Ειλικρινά, πρώτα το ένστικτό σας ήταν ο καλύτερος, έτσι δεν είναι; Βρέθηκαν 7 ακαριαία.

281
00:16:40,150 --> 00:16:46,740
Αλλά θα είχαμε βρεθεί 7 πιο γρήγορα, δεν έχει σημασία τι, σε αυτό το παράδειγμα σε σχέση με αυτό το ένα

282
00:16:46,740 --> 00:16:50,100
γιατί αν οι αριθμοί όλες ταξινόμηση, σαν τις σελίδες ενός βιβλίου τηλέφωνο,

283
00:16:50,100 --> 00:16:54,580
μπορείτε να κόψετε το ήμισυ των πράγματι το πρόβλημα ξανά και ξανά και ξανά.

284
00:16:54,580 --> 00:16:56,740
Και δεν είναι τόσο εύκολο να δει αυτό με μόλις 8 αριθμούς

285
00:16:56,740 --> 00:17:00,100
σε αντίθεση με το τηλεφωνικό 1.000-σελίδα, όπου θα δείτε πραγματικά οπτικά,

286
00:17:00,100 --> 00:17:03,120
αλλά σε αυτή την περίπτωση, όταν ο Sean εδώ έψαχνε για 7,

287
00:17:03,120 --> 00:17:06,020
πόσα βήματα στη χειρότερη περίπτωση θα ήταν να τον πάρει; >> [Φοιτητής] 7.

288
00:17:06,020 --> 00:17:11,670
7 στη χειρότερη περίπτωση. Λοιπόν, στη χειρότερη περίπτωση δεν 7 εάν υπάρχει 8 θυρών εδώ.

289
00:17:11,670 --> 00:17:13,440
Θα έχουν τον 8 βήματα.

290
00:17:13,440 --> 00:17:18,170
>> Έτσι, αν υπάρχει n πόρτες, θα μπορούσε να ληφθεί Sean ένα-δύο χρόνια πριν από n βήματα.

291
00:17:18,170 --> 00:17:21,520
Τώρα, στην περίπτωσή σας, ο Άλεξ, δεδομένου ότι είναι ταξινομημένο αυτοί οι αριθμοί -

292
00:17:21,520 --> 00:17:25,130
και μπορούμε να το είδος του να συναγάγει από αυτό που ήμασταν μέχρι τώρα σε αυτή την ιστορία -

293
00:17:25,130 --> 00:17:28,300
τι είναι ο χρόνος εκτέλεσης του πιο ευφυή αλγόριθμο Άλεξ

294
00:17:28,300 --> 00:17:30,770
της ξεκινώντας από τη μέση και στη συνέχεια επανάληψη;

295
00:17:30,770 --> 00:17:36,490
[Φοιτητής] 3. >> Γι 'αυτό πρόκειται να είναι 3, περίπου, αν πάτε 8 - 4 2 έως 1.

296
00:17:36,490 --> 00:17:40,660
Έτσι, 3 βήματα ή, γενικότερα, αυτό είναι log n και πάλι.

297
00:17:40,660 --> 00:17:43,380
Κάθε φορά που είστε και μείωση κατά το ήμισυ μείωση κατά το ήμισυ και μείωση κατά το ήμισυ και μείωση κατά το ήμισυ,

298
00:17:43,380 --> 00:17:45,290
αυτό είναι μια έκφραση αυτής της ιδέας του log n.

299
00:17:45,290 --> 00:17:48,140
Και έτσι αυτό θα σας έχουν πάρει μόνο 3 βήματα, και μάλιστα το έκανε

300
00:17:48,140 --> 00:17:50,890
μόλις ανοίξαμε τις πόρτες και μείωση κατά το ήμισυ μείωση κατά το ήμισυ,

301
00:17:50,890 --> 00:17:53,770
λαμβάνοντας υπόψη ότι αυτό θα ληφθεί Sean περίπου 7 ή 8 βήματα.

302
00:17:53,770 --> 00:17:56,330
Σας ευχαριστώ λοιπόν για να είναι μαζί μας φέτος. >> Σας ευχαριστούμε. Ωραία συνάντηση σας.

303
00:17:56,330 --> 00:18:00,170
Σας ευχαριστούμε για την Άλεξ. Ομοίως >>. [Χειροκροτήματα]

304
00:18:00,170 --> 00:18:02,150
>> Ποια είναι τότε η πραγματική επίπτωση της αυτό;

305
00:18:02,150 --> 00:18:06,050
Τώρα φανταστείτε ότι δεν είναι 8 θυρών, η οποία, ειλικρινά, όλοι μας θα μπορούσε να βρει κάτι

306
00:18:06,050 --> 00:18:10,430
8 θυρών πίσω αρκετά γρήγορα μόλις με σκίσιμο τα κομμάτια χαρτιού και πηγαίνοντας με τα ένστικτά μας.

307
00:18:10,430 --> 00:18:14,430
Τι γίνεται όμως αν αυτό είναι ένα εκατομμύριο πόρτες; Τι και αν είναι 4 δισεκατομμύρια πόρτες;

308
00:18:14,430 --> 00:18:19,630
Στην περίπτωση των 4 δισ. πόρτες, είστε πραγματικά πρόκειται να θέλουν να πάνε με τον αλγόριθμο του Alex,

309
00:18:19,630 --> 00:18:23,150
δυαδική αναζήτηση, όπως θα αρχίσουμε καλώντας το ή διαίρει και βασίλευε, γενικότερα,

310
00:18:23,150 --> 00:18:25,220
όπου μπορείτε κρατήσει μείωση κατά το ήμισυ και μείωση κατά το ήμισυ του προβλήματος,

311
00:18:25,220 --> 00:18:30,510
γιατί αν έχετε 4 δισεκατομμύρια πόρτες, πόσες φορές μπορείτε να τεμαχίσει 4 δισ. ημίχρονο;

312
00:18:30,510 --> 00:18:33,870
[Φοιτητής] 32. >> Είναι πραγματικά 32. Μπορείτε να εργαστείτε από αυτό σε ένα κομμάτι χαρτί ή στο κεφάλι σας.

313
00:18:33,870 --> 00:18:38,490
Πηγαίνεις 4 δισεκατομμύρια έως 2 δισεκατομμύρια to 1 δισ. ευρώ για μισό δισεκατομμύριο, σε 250 εκατ. ευρώ, τελεία, τελεία, τελεία.

314
00:18:38,490 --> 00:18:41,620
Και αν το κάνετε το math, εσείς πρόκειται να πάρει πραγματικά 32,

315
00:18:41,620 --> 00:18:44,950
και αυτό αφορά στην πραγματικότητα την επιστήμη των υπολογιστών, γιατί συνήθως μετράνε σε δυνάμεις του 2.

316
00:18:44,950 --> 00:18:47,600
2 έως τις 32 τυχαίνει να είναι 4 δις ευρώ.

317
00:18:47,600 --> 00:18:51,440
Έτσι, υπάρχει ένα πολύ ενδιαφέρον για αυτού του είδους τις δυνάμεις του 2 στην επιστήμη των υπολογιστών.

318
00:18:51,440 --> 00:18:55,120
>> Αλλά τι περίπου 8 δισεκατομμύρια; Πόσα βήματα είναι ότι θα πρέπει να ληφθούν εάν υπάρχουν 8 δισεκατομμύρια πόρτες;

319
00:18:55,120 --> 00:19:00,350
[Φοιτητής] 33. Έτσι >> 33. Τι θα συμβεί αν δεν υπάρχει 16 δισεκατομμύρια πόρτες; Πόσα βήματα είναι ότι πρόκειται να πάρει;

320
00:19:00,350 --> 00:19:05,020
[Φοιτητής] 34. >> 34. Θα μπορούσαμε να συνεχίσουμε το είδος αυτής της αηδίας. Αλλά αυτό είναι ένα ισχυρό πράγμα.

321
00:19:05,020 --> 00:19:09,430
Μπορείτε να εισαγάγει δισεκατομμύρια περισσότερες εισόδους στο πρόβλημά σας, αλλά δεν είναι μεγάλη υπόθεση,

322
00:19:09,430 --> 00:19:14,140
παίρνετε μόνο 1 επιπλέον δάγκωμα από αυτό και έτσι μας δίνει κάτι σαν δυαδική αναζήτηση

323
00:19:14,140 --> 00:19:15,920
ή διαίρει και βασίλευε, γενικότερα.

324
00:19:15,920 --> 00:19:17,990
Αλλά είμαι το είδος της εξαπάτησης εδώ, έτσι δεν είναι;

325
00:19:17,990 --> 00:19:22,410
Στην περίπτωση του αλγορίθμου του Alex, είχε ένα πλεονέκτημα σε σχέση με τον Sean.

326
00:19:22,410 --> 00:19:27,780
Ήξερε ότι αυτοί οι αριθμοί ήταν ταξινομημένο, αλλά ο Άλεξ δεν είχε να ταξινομήσετε τον εαυτό τους.

327
00:19:27,780 --> 00:19:30,520
I εκ των προτέρων ήρθε στο μαυροπίνακα και το είδος των φρόντισε

328
00:19:30,520 --> 00:19:33,670
ότι έβγαλα όλα έξω σε ταξινομημένη σειρά, τότε εγώ τους καλυμμένο με χαρτί.

329
00:19:33,670 --> 00:19:35,850
Αλλά πόση δουλειά ήταν ότι μου πάρει;

330
00:19:35,850 --> 00:19:40,110
Αν είχαμε ξεκίνησε με αυτούς τους αριθμούς σε κάποια φαινομενικά τυχαία σειρά -

331
00:19:40,110 --> 00:19:43,320
σε αυτή την περίπτωση αυτές οι απλούστερες αριθμούς, 1 έως 8 εδώ -

332
00:19:43,320 --> 00:19:46,090
πώς θα πάτε για την ταξινόμηση αυτών των αξιών;

333
00:19:46,090 --> 00:19:52,530
Αν ήταν ένας άνθρωπος που το έργο αυτό, τι είδους διαισθητική προσέγγιση θα πάρετε

334
00:19:52,530 --> 00:19:54,800
διαλογής ένα σωρό αριθμούς;

335
00:19:54,800 --> 00:19:57,050
Αυτά τα πράγματα που αναφέρονται ως κομμάτια του παζλ. Ναι.

336
00:19:57,050 --> 00:19:59,950
>> [Φοιτητής] θα λάβει κάθε αριθμό και συγκρίνετέ την με κάθε μία

337
00:19:59,950 --> 00:20:03,180
και συνεχίστε προς τα αριστερά. >> Εντάξει, καλά.

338
00:20:03,180 --> 00:20:05,720
Πάρτε λοιπόν κάθε αριθμό, συγκρίνετε το με το επόμενο να είναι,

339
00:20:05,720 --> 00:20:09,610
και στη συνέχεια, μόλις συνεχίσει να κινείται κατά μήκος της λίστας, το είδος της rejiggering τα πράγματα καθώς πηγαίνετε.

340
00:20:09,610 --> 00:20:13,800
Έτσι, εδώ έχουμε μια ευκαιρία για ίσως λίγα περισσότερα παιδιά να συμμετάσχουν.

341
00:20:13,800 --> 00:20:16,290
Έχουμε ακόμη 8 εθελοντές που θα ήθελαν να καταλήξουμε;

342
00:20:16,290 --> 00:20:23,950
Λίγο λιγότερη πίεση αφού δεν είστε ο μόνος. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Έλα κάτω. Εσείς πρόκειται να είναι οι αριθμοί 1 έως 8.

344
00:20:28,190 --> 00:20:36,050
Ας δούμε αν δεν μπορούμε να κάνουμε αυτή την διαλογή για τον Άλεξ πολύ με τον ίδιο τρόπο που το έκανα εκ των προτέρων.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Προχωρήστε και αν θα κάνατε, line up στη σκηνή ανάμεσα στο περίπτερο μουσική και εγώ εδώ

347
00:20:40,760 --> 00:20:44,960
με την ίδια σειρά όπως η διαφάνεια στην οθόνη.

348
00:20:47,910 --> 00:20:49,680
Uh-oh.

349
00:20:50,370 --> 00:20:53,230
Θα εργάζεστε στο επόμενο παράδειγμα. Περίμενε, περίμενε. Εδώ πάμε. Περιμένετε.

350
00:20:53,230 --> 00:20:57,570
Το επόμενο παράδειγμα είναι τώρα. Εδώ θα πάτε. Αριθμός 8. Ελάτε επάνω.

351
00:20:57,570 --> 00:21:00,270
Εντάξει. Ταξινόμηση οι ίδιοι, σύμφωνα με αυτό.

352
00:21:00,270 --> 00:21:03,620
Σύρετε απλά λίγο προς την πλευρά της μουσικής στέκονται εδώ.

353
00:21:03,620 --> 00:21:12,310
Έτσι, έχουμε 4, 2, 6 - να πάρει εκεί, εδώ, εκεί - 3.

354
00:21:12,310 --> 00:21:17,570
Ναι. Εντάξει. Μπορείτε να πάτε εδώ. Όχι, μείνετε εκεί.

355
00:21:17,570 --> 00:21:21,840
Ναι, ακριβώς εκεί. Όχι, είμαι λάθος. Ακριβώς εκεί. Εντάξει, πολύ καλό. Εντάξει.

356
00:21:21,840 --> 00:21:24,930
Έτσι τώρα ας τους ταξινομήσετε σε αύξουσα σειρά.

357
00:21:24,930 --> 00:21:26,210
>> Πώς μπορώ να πάω για να κάνει αυτό;

358
00:21:26,210 --> 00:21:28,630
Ο αλγόριθμος που προτάθηκε πριν από λίγο ήταν γιατί δεν είμαστε απλά συγκρίνετε

359
00:21:28,630 --> 00:21:31,970
οι λαοί που είναι το είδος της ένα δίπλα στο άλλο και στη συνέχεια να διορθώσετε τυχόν λάθη,

360
00:21:31,970 --> 00:21:33,540
κινείται από αριστερά προς τα δεξιά.

361
00:21:33,540 --> 00:21:36,580
Έτσι, εδώ έχουμε 4 και 2, προφανώς εκτός λειτουργίας. Ας αλλάζετε. Εντάξει.

362
00:21:36,580 --> 00:21:40,760
Έτσι, τώρα θα πάω να κινηθεί κάτω από τη γραμμή. 4 και 6, nope. [Γέλια]

363
00:21:40,760 --> 00:21:45,010
6 και 8, πολύ καλή. 8 και 1, επιτρέψτε μου να ανταλλάξουν εσείς. Εντάξει.

364
00:21:45,010 --> 00:21:48,030
Έτσι, 8 και 3, αλλάξτε εσείς.

365
00:21:48,030 --> 00:21:52,280
8 και 7, επιτρέψτε μου να ανταλλάξουν εσείς. 5 και 8, εξαιρετική.

366
00:21:52,280 --> 00:21:54,820
Σας δίνω μια ταξινομημένη λίστα.

367
00:21:54,820 --> 00:21:56,860
Εντάξει. Έτσι, δεν είναι αρκετά.

368
00:21:56,860 --> 00:22:01,180
Αλλά είναι καλύτερα, επειδή οι μεγαλύτερους αριθμούς - περίπτωση στο σημείο 8 -

369
00:22:01,180 --> 00:22:04,030
έχουν το είδος της διοχετεύεται επάνω από το αριστερό πάνω προς τα δεξιά.

370
00:22:04,030 --> 00:22:08,010
Γι 'αυτό και πήρε 1 από τα δεξιά, αλλά αισθάνεται σαν αυτό δεν έλυσε το πρόβλημα αρκετά.

371
00:22:08,010 --> 00:22:11,150
>> Λοιπόν, τι θα προτείνατε να κάνουμε το επόμενο βήμα; >> [Φοιτητής] Συνεχίστε να το κάνετε αυτό. >> Κρατάμε το κάνουμε.

372
00:22:11,150 --> 00:22:13,740
Και συνειδητοποιούν, πάλι, θέτουμε τα πράγματα από απλά έχοντας όλους τους ανθρώπους

373
00:22:13,740 --> 00:22:17,180
είδος οργανώσει οι ίδιοι έξυπνα με βάση αυτή την εικόνα,

374
00:22:17,180 --> 00:22:19,040
αλλά τώρα πρέπει να είμαστε πολύ πιο μεθοδικά.

375
00:22:19,040 --> 00:22:21,510
Πρέπει να είναι αλγοριθμική γι 'αυτό σαν να γράφουμε κώδικα -

376
00:22:21,510 --> 00:22:23,520
σε αυτή την περίπτωση λεκτική ψευδοκώδικα.

377
00:22:23,520 --> 00:22:26,040
Έτσι, επιτρέψτε μου να προσπαθήσω πάλι. Αυτό λειτούργησε αρκετά καλά. Δεν το λύσει.

378
00:22:26,040 --> 00:22:30,400
Αλλά όταν αμφιβάλλω, απλώς προσπαθήστε και προσπαθήστε ξανά. Έτσι, 2 και 4, δεν βοηθούν πια.

379
00:22:30,400 --> 00:22:33,200
4 και 6. Αχ! 6 και 1, ελαφρώς καλύτερα τώρα.

380
00:22:33,200 --> 00:22:39,740
6 και 3, καλή. 6 και 7, 7 και 5, 7 και 8, καλή.

381
00:22:39,740 --> 00:22:44,060
Και ξέρετε, εγώ μπορεί να αγνοήσει πιθανώς 8 τώρα επειδή είναι στο τέλος της λίστας.

382
00:22:44,060 --> 00:22:47,250
Ίσως δεν έχετε να ανησυχείτε για να πάει κάποιος μπροστά του.

383
00:22:47,250 --> 00:22:49,240
Αλλά ας δούμε αν αυτό είναι μια ασφαλής υπόθεση.

384
00:22:49,240 --> 00:22:52,340
Τώρα είναι η λίστα - δεκάρα - δεν ταξινομημένο. Ας δοκιμάσουμε ξανά.

385
00:22:52,340 --> 00:22:56,440
Έτσι 2 και 4, 4 και 1, 4 και 3.

386
00:22:56,440 --> 00:22:59,230
4 και 6, καλή. 6 και 5, καλή.

387
00:22:59,230 --> 00:23:04,890
6, 7, και 8, καλή. Αλλά ειδοποίηση, μπορώ μόνο να σταματήσει εδώ και τώρα να σταματήσει εδώ τώρα;

388
00:23:04,890 --> 00:23:07,770
[Φοιτητής] Ναι. Ναι >>;

389
00:23:07,770 --> 00:23:11,160
Τι θα συμβεί αν κάποιος από εσάς ήταν ο αριθμός 9 σε όλη τη διαδρομή πάνω από εκεί;

390
00:23:11,160 --> 00:23:13,640
Θα έχουν ταξινομηθεί. Καλή >>. Θα έχουν ταξινομηθεί για πρώτη φορά γύρω.

391
00:23:13,640 --> 00:23:16,050
Καλή. Ας πάμε πάλι πίσω. Είμαστε σχεδόν εκεί.

392
00:23:16,050 --> 00:23:22,800
1 και 2, 2 και 3, 3 και 4, 4 και 5, 5 και 6, 6 και 7, 7 και 8.

393
00:23:22,800 --> 00:23:26,640
>> Είμαι γίνει τώρα, αλλά, και πάλι, είμαι ένας υπολογιστής που μπορεί να κάνει μόνο ό, τι μου έχουν πει να κάνω,

394
00:23:26,640 --> 00:23:30,120
και μόνο ανάμνηση μου τώρα είναι ότι εγώ πραγματικά έκανε ακριβώς ένα κομμάτι της εργασίας.

395
00:23:30,120 --> 00:23:31,700
Κάτι άλλαξε εδώ.

396
00:23:31,700 --> 00:23:37,100
Γι 'αυτό και δεν έχουν επιβεβαιωθεί οπτικά τεχνικά ή αλγοριθμικά ότι ο κατάλογος αυτός είναι πράγματι ταξινομημένο.

397
00:23:37,100 --> 00:23:40,720
Έτσι, μόνο για το καλό μέτρο, ακριβώς για να είναι πρωκτικό γι 'αυτό, ας κάνουμε αυτό 1 φορά.

398
00:23:40,720 --> 00:23:44,040
Έτσι 1 και 2, 2 και 3, 3 και 4. Και ξέρετε τι;

399
00:23:44,040 --> 00:23:46,190
Ακριβώς για το καλό μέτρο, Πάω να παρακολουθείτε το χέρι μου αυτή τη φορά

400
00:23:46,190 --> 00:23:51,110
πόσα swaps κάνω ακριβώς έτσι ότι ξέρω πόση δουλειά που έχω κάνει στην πραγματικότητα.

401
00:23:51,110 --> 00:23:56,930
3 και 4, 4 και 5, 5 και 6, 6 και 7, 7 και 8. Δεν swaps.

402
00:23:56,930 --> 00:24:00,800
Έτσι τώρα θα ήθελα να είναι νόμιμα ηλίθιος για να το κάνουμε αυτό και πάλι

403
00:24:00,800 --> 00:24:03,330
γιατί αν το έκανα καμία δουλειά μέσα από αυτό το πέρασμα των ανθρώπων,

404
00:24:03,330 --> 00:24:06,710
τότε σαφώς ότι πρόκειται να συμβεί ξανά εάν κανένα από αυτά δεν είναι τυχαία είδος της

405
00:24:06,710 --> 00:24:10,410
adversarially κινείται γύρω από τον εαυτό τους. Έτσι τώρα μπορώ να σταματήσω.

406
00:24:10,410 --> 00:24:15,120
Τώρα ας θέσουμε το ερώτημα, πόση δουλειά έκανε αυτό μου πάρει πραγματικά;

407
00:24:15,120 --> 00:24:18,260
Πόσα βήματα δεν πάρει αυτό; >> Ν τετράγωνο.

408
00:24:18,260 --> 00:24:20,400
Ναι, έτσι n τετράγωνο. Σε περίπτωση που δεν μπορείτε να πάρετε από το τετράγωνο n;

409
00:24:20,400 --> 00:24:22,660
Θα πρέπει να ελέγξετε κάθε αριθμός -

410
00:24:22,660 --> 00:24:26,530
Υπάρχει n αριθμούς, και θα πρέπει να ελέγξετε κάθε αριθμό με τους άλλους αριθμούς n.

411
00:24:26,530 --> 00:24:29,030
Καλή. >> Έτσι είναι n τετράγωνο. Καλή >>.

412
00:24:29,030 --> 00:24:31,060
>> Γι 'αυτό αισθάνεται όπως θα μπορούσε κάλλιστα να είναι n τετράγωνο, έτσι δεν είναι;

413
00:24:31,060 --> 00:24:33,820
Εκεί n από αυτά τα παιδιά, 8 ειδικά σε αυτή την περίπτωση,

414
00:24:33,820 --> 00:24:37,590
αλλά κάθε φορά που πήγα μέσα από αυτή τη λίστα μου συγκρίνοντας το πρώτο πρόσωπο κατά τη δεύτερη,

415
00:24:37,590 --> 00:24:39,650
η δεύτερη κατά το τρίτο ξανά και ξανά και ξανά,

416
00:24:39,650 --> 00:24:42,450
και όταν έφτασα στο τέλος, τι να κάνω; Μου redid.

417
00:24:42,450 --> 00:24:46,280
Έτσι, αν γενικεύσουμε αυτή την εξήγηση, έχουμε n άτομα

418
00:24:46,280 --> 00:24:51,090
και κάνω, προφανώς 8 βήματα, n βήματα, κάθε φορά που πάω με αυτόν τον αλγόριθμο.

419
00:24:51,090 --> 00:24:56,070
Αλλά πόσες φορές στη χειρότερη περίπτωση δεν πρέπει να περάσει μέσα από αυτή τη λίστα των ανθρώπων;

420
00:24:56,070 --> 00:24:59,370
[Φοιτητής] Ν φορές. Πιθανώς n >>, δεξιά, διότι στη χειρότερη περίπτωση,

421
00:24:59,370 --> 00:25:03,410
τι είναι ίσως η χειρότερη περίπτωση ρύθμισης από αυτά τα παιδιά από το get-go;

422
00:25:03,410 --> 00:25:06,520
Αν είστε αντιστραφεί εντελώς παραγγελία

423
00:25:06,520 --> 00:25:09,310
επειδή ακριβώς ας υποθέσουμε, διανοητικά let's - Ποιο είναι το όνομά σου; >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Εντάξει. Έτσι Bowen, έλα εδώ για μια στιγμή.

425
00:25:12,510 --> 00:25:16,150
>> Ας υποθέσουμε ότι Bowen ήταν εδώ κατά την έναρξη του αλγορίθμου,

426
00:25:16,150 --> 00:25:19,790
και δεν ξέρουμε τι όλοι οι άλλοι είναι, αλλά εδώ Bowen, σύμφωνα με αυτόν τον αλγόριθμο -

427
00:25:19,790 --> 00:25:23,820
και αν θέλετε απλά να κάνετε μια βόλτα μαζί μου - πρόκειται για φούσκα επάνω, όπως έκανε και την πρώτη φορά,

428
00:25:23,820 --> 00:25:25,740
όλη τη διαδρομή μέχρι το τέλος.

429
00:25:25,740 --> 00:25:29,400
Αλλά ας υποθέσουμε ότι το πρόσωπο δίπλα σε Bowen ήταν ο αριθμός 7.

430
00:25:29,400 --> 00:25:33,450
Πρέπει να πάω πίσω και να πάρει τον αριθμό 7, το οποίο σημαίνει ότι πρέπει να πάει όλος ο τρόπος πίσω εδώ.

431
00:25:33,450 --> 00:25:36,980
Τώρα πρέπει να έχω την ίδια απόσταση με το πρόσωπο που είναι ο αριθμός 7.

432
00:25:36,980 --> 00:25:40,140
Αλλά τι θα γινόταν αν τότε ο αριθμός 6 ήταν δίπλα του, καθώς;

433
00:25:40,140 --> 00:25:42,180
Στη συνέχεια, πρέπει να πάω πίσω και να πάρει 6.

434
00:25:42,180 --> 00:25:46,490
Έτσι, και πάλι, σε κάθε επανάληψη του βρόχου αυτό μιλάω για κάθε μία από τις n ανθρώπων,

435
00:25:46,490 --> 00:25:50,090
και εγώ θα πρέπει να κάνει n αυτών βόλτες για να βεβαιωθείτε ότι είμαι τραβώντας

436
00:25:50,090 --> 00:25:53,760
όλα από τα μεγαλύτερα στοιχεία και πίσω και πίσω μέχρι το τέλος της λίστας.

437
00:25:53,760 --> 00:25:58,230
Έτσι, n n φορές τα πράγματα είναι ακριβώς n φορές n ή n τετράγωνο.

438
00:25:58,230 --> 00:26:02,050
>> Έτσι, εδώ έχουμε ήδη έναν αλγόριθμο που δεν είναι πλέον ν, που δεν είναι πλέον log n,

439
00:26:02,050 --> 00:26:04,820
είναι στην πραγματικότητα χειρότερο από οτιδήποτε έχουμε κάνει στο παρελθόν.

440
00:26:04,820 --> 00:26:09,840
Έτσι Alex είδος του πήρε τυχερός στο ότι έκανα όλη τη δουλειά προφανώς μπροστά γι 'αυτήν,

441
00:26:09,840 --> 00:26:14,690
όλα τα ακριβά εργασίας, έτσι ώστε θα μπορούσε να απολαύσετε σε αυτό το δυαδικό αλγόριθμο αναζήτησης,

442
00:26:14,690 --> 00:26:16,420
που είναι log n του.

443
00:26:16,420 --> 00:26:18,240
Αλλά αυτό είναι συμβατό με το θέμα της Δευτέρας.

444
00:26:18,240 --> 00:26:23,260
Δώσαμε ένα λίγο περισσότερο χώρο, θα χρησιμοποιείται περισσότερο bits, προκειμένου να επιταχυνθεί χρόνο λειτουργίας μας.

445
00:26:23,260 --> 00:26:26,170
Τόσο πολύ σαν να υπάρχει αυτό το trade-off μεταξύ του χρόνου και του χώρου,

446
00:26:26,170 --> 00:26:31,060
μπορεί να υπάρχουν, επίσης, απλά να τους συμβιβασμούς μεταξύ του χρόνου που πέρασε μπροστά είδος του να πάρει τα πράγματα είναι έτοιμα να ξεκινήσουν

447
00:26:31,060 --> 00:26:35,000
και εκτελεί στην πραγματικότητα έναν αλγόριθμο όπως η αναζήτηση. Ας προσπαθήσουμε ένα άλλο.

448
00:26:35,000 --> 00:26:39,050
Αν εσείς δεν θα με πείραζε απλά γρήγορα αναδιάταξη εαυτό σας για να ταιριάζει με ότι και πάλι,

449
00:26:39,050 --> 00:26:42,240
ας δοκιμάσουμε κάτι διαφορετικό ελαφρώς όπου δεν είναι αρκετά τόσο απλό

450
00:26:42,240 --> 00:26:45,760
όπως ακριβώς διορθώσετε όλα τα λάθη ανά ζεύγος, το οποίο είναι εξαιρετικά διαισθητική.

451
00:26:45,760 --> 00:26:48,150
Ας αντί να είναι λίγο πιο σκόπιμη και να το κάνετε αυτό.

452
00:26:48,150 --> 00:26:51,010
Αυτό και μόνο πολύ θα ήθελα να προτείνω είναι μάλλον αρκετά έξυπνο.

453
00:26:51,010 --> 00:26:55,070
>> Ας επιλέξτε το μικρότερο άτομο από τη λίστα ξανά και ξανά. Έτσι, εδώ πηγαίνουμε.

454
00:26:55,070 --> 00:26:57,350
4, που είναι το μικρότερο άτομο που έχω δει έτσι μέχρι τώρα,

455
00:26:57,350 --> 00:27:00,520
έτσι Πάω να θυμόμαστε διανοητικά ότι με απλά δείχνοντας σας για τώρα.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Ξεχάστε τον αριθμό 4. Βρήκα μόλις το νέο μικρότερο στοιχείο σε αυτή τη λίστα.

457
00:27:05,020 --> 00:27:07,410
Πάω να θυμούνται το είδος αυτό. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Αντίο. Έτσι, τώρα θα πάω να θυμόμαστε τον αριθμό 1.

459
00:27:11,190 --> 00:27:14,790
Γνωρίζουμε ότι το 1 είναι ο μικρότερος, αλλά είμαι ο υπολογιστής. Τι γίνεται αν υπάρχει ένα 0;

460
00:27:14,790 --> 00:27:17,140
Τι γίνεται αν υπάρχει ένα -1; Πρέπει να συνεχίσω.

461
00:27:17,140 --> 00:27:20,990
Έτσι, 3, 7, 5, nope. Εντάξει. Έτσι, ο αριθμός 1 ήταν η μικρότερη.

462
00:27:20,990 --> 00:27:23,640
Επιτρέψτε μου να σας επιλέξτε από τη λίστα - we'll πάει με αυτόν τον τρόπο -

463
00:27:23,640 --> 00:27:27,760
και βάζετε αυθαίρετα στην αρχή της λίστας.

464
00:27:27,760 --> 00:27:29,740
Τώρα, περιμένετε ένα λεπτό. Ι το είδος εξαπατημένοι.

465
00:27:29,740 --> 00:27:34,010
Αν αυτοί οι τύποι δεν αντιπροσωπεύουν μια λίστα των 8 ατόμων, αλλά μια σειρά,

466
00:27:34,010 --> 00:27:37,050
8 κομμάτια της συνεχούς μνήμης - δεν σας πειράζει βήμα πίσω για μια στιγμή;

467
00:27:37,050 --> 00:27:39,060
Δεν υπάρχει πραγματικά κανένας χώρος για σας εδώ.

468
00:27:39,060 --> 00:27:41,840
Επομένως, πώς θα κάνουν χώρο για - τι είναι το όνομά σας; >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Πώς θα κάνουμε χώρο για Sammy;

470
00:27:43,710 --> 00:27:46,760
>> Κινούμαστε τα n που είναι μπροστά μου. Εντάξει >>.

471
00:27:46,760 --> 00:27:48,850
Έτσι, θα μπορούσαμε να μετακινήσετε τα n άτομα που είναι πριν απ 'αυτόν,

472
00:27:48,850 --> 00:27:52,400
οπότε αν εσείς θέλετε να λάβει 1 σκόπιμη, δραματικό βήμα προς τα αριστερά.

473
00:27:52,400 --> 00:27:57,000
Έκαναν όλα αυτά σε αρμονία, αλλά την τελευταία φορά που έγραψα κάποιο κώδικα,

474
00:27:57,000 --> 00:27:59,740
δεν μπορείτε να ταξινομήσετε του κινούνται πολλά πράγματα ταυτόχρονα.

475
00:27:59,740 --> 00:28:02,450
Θα μπορούσαμε να το κάνουμε με έναν βρόχο, κινείται ο καθένας μια φορά σε μια στιγμή.

476
00:28:02,450 --> 00:28:04,340
Έτσι, αν εσείς δεν θα με πείραζε βήμα πίσω προς τα δεξιά,

477
00:28:04,340 --> 00:28:07,230
και Sammy, εάν θα μπορούσε να βήμα πίσω, γιατί υπάρχει ακόμα κανένας χώρος για σας,

478
00:28:07,230 --> 00:28:11,420
Τώρα ας κάνουμε αυτό. Πού ήταν Sammy πριν από λίγο; Ακριβώς εκεί.

479
00:28:11,420 --> 00:28:16,140
Έτσι, υπάρχει ένα κενό εκεί. Έτσι, θα μπορούσε να κινηθεί σε σημείο του Sammy.

480
00:28:16,140 --> 00:28:20,580
Τώρα επόμενο πρόσωπο μέχρι και τώρα το επόμενο πρόσωπο, τώρα το επόμενο πρόσωπο. Τώρα έχουμε περιθώρια για Sammy.

481
00:28:20,580 --> 00:28:23,490
Τώρα, κάποιος από το κοινό - που ήταν καλή, που ήταν σωστή,

482
00:28:23,490 --> 00:28:27,070
αισθάνθηκε λίγο χρονοβόρα - τι είναι πιο γρήγορα; Ναι.

483
00:28:27,070 --> 00:28:29,440
[Φοιτητής] Μια νέα σειρά; >> Τι είναι αυτό; >> [Φοιτητής] Μια νέα σειρά; >> Εντάξει, καλά.

484
00:28:29,440 --> 00:28:33,200
>> Έτσι, σύμφωνα με αυτό το θέμα μόλις συμβιβασμούς, γιατί δεν μπορώ να κάνω μόνο μια νέα σειρά

485
00:28:33,200 --> 00:28:36,570
 και στη συνέχεια θα Sammy να κολυμπάνε στο χώρο μπροστά από αυτά τα άτομα, για παράδειγμα,

486
00:28:36,570 --> 00:28:39,600
και μπορούμε απλά να αρχίσει να γεμίζει μια εντελώς νέα σειρά. Αυτό επίσης θα μπορούσε να λειτουργήσει.

487
00:28:39,600 --> 00:28:42,450
Αλλά δεν είμαι ενδιαφέρονται για τις δαπάνες σήμερα περισσότερο χώρο. Τι είναι μια άλλη προσέγγιση;

488
00:28:42,450 --> 00:28:46,630
[Φοιτητής] Swap. Εντάξει >>. Θα μπορούσαμε να ανταλλάξουν μόνο αυτά τα 2 παιδιά. Ποιο είναι το όνομά σου;

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Έτσι, Mario, ήσασταν σήμερα εδώ.

490
00:28:49,390 --> 00:28:52,480
Sammy, μπορείτε να δημιουργήσετε αντίγραφα ασφαλείας για μια στιγμή; Mario ήταν εδώ.

491
00:28:52,480 --> 00:28:55,830
Δεν έχουμε περιθώρια για σας πια, οπότε αν δεν θα με πείραζε, όπου πρόκειται να Sammy είναι,

492
00:28:55,830 --> 00:29:02,430
θα βάλουμε Sammy εδώ, και τώρα θα ήθελα να υποστηρίζουν ότι αλλάζουν τη λειτουργία του Sammy ήταν πολύ πιο γρήγορα.

493
00:29:02,430 --> 00:29:06,370
Κάναμε μία λειτουργία για να ανταλλάξει αυτά τα παιδιά, ή ίσως 2 για να ανταλλάξουν αυτά τα παιδιά,

494
00:29:06,370 --> 00:29:11,210
αλλά δεν κάναμε 1, 2, 3, 4, έτσι ώστε αισθάνεται καλύτερα. Τώρα, περιμένετε ένα λεπτό.

495
00:29:11,210 --> 00:29:14,660
Ι το είδος του κάνει το πρόβλημα χειρότερο, διότι ο αριθμός 4 ήταν το είδος του κοντά στην αρχή.

496
00:29:14,660 --> 00:29:19,470
Τώρα αριθμός 4 είναι λίγο πιο κοντά προς το σκοπό αυτό, αλλά δεν είχα πραγματικά γνωρίζουν ή ενδιαφέρονται γι 'αυτό.

497
00:29:19,470 --> 00:29:23,330
Έτσι, αυτό είναι απλά κακή τύχη ότι ο αριθμός 4 είναι λίγο πιο μακριά από την προκαθορισμένη του θέση.

498
00:29:23,330 --> 00:29:25,110
Ας επαναλάβουμε τώρα αυτόν τον αλγόριθμο.

499
00:29:25,110 --> 00:29:28,410
>> Για να ανακεφαλαιώσουμε, εφ 'όσον αυτή η ιστορία ήταν, το μόνο που έκανε ήταν με τα πόδια μέσα από τη λίστα

500
00:29:28,410 --> 00:29:31,130
ψάχνει για τον αριθμό μικρότερο άτομο.

501
00:29:31,130 --> 00:29:34,530
Έτσι, τώρα ας το κάνουμε πάλι. Δεν χρειάζεται να ανησυχείτε για Sammy πια.

502
00:29:34,530 --> 00:29:37,590
Μπορούμε απλά να πάτε εδώ. Ooh! Αριθμός 2. Αυτός είναι ένας πολύ μικρός αριθμός.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Εντάξει, καλά.

504
00:29:41,180 --> 00:29:43,770
Και ευτυχώς, από σύμπτωση, δεν έχω να κινηθεί - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie επειδή είναι σε σωστή θέση του τώρα.

506
00:29:45,910 --> 00:29:48,110
Ας κάνουμε αυτό και πάλι και να αγνοούν αυτά τα 2 παιδιά.

507
00:29:48,110 --> 00:29:50,460
6. Αυτός είναι ένας πολύ μικρός αριθμός. Ooh! 8 είναι σίγουρα μεγαλύτερο.

508
00:29:50,460 --> 00:29:53,410
4. Ας επικεντρωθεί στις 4. Ooh! 3 είναι ακόμα καλύτερα.

509
00:29:53,410 --> 00:29:58,290
7 και 5. Λοιπόν, τι θα κάνουμε τώρα με - >> Ρότζερ. >> Roger;

510
00:29:58,290 --> 00:30:00,250
Ας τον ανταλλάξουν με τον αριθμό 6.

511
00:30:00,250 --> 00:30:03,570
Έτσι, εάν 6 και 3 θα ήθελα να ανταλλάξουν,

512
00:30:03,570 --> 00:30:07,320
έχουμε τώρα το είδος του πάρει τυχερός σε αυτό το 6 είναι πιο κοντά στο σημείο όπου αυτή θα πρέπει να είναι,

513
00:30:07,320 --> 00:30:10,300
αλλά είναι απλώς σύμπτωση εδώ. Ας πάμε τώρα εδώ.

514
00:30:10,300 --> 00:30:13,430
8 είναι ένα πολύ μικρό αριθμό. Ooh! 4 είναι μικρότερη.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Τι κάνουμε τώρα; Swap >>. Ακριβώς >>.

516
00:30:17,130 --> 00:30:19,010
Έτσι, τώρα ας κάνουμε αυτό το είδος της πιο γρήγορα.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Πού 5 πάτε; Καλή. Εντάξει.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 παίρνει να μείνει εκεί που είναι. Ποιο είναι το όνομά σου; >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie παίρνει να μείνει εκεί που είναι. 7 παίρνει να - Για να δούμε. 7, 8. Εντάξει.

520
00:30:31,770 --> 00:30:35,100
Έτσι 7 παίρνει να μείνει εκεί που είναι. Ποιο είναι το όνομά σου; >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Έτσι Amna παίρνει να μείνει εκεί που είναι, και ο αριθμός 8 είναι ήδη τώρα, όπου πρέπει να είναι.

522
00:30:39,670 --> 00:30:43,960
Εντάξει, καλά. Αισθάνεται σαν να είμαστε δημιουργώντας απλά το έργο για τους εαυτούς μας εδώ, όμως.

523
00:30:43,960 --> 00:30:47,440
Τι είναι τελικά ο χρόνος εκτέλεσης του αλγορίθμου;

524
00:30:47,440 --> 00:30:51,900
Αν σκεφτούμε αυτούς τους ανθρώπους όχι ως 8, αλλά όπως n; >> Είναι n.

525
00:30:51,900 --> 00:30:55,440
Είναι n βήματα, αλλά είμαστε έλεγχο κάθε φορά.

526
00:30:55,440 --> 00:30:57,570
Εντάξει. Ν αλλά εσείς τον έλεγχο κάθε φορά;

527
00:30:57,570 --> 00:31:03,450
Εντάξει, αλλά αν είναι n βήματα, δεν θα πρέπει να έχω τη δυνατότητα να ταξινομήσετε σας με απλά θα 1, 2, 3, 4;

528
00:31:03,450 --> 00:31:05,590
Oh! Εντάξει, αυτό είναι μια μεγάλη διαφορά.

529
00:31:05,590 --> 00:31:08,050
Έτσι n τετράγωνο γιατί; Τι πραγματικά συμβαίνει;

530
00:31:08,050 --> 00:31:12,130
Υπάρχει n άνθρωποι σε αυτή τη λίστα, αλλά για να βρει το μικρότερο άτομο στον κατάλογο

531
00:31:12,130 --> 00:31:16,200
στη χειρότερη περίπτωση, πόσα βήματα μπορώ να λάβει; >> Ν.

532
00:31:16,200 --> 00:31:19,160
>> Ν, δεξιά, διότι στη χειρότερη περίπτωση, ο αριθμός 1 είναι όλος ο τρόπος εκεί,

533
00:31:19,160 --> 00:31:20,990
γι 'αυτό πρέπει να πάει να πάρει αυτόν ή αυτήν.

534
00:31:20,990 --> 00:31:25,500
Και στη συνέχεια, όταν τελικά συνειδητοποιούν 1 ήταν το μικρότερο, τότε είναι αρκετά γρήγορος για να τους ανταλλάξουν.

535
00:31:25,500 --> 00:31:28,450
Αλλά τώρα πρέπει να ξεκινήσει από την αρχή και να δούμε για ποιον;

536
00:31:28,450 --> 00:31:31,980
Η επόμενη μικρότερη προσώπου, η οποία είναι 2. Σε περίπτωση που στη χειρότερη περίπτωση είναι 2;

537
00:31:31,980 --> 00:31:34,320
Ω, Θεέ μου. Είναι όλος ο τρόπος εδώ στο τέλος.

538
00:31:34,320 --> 00:31:37,000
Μέχρι τώρα έχω κάνει μόνο μια άλλη n βήματα, ένα άλλο n βήματα.

539
00:31:37,000 --> 00:31:41,200
Και αν έχουμε n άτομα και στη χειρότερη περίπτωση το μικρότερο άτομο είναι n βήματα,

540
00:31:41,200 --> 00:31:45,230
αυτό είναι και πάλι n n φορές, και γι 'αυτό έχουν και πάλι ν τετράγωνο.

541
00:31:45,230 --> 00:31:47,280
Αυτό δεν αισθάνεται και τόσο καλά.

542
00:31:47,280 --> 00:31:52,150
Και στην πραγματικότητα, ακόμη και στην καλύτερη περίπτωση - ας υποθέσουμε ότι ξεκινάτε ταξινομημένο -

543
00:31:52,150 --> 00:31:59,080
πόσα βήματα χρειάζεται για μένα με αυτόν τον αλγόριθμο για να ταξινομήσετε τα n άνθρωποι;

544
00:31:59,080 --> 00:32:01,010
Ν τετράγωνο. >> Άκουσα ν τετράγωνο. Γιατί ν τετράγωνο;

545
00:32:01,010 --> 00:32:05,240
Επειδή πρέπει ακόμα να ελέγξει κάθε φορά. Ναι >>.

546
00:32:05,240 --> 00:32:08,060
Και θα πρέπει να τα ανταλλάξουν. >> Ακόμα κι αν οι άνθρωποι είναι το είδος του παντογνώστης

547
00:32:08,060 --> 00:32:10,770
με την έννοια ότι οπτικά μπορούμε ακριβώς το είδος της δείτε ότι αυτό είναι ταξινομημένο,

548
00:32:10,770 --> 00:32:12,140
ένας υπολογιστής δεν είναι ότι έξυπνος.

549
00:32:12,140 --> 00:32:14,040
Είναι πρόκειται να δούμε εδώ και εδώ και εδώ,

550
00:32:14,040 --> 00:32:16,610
αλλά αν αυτό που ψάχνει είναι το μικρότερο στοιχείο,

551
00:32:16,610 --> 00:32:22,110
το μόνο που ξέρετε ότι βρήκε το μικρότερο στοιχείο από ποιο σημείο; Μόλις είστε στο τέλος.

552
00:32:22,110 --> 00:32:25,880
Αλλά σε αυτό το σημείο έχετε βρεί μόνο το σήμερα μικρότερο στοιχείο.

553
00:32:25,880 --> 00:32:28,810
Δεν ξέρω κατ 'ανάγκη οτιδήποτε άλλο για την κατάσταση του κόσμου.

554
00:32:28,810 --> 00:32:30,880
Έτσι, θα πρέπει να πάτε ξανά και ξανά και ξανά.

555
00:32:30,880 --> 00:32:34,880
>> Έτσι, αυτή τη φορά πραγματικά φαίνονται χαζή επειδή είμαι έλεγχο, εντάξει, 2, είσαι το μικρότερο,

556
00:32:34,880 --> 00:32:37,530
αλλά δεν ξέρω πως στο σύνολο ακόμα.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Εντάξει, καλά. 2 ήταν πράγματι ο μικρότερος.

558
00:32:41,090 --> 00:32:43,150
Τώρα ας βρούμε την επόμενη μικρότερη. Εντάξει.

559
00:32:43,150 --> 00:32:48,350
3, είστε επί του παρόντος το μικρότερο. Ας δούμε. 4, 5, 6, 7, 8. Εντάξει, πήρε και πάλι τυχερός.

560
00:32:48,350 --> 00:32:53,170
3 ήταν πράγματι στο σωστό μέρος. Αλλά Πάω να συνεχίσει να κάνει αυτό ξανά και ξανά και ξανά.

561
00:32:53,170 --> 00:32:55,990
Πώς μπορούμε να κάνουμε πάντα τόσο ελαφρώς καλύτερα;

562
00:32:55,990 --> 00:33:00,120
Αντί να έχουμε ανθρώπους φούσκα επάνω ζεύγη από το μικρότερο στο μεγαλύτερο

563
00:33:00,120 --> 00:33:04,350
και αντί να πηγαίνουν πέρα ​​δώθε μέσα από τη λίστα επιλέγοντας το μικρότερο άτομο, στη συνέχεια,

564
00:33:04,350 --> 00:33:09,780
γιατί δεν εισάγουμε αυτούς τους ανθρώπους, αντί σε ένα νέο βήμα προς βήμα λίστα;

565
00:33:09,780 --> 00:33:13,080
Ας προσπαθήσουμε αυτό. Τώρα, επιτρέψτε μου να καλέσετε αυτό το είδος εισαγωγής πράγμα.

566
00:33:13,080 --> 00:33:17,250
Έτσι, εδώ είμαστε εδώ. Αριθμός 1. Δεν με νοιάζει για κανέναν άλλο σε αυτή τη λίστα.

567
00:33:17,250 --> 00:33:21,310
Ο στόχος μου τώρα είναι να τεθεί ο αριθμός 1 στην αρχή μιας ταξινομημένη λίστα.

568
00:33:21,310 --> 00:33:23,910
Και Πάω να προτείνω επειδή έχω μόνο 8 κομμάτια της μνήμης,

569
00:33:23,910 --> 00:33:28,670
αυθαίρετα τώρα είμαι ο τοίχος μεταξύ δήθεν αδιαχώριστα λίστα μου,

570
00:33:28,670 --> 00:33:32,740
και όποιος είναι πίσω μου Πάω να διεκδικήσει είναι ταξινομημένο.

571
00:33:32,740 --> 00:33:34,680
Έτσι τώρα έχουμε τον αριθμό 1.

572
00:33:34,680 --> 00:33:39,240
Θέλω να τον τοποθετήσετε σε ταξινομημένη λίστα μου, οπότε είμαι απλώς πρόκειται να κινηθεί τοίχο μου εδώ,

573
00:33:39,240 --> 00:33:43,930
και τώρα υποστηρίζουν αυτή η λίστα είναι ταξινομημένη, ο κατάλογος αυτός δεν έχει υποστεί διαλογή - τουλάχιστον μέχρι στιγμής όσο γνωρίζω.

574
00:33:43,930 --> 00:33:46,070
Δεν μπορώ να δω όλους τους αριθμούς ταυτόχρονα.

575
00:33:46,070 --> 00:33:49,000
>> Τώρα τυχαίνει να συναντήσουν τον αριθμό 2. Τι μπορώ να κάνω μαζί του;

576
00:33:49,000 --> 00:33:54,380
Σας εισάγετε τώρα στην ταξινομημένη λίστα. Αλλά παρατηρήσετε πόσο εύκολο ήταν αυτό.

577
00:33:54,380 --> 00:33:59,650
Απλά πρέπει να κοιτάξουμε. Αριθμός 1 είναι εκεί. Ω, προφανώς 2 πηγαίνει προς την πλευρά του αριθμού 1.

578
00:33:59,650 --> 00:34:03,700
Τώρα τι μπορώ να κάνω με 3; Σας εισάγετε στο ταξινομημένη λίστα. Αλλά αυτό ήταν εξαιρετικά εύκολο.

579
00:34:03,700 --> 00:34:07,250
Αυτό είναι εξαιρετικά εύκολο, αυτό είναι εξαιρετικά εύκολο, αυτό είναι εξαιρετικά εύκολο, εξαιρετικά εύκολο, σούπερ εύκολο.

580
00:34:07,250 --> 00:34:12,790
Και τώρα όλα είναι ταξινομημένο πίσω μου, και πόσα βήματα δεν πάρει αυτό;

581
00:34:12,790 --> 00:34:15,620
[Φοιτητές] >> Ν. Γι 'αυτό είναι μόνο n. Είμαστε τυχεροί.

582
00:34:15,620 --> 00:34:18,860
Ήταν μόνο n γιατί; >> [Φοιτητής] Επειδή ο κατάλογος ήταν ταξινομημένο.

583
00:34:18,860 --> 00:34:21,630
Ο κατάλογος είναι ήδη ταξινομημένο. Γι 'αυτό και πήρε τυχερός.

584
00:34:21,630 --> 00:34:25,639
Αλλά σχεδιάσαμε έναν αλγόριθμο αυτή τη φορά που εκμεταλλεύεται αυτό το είδος της τύχης,

585
00:34:25,639 --> 00:34:29,420
ότι καλύτερο σενάριο, με το να μην χάνουμε περιττό χρόνο.

586
00:34:29,420 --> 00:34:31,750
Έτσι έχουμε τώρα τι θα καλέσουμε τα είδη φούσκα

587
00:34:31,750 --> 00:34:33,949
όπου οι άνθρωποι είδος της φούσκας μέχρι ζεύγη.

588
00:34:33,949 --> 00:34:38,100
Έχουμε τώρα είδος επιλογής όπου θα κόβω από το μικρότερο άτομο ξανά και ξανά.

589
00:34:38,100 --> 00:34:42,350
Και τώρα έχουμε είδος εισαγωγής όπου είδους προληπτικά βάλει τους ανθρώπους που ανήκουν

590
00:34:42,350 --> 00:34:45,000
σε μια όλο και πιο ταξινομημένη λίστα.

591
00:34:45,000 --> 00:34:49,679
Αν μπορούσαμε, ένα χειροκρότημα για αυτά τα παιδιά εδώ. [Χειροκροτήματα]

592
00:34:49,679 --> 00:34:52,310
Ας ρίξουμε 5-λεπτά διάλειμμα μας εδώ.

593
00:34:52,310 --> 00:34:55,139
Και όταν θα έρθει πίσω, θα φυσήξει όλα αυτά αλγορίθμων έξω από το νερό

594
00:34:55,139 --> 00:35:00,260
με κάτι καλύτερο. Εντάξει. Ευχαριστώ πολύ. Μπορείτε να κρατήσετε τα ως αναμνηστικά.

595
00:35:01,710 --> 00:35:04,330
Εντάξει. Είμαστε πίσω.

596
00:35:04,330 --> 00:35:08,420
>> Και για να ανακεφαλαιώσουμε πολύ γρήγορα, είχαμε αυτά τα 3 διαφορετικές προσεγγίσεις για την ταξινόμηση,

597
00:35:08,420 --> 00:35:13,000
το νόημα της οποίας ήταν να φτάσουμε στο σημείο όπου κάποιος σαν τον Άλεξ

598
00:35:13,000 --> 00:35:16,930
θα μπορούσε να αναζητήσει μια λίστα με τους αριθμούς πιο γρήγορα από ό, τι κάποιος θα μπορούσε, όπως ο Sean.

599
00:35:16,930 --> 00:35:19,830
Και ακόμα κι αν έχουμε τέτοια απλά παραδείγματα με 8 αριθμούς,

600
00:35:19,830 --> 00:35:24,000
θα μπορούσατε να προεκτείνουν εύκολα σε 8 ιστοσελίδες, 8 δισεκατομμύρια ιστοσελίδες,

601
00:35:24,000 --> 00:35:26,680
ή 800 εκατομμύρια φίλους στο Facebook.

602
00:35:26,680 --> 00:35:30,090
Έτσι, αυτοί οι αλγόριθμοι μπορεί σίγουρα να κλιμακωθούν σε αυτά τα είδη των αξιών,

603
00:35:30,090 --> 00:35:32,300
και οι ιδέες είναι τελικά το ίδιο.

604
00:35:32,300 --> 00:35:36,140
Έτσι, το είδος φούσκα ήταν η πρώτη όπου το είδος της διοχετεύεται το μεγαλύτερο πρόσωπο

605
00:35:36,140 --> 00:35:39,110
σε όλη τη διαδρομή προς τα δεξιά από την εναλλαγή τους ανθρώπους ανά ζεύγος.

606
00:35:39,110 --> 00:35:42,040
Τότε είχαμε τι θα καλέσουμε είδος επιλογής όπου λίγο πιο σκόπιμα

607
00:35:42,040 --> 00:35:46,480
διατηρούνται αναζητούν μέσα από τη λίστα, επιλέγοντας το μικρότερο αριθμό ξανά και ξανά και ξανά,

608
00:35:46,480 --> 00:35:49,530
το λογικό αποτέλεσμα της οποίας είναι ότι ο κατάλογος είναι τελικά ταξινόμηση.

609
00:35:49,530 --> 00:35:53,780
Στη συνέχεια, στο τρίτο, προσέθεσα άνθρωποι στην κατάλληλη θέση τους,

610
00:35:53,780 --> 00:35:57,720
και κάναμε μια πολύ καλοσχεδιασμένη παράδειγμα το γεγονός ότι ο κατάλογος ήταν ήδη ταξινομημένο,

611
00:35:57,720 --> 00:36:01,100
αλλά αυτό ήταν να στείλει το μήνυμα ότι σε περίπτωση που το είδος της εισαγωγής,

612
00:36:01,100 --> 00:36:02,670
μπορείτε να πάρετε τυχεροί.

613
00:36:02,670 --> 00:36:07,930
Αν οι αριθμοί που έχουν ήδη ταξινομημένο, αυτό είναι μόνο πρόκειται να σας πάρει n ενέργειες προκειμένου να επιβεβαιώσει τόσο πολύ,

614
00:36:07,930 --> 00:36:10,870
λαμβάνοντας υπόψη ότι η επιλογή του είδους είστε λίγο περισσότερο όραμα σηράγγων

615
00:36:10,870 --> 00:36:14,360
και δεν συνειδητοποιούν ποτέ ότι ο κατάλογος είναι ήδη ταξινομημένο.

616
00:36:14,360 --> 00:36:16,830
Ας δούμε λοιπόν είδος φούσκα σε δράση εδώ.

617
00:36:16,830 --> 00:36:19,590
Στο παρακάτω παράδειγμα, είμαστε έτοιμοι να δούμε κάθετες μπάρες

618
00:36:19,590 --> 00:36:23,030
ύψος των οποίων αντιπροσωπεύουν οι αριθμοί, έτσι ώστε να μπορούμε να ταξινομήσετε τη διαλογή των Κοίτα να συμβεί.

619
00:36:23,030 --> 00:36:26,630
Όσο μικρότερη είναι η γραμμή, τόσο μικρότερος είναι ο αριθμός? Όσο μεγαλύτερη είναι η γραμμή, τόσο μεγαλύτερος είναι ο αριθμός.

620
00:36:26,630 --> 00:36:28,860
>> Και θα το παίξει σε αυτή την ταχύτητα προεπιλογή.

621
00:36:28,860 --> 00:36:33,460
Είναι πρόκειται να κινηθεί λίγο γρήγορα για τώρα, αλλά το κόκκινο είναι αυτό που δείχνει 2 μπαρ

622
00:36:33,460 --> 00:36:35,480
που συγκρίνονται δίπλα-δίπλα.

623
00:36:35,480 --> 00:36:39,520
Και αν δείτε προσεκτικά, αυτό που συμβαίνει είναι ότι, εάν οι ράβδοι είναι εκτός λειτουργίας,

624
00:36:39,520 --> 00:36:42,300
το μικρότερο μετακινείται προς τα αριστερά, το μεγαλύτερο, προς τα δεξιά,

625
00:36:42,300 --> 00:36:44,360
και στη συνέχεια να κρατήσει την προώθηση.

626
00:36:44,360 --> 00:36:48,520
Έτσι, αν το κάνουμε αυτό ξανά και ξανά, παρατηρούμε ότι τα μικρότερα μπαρ

627
00:36:48,520 --> 00:36:51,090
πρόκειται να κρατήσει στριμώχνονται το δρόμο τους προς τα αριστερά

628
00:36:51,090 --> 00:36:54,130
και τα μεγαλύτερα μπαρ θα στριμώχνονται για να κρατήσει το δρόμο τους προς τα δεξιά.

629
00:36:54,130 --> 00:36:58,490
Και πράγματι, αρχίζουμε να δούμε ένα μοτίβο σε όλη τη διαδρομή στη δεξιά πλευρά

630
00:36:58,490 --> 00:37:04,790
όπως είδαμε 8 και στη συνέχεια 7 τελικά αναβλύζει στην άκρη του ανθρώπινου λίστα μας.

631
00:37:04,790 --> 00:37:08,750
Έτσι, αυτό πρόκειται να πάρει πολύ γρήγορα λίγο κουραστικό, οπότε επιτρέψτε μου να σταματήσει αυτό για μια στιγμή.

632
00:37:08,750 --> 00:37:10,980
Επιτρέψτε μου να αλλάξετε την ταχύτητα να είναι πολύ πιο γρήγορα.

633
00:37:10,980 --> 00:37:15,380
Δεν είμαι αλλάζει τον αλγόριθμο, είμαι απλώς κάνοντας την κίνηση να συμβεί γρηγορότερα.

634
00:37:15,380 --> 00:37:18,410
Ακόμα είδος φούσκα, ίδιο αλγόριθμο,

635
00:37:18,410 --> 00:37:21,910
αλλά τώρα μπορείτε να δείτε πολύ πιο γρήγορα από ό, τι λεκτική επίδειξη μας

636
00:37:21,910 --> 00:37:25,900
ότι τα μεγαλύτερα στοιχεία πράγματι bubbling μέχρι την κορυφή.

637
00:37:25,900 --> 00:37:29,860
>> Ως μέρος, αυτά τα μικρά τετράγωνα στο κάτω αριστερά και κάτω δεξιά

638
00:37:29,860 --> 00:37:33,520
είναι απλώς λίγο υπενθυμίσεις για το πώς πολλές συγκρίσεις που κάνετε.

639
00:37:33,520 --> 00:37:37,620
Αλλά για τώρα, μπορούμε να επικεντρωθεί στην πυραμίδα που είναι να παίρνει μορφή, και εκεί πηγαίνει.

640
00:37:37,620 --> 00:37:41,510
Το μικρότερο στοιχείο είναι στα αριστερά, ο μεγαλύτερος στα δεξιά, και ό, τι άλλο στο μεταξύ.

641
00:37:41,510 --> 00:37:44,470
Τώρα, ας ρίξουμε μια ματιά, αντί στο είδος επιλογής.

642
00:37:44,470 --> 00:37:47,260
Πάω να προχωρήσει και να χτυπήσει στάση. Εμείς πάμε για να πάρετε μια νέα τυχαία σειρά από μπαρ.

643
00:37:47,260 --> 00:37:50,930
Είδος επιλογής, ανάκληση, περνά μέσα από τη λίστα ξανά και ξανά και ξανά,

644
00:37:50,930 --> 00:37:54,900
μάδημα το μικρότερο στοιχείο. Έτσι, εδώ είναι είδος επιλογής.

645
00:37:54,900 --> 00:37:58,390
Φαίνεται σαν να υπάρχει λιγότερη εργασία συμβαίνει τώρα, διότι δεν είμαστε συγκρίνοντας ζεύγη

646
00:37:58,390 --> 00:38:02,590
αλλά είμαστε ακριβώς το είδος του κεράσι πάρει τα μικρότερα στοιχεία από τα δεξιά προς τα αριστερά.

647
00:38:02,590 --> 00:38:06,890
Αυτό πήρε πολύ λίγο χρόνο, έτσι υπάρχει μια διχοτομία ήδη.

648
00:38:06,890 --> 00:38:11,820
Ακριβώς επειδή ένας αλγόριθμος λέγεται να τετράγωνο n φορά, όπως το είδος φούσκα

649
00:38:11,820 --> 00:38:16,100
και σαν είδος επιλογής, αυτά είναι πραγματικά χειρότερη περίπτωση χρόνους λειτουργίας.

650
00:38:16,100 --> 00:38:21,790
Για παράδειγμα, στην περίπτωση του, ας πούμε, το είδος επιλογής,

651
00:38:21,790 --> 00:38:27,240
Εγώ πραγματικά είμαι επιλέγοντας το μικρότερο άτομο και τη θέση σ 'αυτόν εδώ,

652
00:38:27,240 --> 00:38:29,620
τότε θα το κάνω και πάλι, τότε θα το κάνω και πάλι,

653
00:38:29,620 --> 00:38:32,070
αλλά υπήρξε μια μικρή βελτιστοποίηση θα μπορούσα να κάνω.

654
00:38:32,070 --> 00:38:35,040
>> Μόλις μετακόμισα εδώ τον αριθμό 1 - Sammy σε αυτή την περίπτωση -

655
00:38:35,040 --> 00:38:38,630
τι δεν πρέπει να κάνω μαζί του στη συνέχεια; >> [Φοιτητής] Αφήστε τον.

656
00:38:38,630 --> 00:38:40,140
Αφήστε τον, έτσι δεν είναι; Τίποτα.

657
00:38:40,140 --> 00:38:44,310
Δεν χρειάζεται να μιλήσουμε ποτέ για Sammy πάλι γιατί αν είχα επιλέξει το μικρότερο στοιχείο

658
00:38:44,310 --> 00:38:48,580
και τον έβαλε εδώ, γιατί ο χρόνος των αποβλήτων που καταλήγουν στο τέλος ολόκληρης της λίστας μου;

659
00:38:48,580 --> 00:38:54,590
Στην επόμενη επανάληψη πραγματικά επιτρέψτε μου να κινείται μόνο με τον αριθμό 2, μόνο για τον αριθμό 3.

660
00:38:54,590 --> 00:38:57,640
Έτσι, στην πραγματικότητα, εγώ δεν κάνει τα πράγματα n n φορές.

661
00:38:57,640 --> 00:39:05,380
Έκανα n πράγματα, τότε n - 1 πράγματα, τότε n - 2 πράγματα, τότε n - 3 πράγματα,

662
00:39:05,380 --> 00:39:07,080
τότε n - 4, τελεία, τελεία, τελεία.

663
00:39:07,080 --> 00:39:09,470
Έχουμε ένα κομμάτι από μια γεωμετρική σειρά, η οποία απλά σημαίνει

664
00:39:09,470 --> 00:39:11,450
είστε προσθέτοντας σταδιακά μικρότερους αριθμούς.

665
00:39:11,450 --> 00:39:17,940
Δεν n + n + n + n, αλλά ν + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
Και αυτό που γενικά λειτουργεί έξω για να είναι -

667
00:39:21,380 --> 00:39:24,280
Πάω να χαλάσουν σκάφους μου εδώ μόνο για μια στιγμή -

668
00:39:24,280 --> 00:39:28,990
που πρόκειται να λειτουργήσει έξω για να είναι κάτι σαν n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
αν έχουμε ακριβώς το είδος του εμφάνιση στο πίσω μέρος του βιβλίου μαθηματικών όπου έχετε όλα τα εξαπατήσει φύλλα

670
00:39:31,930 --> 00:39:33,410
για τους τύπους.

671
00:39:33,410 --> 00:39:37,760
Εάν θέλετε να προσθέσετε κάτι n + n - 1 + n - 2, λειτουργεί έξω για να είναι κάτι σαν αυτό.

672
00:39:37,760 --> 00:39:42,320
Και αν εμείς ακριβώς το είδος της πολλαπλασιάστε αυτό έξω, που είναι n τετράγωνο μείον n / 2.

673
00:39:42,320 --> 00:39:46,400
Συνέχισα λέγοντας n τετράγωνο, όμως, και αυτό είναι επειδή ήμουν το είδος της λήψης ενός ψυχική συντόμευση

674
00:39:46,400 --> 00:39:51,950
διότι στην πραγματικότητα, n τετράγωνο μείον ν διαιρείται με 2 είναι πράγματι ο πραγματικός αριθμός των βημάτων

675
00:39:51,950 --> 00:39:55,510
ότι ένας αλγόριθμος σαν είδος επιλογής θα πάρουμε αν πραγματικά υπολογίζονται μέχρι

676
00:39:55,510 --> 00:39:58,800
όλες αυτές τις συγκρίσεις και όλα τα μικρά απασχολημένος δουλειά που κάναμε.

677
00:39:58,800 --> 00:40:03,210
Αλλά ειλικρινά, όταν n παίρνει να είναι σαν ένα εκατομμύριο ή ένα δισεκατομμύριο, που στο καλό νοιάζεται

678
00:40:03,210 --> 00:40:07,160
αν κάνετε ένα δισεκατομμύριο τετράγωνο μείον ένα δισεκατομμύριο διαιρείται με το 2;

679
00:40:07,160 --> 00:40:09,320
Ένα δισεκατομμύριο τετράγωνο είναι ένας τεράστιος αριθμός.

680
00:40:09,320 --> 00:40:13,580
Μπορείτε να πάρετε ένα άλλο δις μακριά από αυτό με - n. Δεν είναι μια τέτοια μεγάλη υπόθεση.

681
00:40:13,580 --> 00:40:18,770
Έτσι, το μεγαλύτερο πάρει τους αριθμούς, είναι τα λιγότερο σημαντικά αυτά τα χαμηλότερα διέταξε όρους.

682
00:40:18,770 --> 00:40:24,230
Ποιος νοιάζεται αν διαιρέσετε με το 2, αν μιλάμε για quadrillions τον αριθμό των βημάτων;

683
00:40:24,230 --> 00:40:29,710
>> Έτσι, σε γενικές γραμμές, οι επιστήμονες ηλεκτρονικών υπολογιστών τείνουν να πετάξουν τα πάντα, αλλά το μεγαλύτερο όρος,

684
00:40:29,710 --> 00:40:33,140
και εμείς ακριβώς το είδος του απλοποιήσει τον κόσμο και να πω ότι ο αλγόριθμος

685
00:40:33,140 --> 00:40:38,130
πήρε περίπου τετράγωνο n βήματα. Αυτός είναι ο χρόνος εκτέλεσης ενός αλγορίθμου.

686
00:40:38,130 --> 00:40:40,760
Γι 'αυτό και θα επανέλθουμε σε αυτό σε μια στιγμή με μερικές συγκεκριμένα παραδείγματα,

687
00:40:40,760 --> 00:40:45,940
αλλά για τώρα, αυτό είναι το είδος της διαισθητικής κίνητρο πίσω ακριβώς απλούστευση κόσμο μας

688
00:40:45,940 --> 00:40:51,170
και μιλάμε για τους σημαντικότερους όρους, αντί να εμπλακούμε σε όλα αυτά τα φανταχτερά τους τύπους.

689
00:40:51,170 --> 00:40:53,540
Έτσι, αυτό ήταν το είδος επιλογής, και πήραμε λίγο τυχερός εκεί.

690
00:40:53,540 --> 00:40:57,360
Ας ρίξουμε μια ματιά στο είδος εισαγωγής. Επιτρέψτε μου να προχωρήσει και να αρχίσει αυτό το ένα, καθώς και.

691
00:40:57,360 --> 00:41:00,330
Τώρα παρατηρήσετε το μοτίβο που συμβαίνει είναι λίγο διαφορετικό,

692
00:41:00,330 --> 00:41:03,410
και αρχίσαμε με τυχαίους αριθμούς,

693
00:41:03,410 --> 00:41:06,890
αλλά αν θέλουμε πραγματικά μετράνε τον αριθμό των βημάτων στη χειρότερη περίπτωση,

694
00:41:06,890 --> 00:41:11,070
αν ο κατάλογος που ξεκίνησε εντελώς με τη σωστή σειρά,

695
00:41:11,070 --> 00:41:13,380
θα λάβουν μόνο n μέτρα για την επίτευξη τόσο πολύ.

696
00:41:13,380 --> 00:41:18,240
>> Αλλά εάν η λίστα ήταν πραγματικά προς τα πίσω - για παράδειγμα, σε αυτή την περίπτωση εδώ -

697
00:41:18,240 --> 00:41:23,860
τότε θα παρατηρήσετε πραγματικά πρέπει να κάνουμε πολλή δουλειά σε αυτή την περίπτωση.

698
00:41:23,860 --> 00:41:27,080
Και αυτό πρέπει να το είδος του αισθάνεται να σας αρέσει αυτό είναι το είδος της εργασίας σκληρότερα

699
00:41:27,080 --> 00:41:30,900
για να πάρει εκείνα τα μικρότερα στοιχεία προς τα αριστερά, και αυτό γιατί έχουμε άτυχος.

700
00:41:30,900 --> 00:41:34,210
Η λίστα ταξινομημένο κατά λάθος από την ανάποδη.

701
00:41:34,210 --> 00:41:38,110
Αντίθετα, με την εισαγωγή του είδους, αν μιμούνται ό, τι κάναμε με τους ανθρώπους μας εδώ

702
00:41:38,110 --> 00:41:42,670
ξεκινώντας με ταξινόμηση όλους και στη συνέχεια να ξεκινήσει, είναι ένα πολύ καλό αλγόριθμο, έτσι δεν είναι;

703
00:41:42,670 --> 00:41:45,010
Είναι ήδη, στην πραγματικότητα, με ταξινόμηση.

704
00:41:45,010 --> 00:41:48,670
Ας προσπαθήσουμε να συνοψίσουμε ακριβώς πόσο χρόνο αυτά τα πράγματα που μας

705
00:41:48,670 --> 00:41:52,360
εισάγοντας απλά ένα κομμάτι της αργκό ή συμβολισμό που είναι πραγματικά πολύ απλούστερο

706
00:41:52,360 --> 00:41:54,320
από το είδος του fanciness προτείνει.

707
00:41:54,320 --> 00:41:59,030
Αυτό το πράγμα εδώ, αυτό το μεγάλο O στην οθόνη, είναι ό, τι ένας επιστήμονας υπολογιστών θα χρησιμοποιούν γενικά

708
00:41:59,030 --> 00:42:03,640
για να περιγράψει την χειρότερη περίπτωση χρόνος εκτέλεσης ενός αλγορίθμου.

709
00:42:03,640 --> 00:42:07,360
>> Και πάλι, με χειρότερη περίπτωση, είναι εντελώς εξαρτάται από το πλαίσιο.

710
00:42:07,360 --> 00:42:10,890
Τι εννοούμε με τον όρο χειρότερη περίπτωση εντελώς ποικίλει ανάλογα με το πρόβλημα που μιλάμε.

711
00:42:10,890 --> 00:42:14,550
Αλλά στην περίπτωση της διαλογής, ποιο είναι το χειρότερο δυνατό σενάριο;

712
00:42:14,550 --> 00:42:17,860
Τα πάντα είναι προς τα πίσω, γιατί αισθάνεται σαν αυτό σημαίνει πολλή δουλειά για εμάς.

713
00:42:17,860 --> 00:42:21,330
Έχω καταλήξει σε μερικά από τα αλγόριθμοι που έχουμε δει μέχρι τώρα:

714
00:42:21,330 --> 00:42:24,930
γραμμική αναζήτηση, δυαδική αναζήτηση, όπως με τον τηλεφωνικό κατάλογο ή τα κομμάτια χαρτιού,

715
00:42:24,930 --> 00:42:28,960
τότε είδος bubble sort, ταξινόμηση επιλογή, εισαγωγή και όπως είδαμε με τους ανθρώπους μας,

716
00:42:28,960 --> 00:42:31,770
και στη συνέχεια, 1 άλλο που είναι τελικά πρόκειται να συγχωνευθούν είδος που ονομάζεται.

717
00:42:31,770 --> 00:42:37,710
Έτσι, σε γραμμική αναζήτηση, στη χειρότερη περίπτωση, πόσα βήματα χρειάζονται για να βρείτε τον αριθμό 7

718
00:42:37,710 --> 00:42:40,690
αν υπάρχουν n πόρτες, όπως ο Sean που αντιμετωπίζουν; >> [Φοιτητής] N.

719
00:42:40,690 --> 00:42:44,180
N. Έτσι θα πάμε για να γράψει μεγάλο Ο του n.

720
00:42:44,180 --> 00:42:47,010
Είμαι ακριβώς πρόκειται να συμπληρώσει ορισμένα κενά. Αυτό είναι μόνο ένα πλέγμα κενά.

721
00:42:47,010 --> 00:42:52,990
Όμως, στην καλύτερη περίπτωση με γραμμική αναζήτηση, 7 θα μπορούσε να έχει στην ίδια την αρχή της λίστας,

722
00:42:52,990 --> 00:42:55,520
και Sean μπορεί να έχουν αρχίσει να αναζητούν στην αρχή της λίστας.

723
00:42:55,520 --> 00:42:58,940
Έτσι, αν είστε με τη χρήση γραμμικής αναζήτησης και μόνο έλεγχο αριστερά προς τα δεξιά ή ίσως δεξιά προς τα αριστερά -

724
00:42:58,940 --> 00:43:02,650
ότι είναι ισοδύναμο - στην καλύτερη περίπτωση πόσα βήματα θα μπορούσε γραμμική αναζήτηση,

725
00:43:02,650 --> 00:43:05,550
όπως ο αλγόριθμος του Sean, να λάβει; Μόλις 1 βήμα.

726
00:43:05,550 --> 00:43:09,450
>> Έτσι, Πάω να πω ότι είναι ο συμβολισμός ωμέγα.

727
00:43:09,450 --> 00:43:11,570
Αυτό ακριβώς είναι ωμέγα πρωτεύουσα.

728
00:43:11,570 --> 00:43:15,000
Omega είναι μόνο η σέξι τρόπος για να πούμε καλύτερη περίπτωση διάρκειας.

729
00:43:15,000 --> 00:43:18,900
Έτσι στην καλύτερη περίπτωση ο χρόνος εκτέλεσης είναι ένα μοναδικό στάδιο ή σταθερό αριθμό βημάτων -

730
00:43:18,900 --> 00:43:24,270
1 στην περίπτωση αυτή - αλλά στη χειρότερη περίπτωση, μεγάλες O, είναι πραγματικά n βήματα.

731
00:43:24,270 --> 00:43:28,110
Και αυτό εδώ, θήτα, είμαστε στην πραγματικότητα δεν πρόκειται να δούμε τώρα.

732
00:43:28,110 --> 00:43:30,090
Δεν είναι σχετικό με το συγκεκριμένο παράδειγμα.

733
00:43:30,090 --> 00:43:31,990
Αλλά τώρα ας προσπαθήσουμε δυαδική αναζήτηση.

734
00:43:31,990 --> 00:43:35,990
Στη χειρότερη περίπτωση με δυαδική αναζήτηση, πόσα βήματα είναι αυτό πρόκειται να λάβει για να βρείτε τον αριθμό 7

735
00:43:35,990 --> 00:43:38,340
ή ό, τι ψάχνουμε; >> [Φοιτητής] Σύνδεση n.

736
00:43:38,340 --> 00:43:40,980
Ακόμα πρόκειται να λάβει n log επειδή ακριβώς όπως ο Alex πήρε άτυχος

737
00:43:40,980 --> 00:43:44,030
όταν εμείς πραγματικά εργάστηκαν με το πρόβλημα μεθοδικά

738
00:43:44,030 --> 00:43:48,220
και αυτή δεν βρείτε τον αριθμό 7 μέχρι την τελευταία πόρτα κοίταξε,

739
00:43:48,220 --> 00:43:51,720
αν και, για να είμαστε δίκαιοι, πήρε για να ρίξει μακριά ορισμένες πόρτες κατά μήκος του τρόπου,

740
00:43:51,720 --> 00:43:56,920
δυαδική αναζήτηση στη χειρότερη περίπτωση έχει ένα χρόνο λειτουργίας του log n.

741
00:43:56,920 --> 00:43:59,230
Και πάλι, αυτό μιλάει για αυτό διαίρεση και κατάκτηση.

742
00:43:59,230 --> 00:44:01,140
Αλλά τι γίνεται στην καλύτερη περίπτωση;

743
00:44:01,140 --> 00:44:04,790
Και ο Άλεξ γνώρισε πραγματικά ότι η καλύτερη περίπτωση το δικαίωμα, όταν ήρθε επάνω στη σκηνή.

744
00:44:04,790 --> 00:44:07,290
Πόσα βήματα έκανε ότι λαμβάνουν σε δυαδική αναζήτηση; >> [Φοιτητής] 1.

745
00:44:07,290 --> 00:44:09,380
1, μόνο και μόνο επειδή πήρε τυχερός.

746
00:44:09,380 --> 00:44:12,520
Αλλά αυτό είναι εντάξει, επειδή αναφέρεται σε ωμέγα καλύτερα σενάρια,

747
00:44:12,520 --> 00:44:15,770
καλύτερα τις εισροές περίπτωση, ακόμα κι αν είναι απλά τυχαία τύχη.

748
00:44:15,770 --> 00:44:18,900
>> Τώρα, κι αυτό θα πάμε να ακριβώς το είδος της άδειας κενό για τώρα.

749
00:44:18,900 --> 00:44:21,010
Τι θα λέγατε τώρα είδος φούσκα;

750
00:44:21,010 --> 00:44:24,290
Στη χειρότερη περίπτωση με bubble sort, ο καθένας είναι σε αντίστροφη σειρά,

751
00:44:24,290 --> 00:44:26,380
έτσι πρέπει να κάνουμε πολλά φυσαλίδων.

752
00:44:26,380 --> 00:44:30,190
Αλλά πόσα βήματα είναι ότι πρόκειται να πάρει στη χειρότερη περίπτωση; >> [Φοιτητής] Ν τετράγωνο.

753
00:44:30,190 --> 00:44:32,550
Αυτό ήταν το n τετράγωνο, γιατί αν το καλοσκεφτείς,

754
00:44:32,550 --> 00:44:36,410
αν η λίστα είναι εντελώς προς τα πίσω - 8 είναι πάνω από εδώ, πάνω από 1 είναι εδώ -

755
00:44:36,410 --> 00:44:40,530
ως πράγμα να αρχίσει να φούσκα, ο αριθμός 8 πρόκειται να κινηθεί με αυτό τον τρόπο, με τον τρόπο αυτό,

756
00:44:40,530 --> 00:44:44,540
αυτόν τον τρόπο, με αυτόν τον τρόπο, αλλά πού είναι το νούμερο 7 στη χειρότερη περίπτωση;

757
00:44:44,540 --> 00:44:47,720
Εδώ είναι ακόμα εκεί. Γι 'αυτό και πρέπει να το κάνουμε ξανά και ξανά.

758
00:44:47,720 --> 00:44:53,190
Και αυτό είναι όπου έχουμε n βήματα, τότε n - 1 βήματα, τότε n - 2 βήματα.

759
00:44:53,190 --> 00:44:55,960
Και αν πάρετε τη λέξη μου για αυτό - ότι αν το είδος αυτό πολλαπλασιάζονται,

760
00:44:55,960 --> 00:45:00,110
αυτό είναι περίπου n τετράγωνο στο τέλος με κάποιους άλλους όρους που θα αγνοήσει απλά για τώρα -

761
00:45:00,110 --> 00:45:06,890
τότε στη χειρότερη περίπτωση ταξινόμησης φυσαλίδας είναι ν τετράγωνο, ή να δώσει.

762
00:45:06,890 --> 00:45:09,490
Αλλά τι γίνεται με την καλύτερη περίπτωση με τέτοια φούσκα;

763
00:45:09,490 --> 00:45:13,050
Ποιο είναι το καλύτερο σενάριο; Όλοι οι αριθμοί είναι ήδη ταξινομημένο.

764
00:45:13,050 --> 00:45:15,920
Και ποια ήταν η ευρετική που χρησιμοποιείται, το τέχνασμα που χρησιμοποιείται,

765
00:45:15,920 --> 00:45:20,110
να συνειδητοποιήσει ότι είχα κάνει καμία εργασία και ως εκ τούτου θα μπορούσε να σταματήσει νωρίς;

766
00:45:20,110 --> 00:45:23,590
[Φοιτητής] Δείτε το μια φορά. >> Δείτε το μια φορά. Αλλά αυτό που έκανα κατά μήκος του τρόπου;

767
00:45:23,590 --> 00:45:26,130
Είχα την παρακολούθηση του πόσα swaps που έκανα.

768
00:45:26,130 --> 00:45:30,650
Και κατάλαβα αν δεν έχω κανένα swaps υπολογίζονται στα δάχτυλά μου, τότε έχω κάνει καμία εργασία.

769
00:45:30,650 --> 00:45:34,300
Σίγουρα δεν θα πρέπει να προσπαθήσουμε να κάνουμε καμία δουλειά και πάλι, έτσι μπορώ ακριβώς να σταματήσω.

770
00:45:34,300 --> 00:45:37,830
>> Έτσι, στην καλύτερη περίπτωση του bubble sort, όταν η λίστα είναι ήδη ταξινομημένο,

771
00:45:37,830 --> 00:45:41,530
τι θα λέγατε ότι ο συμβολισμός είναι ωμέγα, η καλύτερη περίπτωση διάρκειας;

772
00:45:41,530 --> 00:45:48,040
Είναι ακριβώς n. Πρέπει να κάνουμε κάποια δουλειά, αλλά δεν έχουμε παρά να κάνουμε αξίας 1 βόλτα του έργου.

773
00:45:48,040 --> 00:45:50,490
Και εδώ θα πάω να αφήσετε κενό αυτό το μέρος.

774
00:45:50,490 --> 00:45:52,430
Και τώρα είδος επιλογής.

775
00:45:52,430 --> 00:45:56,010
Η επιλογή του είδους είχε με το μάδημα το μικρότερο άτομο ξανά και ξανά.

776
00:45:56,010 --> 00:45:58,380
Και τι να πούμε ο χρόνος εκτέλεσης του ότι ήταν;

777
00:45:58,380 --> 00:46:00,590
Αυτό ήταν ν τετράγωνο στη χειρότερη περίπτωση.

778
00:46:00,590 --> 00:46:05,220
Και δυστυχώς, στην καλύτερη περίπτωση είναι επίσης n τετράγωνο

779
00:46:05,220 --> 00:46:08,840
επειδή δεν έχω το είδος του παντογνώστη θέα όλου του κόσμου?

780
00:46:08,840 --> 00:46:13,140
Το μόνο που ξέρω από την πλήρη επανάληψη ότι έχω βρεθεί πράγματι το μικρότερο άτομο.

781
00:46:13,140 --> 00:46:15,860
Έτσι, το είδος είδος της επιλογής χάλια με αυτή την έννοια,

782
00:46:15,860 --> 00:46:17,920
αλλά το θετικό είναι το είδος της διαισθητική.

783
00:46:17,920 --> 00:46:21,470
Είναι αρκετά εύκολο να κωδικοποιήσει έως διότι το μόνο που έχετε να κάνετε είναι να γράψετε ένα ζευγάρι των ένθετων για βρόχους,

784
00:46:21,470 --> 00:46:24,620
κατά κανόνα, που περνά μέσα από ψάχνει για το μικρότερο στοιχείο

785
00:46:24,620 --> 00:46:27,840
και στη συνέχεια τοποθετεί το μικρότερο στοιχείο όπου ανήκει στο τέλος της λίστας.

786
00:46:27,840 --> 00:46:29,900
Έτσι, εδώ υπάρχει πρόκειται να είναι ένα trade-off.

787
00:46:29,900 --> 00:46:34,440
Η ποσότητα του χρόνου που χρειάζεται για να σκεφτούν και να αναπτυχθούν πραγματικά κάτι από τη σύνταξη κώδικα

788
00:46:34,440 --> 00:46:39,460
θα μπορούσε κάλλιστα να πάρει περισσότερο χρόνο, αν θέλετε μια καλύτερη αλγόριθμος και ταχύτερη απόδοση.

789
00:46:39,460 --> 00:46:41,780
>> Αλλά αν πραγματικά ακριβώς το είδος του κώδικα μέχρι κάτι γρήγορο και βρώμικο

790
00:46:41,780 --> 00:46:45,000
και ακριβώς το είδος του να το χαζό δυνατή ιδέα που μπορείτε να σκεφτείτε,

791
00:46:45,000 --> 00:46:47,580
που θα μπορούσε να σας πάρει μερικά λεπτά για να κώδικα, αλλά με μεγάλα σύνολα δεδομένων

792
00:46:47,580 --> 00:46:49,580
αλγόριθμος σας μπορεί να πάρει ώρες για να τρέξει.

793
00:46:49,580 --> 00:46:51,690
Και ακόμα κι εγώ σε μεταπτυχιακό σχολείο θα κάνει μερικές φορές αυτά τα ανταλλάγματα.

794
00:46:51,690 --> 00:46:55,660
Θα ήταν τρεις, ήμουν προσπαθεί να αναλύσει κάποια πολύ μεγάλο σύνολο δεδομένων

795
00:46:55,660 --> 00:46:59,650
που σχετίζονται με την έρευνα για την ασφάλεια που έκανα, και είχε δαπανήσει ούτε 5 λεπτά

796
00:46:59,650 --> 00:47:03,210
μικροαλλαγές το πρόγραμμά μου για να αναλύσει τα δεδομένα και να πάει για ύπνο

797
00:47:03,210 --> 00:47:08,420
ή να περάσουν 8 ώρες να πάρει ακριβώς δεξιά έτσι ώστε να τρέχει αμέσως και να μην πάει για ύπνο.

798
00:47:08,420 --> 00:47:10,530
Και έτσι εκεί είναι το είδος της μια συνειδητή απόφαση.

799
00:47:10,530 --> 00:47:12,740
Λιγότερο χρόνο ανάπτυξης, περισσότερο ύπνο.

800
00:47:12,740 --> 00:47:14,780
Εκ των υστέρων, εγώ κατά πάσα πιθανότητα δεν θα πρέπει να ενθαρρύνουν

801
00:47:14,780 --> 00:47:19,120
όταν ο στόχος εδώ είναι να βελτιστοποιηθεί η ποιότητα του κώδικα,

802
00:47:19,120 --> 00:47:21,280
αλλά επίσης ότι στον πραγματικό κόσμο είναι ένα πολύ λογικό trade-off.

803
00:47:21,280 --> 00:47:25,130
Λιγότερο χρόνο, μικρότερη απόδοση ή το αντίστροφο.

804
00:47:25,130 --> 00:47:28,110
Έτσι, εδώ έχουμε επιτέλους την ευκαιρία να μιλήσουμε για θήτα.

805
00:47:28,110 --> 00:47:32,830
Theta συμβολισμός είναι κάτι που οι επιστήμονες ηλεκτρονικών υπολογιστών μπορεί να φέρει σε συνομιλία

806
00:47:32,830 --> 00:47:36,160
όταν μεγάλες O και ωμέγα τυχαίνει να είναι το ίδιο.

807
00:47:36,160 --> 00:47:40,160
Λέτε θήτα να στείλετε πραγματικά το μήνυμα ότι αυτό είναι ένα είδος δεσμεύεται σφιχτά.

808
00:47:40,160 --> 00:47:43,340
Δεν έχει σημασία αν το σενάριο είναι καλό ή κακό, είναι n τετράγωνο.

809
00:47:43,340 --> 00:47:46,510
Γι 'αυτό ακριβώς δεν έχει σημασία σε αυτές τις ιστορίες εδώ.

810
00:47:46,510 --> 00:47:48,560
Εισαγωγή είδος είναι το τελευταίο εξετάσαμε,

811
00:47:48,560 --> 00:47:50,830
όπου ήμουν εισάγοντας απλώς ο καθένας στο σωστό μέρος.

812
00:47:50,830 --> 00:47:54,930
Στην καλύτερη περίπτωση αυτό που ήταν ο χρόνος εκτέλεσης της εισαγωγής του είδους, όπως το είδαμε εδώ;

813
00:47:54,930 --> 00:47:57,250
[Φοιτητής] Η καλύτερη περίπτωση; >> Η καλύτερη περίπτωση.

814
00:47:57,250 --> 00:48:00,100
>> Ήταν n γιατί στην καλύτερη περίπτωση ταξινομημένο σε όλους,

815
00:48:00,100 --> 00:48:02,580
και Sammy και κανένας άλλος πραγματικά έπρεπε να κινηθεί καθόλου.

816
00:48:02,580 --> 00:48:04,610
Είχαν ήδη σε σωστή θέση τους.

817
00:48:04,610 --> 00:48:08,570
Έτσι ταξινόμηση με εισαγωγή στην καλύτερη περίπτωση είναι, στην περίπτωση αυτή, n.

818
00:48:08,570 --> 00:48:12,770
Όμως, στη χειρότερη περίπτωση είναι το είδος του n στο τετράγωνο. Γιατί;

819
00:48:12,770 --> 00:48:16,230
Αν μου λίστα των ανθρώπων είναι σε αντίστροφη σειρά,

820
00:48:16,230 --> 00:48:21,260
Εγώ για πρώτη φορά με τον αριθμό 8 και θα τον τοποθετήσετε ή την στη σωστή θέση, η οποία είναι ακριβώς εδώ.

821
00:48:21,260 --> 00:48:25,270
Ι το είδος της κίνησης προς την πλευρά. Αυτά τα παιδιά που έχουν υποστεί διαλογή, ή αυτή είναι ταξινομημένο.

822
00:48:25,270 --> 00:48:28,970
Τώρα, όμως, τυχαίνει να βρει ποιος το επόμενο βήμα; >> [Φοιτητής] 7.

823
00:48:28,970 --> 00:48:31,250
7 στην χειρότερη περίπτωση, επειδή είναι σε αντίστροφη σειρά.

824
00:48:31,250 --> 00:48:34,920
>> Έτσι, εδώ είναι 7. Σε περίπτωση που δεν ανήκουν 7; Σίγουρα πίσω μου.

825
00:48:34,920 --> 00:48:39,460
Αλλά τώρα 7 ανήκει στην πραγματικότητα δεν είναι ακριβώς πίσω από μένα, αλλά πίσω από τον αριθμό 8,

826
00:48:39,460 --> 00:48:41,880
έτσι έχω να πω, "Με συγχωρείτε, αριθμός 8, μπορείτε σας παρακαλώ να προχωρήσουμε με αυτόν τον τρόπο

827
00:48:41,880 --> 00:48:44,640
"Για να δημιουργηθεί χώρος για 7;" Τώρα έχω συναντήσει 6.

828
00:48:44,640 --> 00:48:48,530
"Ω, με συγχωρείτε, τον αριθμό 8 και τον αριθμό 7, μπορείτε να μετακινηθείτε για να δημιουργηθεί χώρος για 6;"

829
00:48:48,530 --> 00:48:52,360
Έτσι με άλλα λόγια, με την εισαγωγή του είδους, ακόμη και αν δεν κάνω πολύ κίνηση,

830
00:48:52,360 --> 00:48:56,330
οι άνθρωποι πίσω μου κάνουν πολύ περισσότερη δουλειά, και που πήρε χρόνο να κοστίσει κάποιον.

831
00:48:56,330 --> 00:48:58,000
Είναι πρόκειται να κοστίσει την ώρα του υπολογιστή.

832
00:48:58,000 --> 00:49:01,450
Έτσι, στην περίπτωση της εισαγωγής του είδους που εξακολουθούν να υποφέρουν.

833
00:49:01,450 --> 00:49:06,260
Αν ξεκινήσετε προσθέτοντας τον συνολικό αριθμό των βημάτων, καταλήγουμε να χτυπήσει περίπου n τετράγωνο

834
00:49:06,260 --> 00:49:11,160
επειδή αυτοί οι τύποι πρέπει να δημιουργηθεί χώρος για την ανθρώπινη να εισαχθεί ξανά σε αυτόν τον κατάλογο.

835
00:49:11,160 --> 00:49:15,960
Και έτσι σε αυτή την περίπτωση θήτα είναι απλώς δεν ισχύει για τη συγκεκριμένη ιστορία στο χέρι.

836
00:49:15,960 --> 00:49:21,100
Αυτό είναι όλα ωραία και καλά. Έχουμε αυτά τα 3 διαφορετικοί τρόποι να μιλάμε για το χρόνο λειτουργίας.

837
00:49:21,100 --> 00:49:26,370
Αλλά τι ακριβώς σημαίνει αυτό σε πραγματικούς όρους, αν πραγματικά προσπαθήσει να κωδικοποιήσει έως έναν αλγόριθμο;

838
00:49:26,370 --> 00:49:31,620
>> Επιτρέψτε μου να προτείνω ότι υπάρχει ένα ακόμα καλύτερο αλγόριθμο εκεί έξω

839
00:49:31,620 --> 00:49:33,740
ότι η ίδια έχει κάποια ανταλλάγματα.

840
00:49:33,740 --> 00:49:36,890
Εμείς πάμε για να καλέσετε το είδος συγχώνευσης, και αυτό είναι το είδος του αυτό το μαγικό αλγόριθμο

841
00:49:36,890 --> 00:49:42,840
που λειτουργεί ακριβώς γρηγορότερα με κάποιο τρόπο, και είναι τόσο εύκολο να εκφράσει, τουλάχιστον σε ψευδοκώδικα.

842
00:49:42,840 --> 00:49:46,900
Η εφαρμογή αυτού του είδους συγχώνευσης αλγόριθμος πρόκειται να είναι ως εξής.

843
00:49:46,900 --> 00:49:50,860
Όταν σας δίνεται n στοιχεία - αριθμούς n, n οι άνθρωποι, ό, τι - πρώτα υπάρχει μια λογική ελέγχου.

844
00:49:50,860 --> 00:49:56,340
Αν το n είναι μικρότερο από 2, συγχώνευση είδος σταματά ακριβώς. Επιστρέφει, να το πω έτσι.

845
00:49:56,340 --> 00:50:00,830
Γιατί θα σταματήσει αν το n είναι μικρότερο από το 2; >> [Ακούγεται ανταπόκριση των φοιτητών]

846
00:50:00,830 --> 00:50:04,480
Δεξιά. Και πάλι, το η δεν είναι ο αριθμός στη λίστα, n είναι το μέγεθος του καταλόγου.

847
00:50:04,480 --> 00:50:07,660
Εάν το n είναι μικρότερο από 2, αυτό σημαίνει ότι η λίστα σας είναι είτε 1,

848
00:50:07,660 --> 00:50:09,640
Όπου και αν προφανώς ταξινομημένο αν είναι 1 αριθμός,

849
00:50:09,640 --> 00:50:11,710
ή 0, οπότε δεν υπάρχει τίποτα για να ταξινομήσετε,

850
00:50:11,710 --> 00:50:13,570
γι 'αυτό χρειαζόμαστε αυτό το είδος της υπόθεσης βάσης.

851
00:50:13,570 --> 00:50:20,350
Εάν η λίστα είναι τόσο μικρή που δεν υπάρχει τίποτε άλλο να κάνεις, κυριολεκτικά δεν κάνουν τίποτα. Επιστροφή.

852
00:50:20,350 --> 00:50:25,090
Διαφορετικά ταξινομήσετε το αριστερό μισό των στοιχείων, τότε ταξινομήσετε το δεξί ήμισυ από τα στοιχεία,

853
00:50:25,090 --> 00:50:27,410
μετά τη συγχώνευση τα 2 ημίχρονα ταξινομημένο.

854
00:50:27,410 --> 00:50:32,130
>> Αυτό το είδος του φαίνεται σαν μια μικρή εξαπατήσει το οποίο ρωτάω πώς να ταξινομήσετε τα στοιχεία

855
00:50:32,130 --> 00:50:34,900
και μου λες, "Ταξινομήστε το αριστερό μισό, ταξινομήστε το δεξιό μισό."

856
00:50:34,900 --> 00:50:37,240
Είμαι όπως, «Εντάξει. Πώς μπορείτε να ταξινομήσετε το αριστερό μισό;"

857
00:50:37,240 --> 00:50:40,670
"Ξεχωρίστε το αριστερό μισό του αριστερό μισό, το δικαίωμα ταξινομήσετε μισό του αριστερό μισό, και στη συνέχεια να γίνει."

858
00:50:40,670 --> 00:50:44,060
Είσαι το είδος του κυκλικά τον καθορισμό του τι σημαίνει να ταξινομήσετε,

859
00:50:44,060 --> 00:50:46,790
αλλά αποδεικνύεται ότι είναι πραγματικά λαμπρή σε αυτή την περίπτωση.

860
00:50:46,790 --> 00:50:50,230
Δεν είναι πραγματικά αυτός ο φαύλος κύκλος που δεν τελειώνει ποτέ

861
00:50:50,230 --> 00:50:52,550
επειδή δεν τελειώνει όταν; >> [Φοιτητής] Όταν φθάσει το 1 πράγμα.

862
00:50:52,550 --> 00:50:54,220
Όταν φθάσει το 1 πράγμα.

863
00:50:54,220 --> 00:50:57,850
Έτσι, ακόμα κι αν θα μπορούσε να ξεκινήσει με 8 άτομα και λέω, "Ταξινομήστε το αριστερό ήμισυ των ατόμων αυτών,

864
00:50:57,850 --> 00:51:00,480
αυτά τα 4 άτομα, "τότε λέω,« Πώς μπορείτε να ταξινομήσετε το αριστερό μισό; "

865
00:51:00,480 --> 00:51:03,450
"Λοιπόν, να ταξινομήσετε τις 2 άτομα εδώ." Και τότε θα είστε όπως, «Εντάξει, εντάξει."

866
00:51:03,450 --> 00:51:05,520
"Πώς μπορείτε να ταξινομήσετε το αριστερό μισό από αυτούς τους ανθρώπους;"

867
00:51:05,520 --> 00:51:09,040
"Ακριβώς αυτό ταξινομήσετε 1 άτομο εδώ." Ποια είναι η λαμπρή αποκάλυψη τώρα;

868
00:51:09,040 --> 00:51:13,050
Θα πρέπει να ταξινομήσετε 1 άτομο. Τέλος. Δεν έχω να κάνω οποιαδήποτε εργασία.

869
00:51:13,050 --> 00:51:16,580
Αλλά τώρα έχω να ταξινομήσετε αυτό το πρόσωπο, αλλά είναι ένα μεμονωμένο άτομο, να κάνει τίποτα.

870
00:51:16,580 --> 00:51:21,490
>> Έτσι, η μαγεία είναι προφανώς σε αυτό το τρίτο βήμα: τη συγχώνευση των ταξινομημένο μισά.

871
00:51:21,490 --> 00:51:25,770
Έτσι συγχώνευση είδος παίρνει αυτή την λαμπρή ιδέα ότι, αν σπάσει ένα μεγάλο πρόβλημα κάτω

872
00:51:25,770 --> 00:51:28,650
σε 2 μικρότερα, όμοια σε μέγεθος προβλήματα

873
00:51:28,650 --> 00:51:32,710
και στη συνέχεια, ακριβώς το είδος της κόλλας οι μικρότερες λύσεις μαζί στο τέλος,

874
00:51:32,710 --> 00:51:34,720
Προτείνω ότι μπορούμε να κάνουμε πολλά, πολύ καλύτερα [χτυπώντας ήχο]

875
00:51:34,720 --> 00:51:38,050
από οποιοδήποτε είδος ή είδος επιλογής εισαγωγής.

876
00:51:38,050 --> 00:51:40,690
Έχω πράγματι αγνοώντας ότι για μισή ώρα, αλλά εγώ πραγματικά δεν ξέρω τι συμβαίνει

877
00:51:40,690 --> 00:51:45,040
έξω σήμερα. [Βουητό] [γέλια]

878
00:51:45,040 --> 00:51:49,660
Ας δούμε αν μπορούμε να δούμε αυτό με μια μικρή βοήθεια από τον φίλο μας τον Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Υπάρχουν 2 μεγάλα βήματα στη διαδικασία της συγχώνευσης είδος.

880
00:51:52,810 --> 00:51:56,400
Κατ 'αρχάς, χωρίζεται συνεχώς τον κατάλογο των κυπέλλων στη μέση

881
00:51:56,400 --> 00:51:59,610
μέχρι να έχουμε ένα σωρό λίστες με μόλις 1 φλιτζάνι σε αυτά.

882
00:51:59,610 --> 00:52:02,150
Μην ανησυχείτε εάν η λίστα περιέχει περιττό αριθμό

883
00:52:02,150 --> 00:52:04,830
και δεν μπορείτε να κάνετε μια απόλυτα καθαρή κοπή μεταξύ τους.

884
00:52:04,830 --> 00:52:08,740
Απλά επιλέξτε αυθαίρετα ποια λίστα να περιλαμβάνει το επιπλέον φλιτζάνι μέσα

885
00:52:08,740 --> 00:52:11,320
Ας χωρίσει τους καταλόγους αυτούς.

886
00:52:12,420 --> 00:52:14,570
Τώρα έχουμε 2 λίστες.

887
00:52:18,930 --> 00:52:20,930
Τώρα έχουμε 4 λίστες.

888
00:52:25,730 --> 00:52:28,740
Τώρα έχουμε 8 λίστες με ένα μόνο φλιτζάνι σε κάθε λίστα.

889
00:52:28,740 --> 00:52:31,520
Έτσι, αυτό είναι όλο για το βήμα 1.

890
00:52:31,520 --> 00:52:37,280
Για το βήμα 2 θα συγχωνευθούν επανειλημμένα ζεύγη λίστες χρησιμοποιώντας τον αλγόριθμο συγχώνευσης μάθαμε πριν.

891
00:52:37,280 --> 00:52:44,320
Συγχώνευση 108 και 15 καταλήγουμε με τον κατάλογο 15, 108.

892
00:52:45,240 --> 00:52:51,330
Συγχώνευση 50 και 4 καταλήγουμε με 4, 50.

893
00:52:51,330 --> 00:52:56,950
Συγχώνευση 8 και 42 καταλήγουμε με 8, 42.

894
00:52:57,790 --> 00:53:04,360
Και τη συγχώνευση 23 και 16 καταλήγουμε με 16, 23.

895
00:53:04,360 --> 00:53:08,030
Τώρα όλες τις λίστες μας είναι το μέγεθος 2.

896
00:53:08,030 --> 00:53:10,980
Παρατηρήστε ότι κάθε ένα από τα 4 καταλόγων ταξινόμηση,

897
00:53:10,980 --> 00:53:14,230
έτσι μπορούμε να αρχίσουμε τη συγχώνευση ζεύγη των καταλόγων και πάλι.

898
00:53:14,230 --> 00:53:22,150
Συγχώνευση 15 και 108 και 4 και 50 παίρνουμε πρώτα το 4, τότε το 15,

899
00:53:22,150 --> 00:53:26,250
τότε το 50, τότε το 108.

900
00:53:26,250 --> 00:53:33,020
Συγχωνευόμενες 8, 42 και 16, 23 παίρνουμε πρώτα το 8, τότε το 16,

901
00:53:33,020 --> 00:53:37,170
τότε το 23, τότε το 42.

902
00:53:37,170 --> 00:53:42,490
Έτσι τώρα έχουμε μόλις 2 καταλόγους μεγέθους 4, καθένα από τα οποία είναι ταξινομημένο.

903
00:53:42,490 --> 00:53:45,940
Έτσι τώρα έχουμε συγχωνεύσει αυτά τα 2 λίστες.

904
00:53:45,940 --> 00:53:54,230
Πρώτα παίρνουμε το 4, τότε παίρνουμε το 8, τότε παίρνουμε το 15

905
00:53:54,230 --> 00:54:05,280
και 16 και 23 και 42 και 50 και 108.

906
00:54:05,280 --> 00:54:09,020
Και τελειώσαμε. Έχουμε τώρα μια ταξινομημένη λίστα.

907
00:54:09,020 --> 00:54:13,740
>> Rob ήταν το είδος της εκμεταλλευόμενοι κάτι που δεν το έχουν πράξει ακόμη.

908
00:54:13,740 --> 00:54:16,540
Προτάθηκε, αλλά εμείς δεν το κάνουμε πραγματικότητα.

909
00:54:16,540 --> 00:54:19,230
Ήταν κάτι φυσικά με τα κύπελλα που προτείνει

910
00:54:19,230 --> 00:54:23,680
ξόδευε κάποια πηγή εκτός από το χρόνο. >> [Φοιτητής] Space. >> Ήταν χώρο.

911
00:54:23,680 --> 00:54:27,360
Το γεγονός ότι είχε αυτό το είδος της δι-επίπεδο τραπέζι όπου είχε χώρο εδώ

912
00:54:27,360 --> 00:54:31,960
και το χώρο κάτω εδώ ήταν πραγματικά πράγμα που σημαίνει ότι είναι με το διπλάσιο χώρο

913
00:54:31,960 --> 00:54:36,390
όπως κάθε αλγορίθμων μας μέχρι στιγμής - είδος εισαγωγής, είδος φούσκα, ή την επιλογή του είδους -

914
00:54:36,390 --> 00:54:40,780
αλλά ήταν μόχλευση αυτή την επιπλέον χώρο για το είδος των πραγμάτων κίνηση εμπρός και πίσω

915
00:54:40,780 --> 00:54:42,600
διατηρώντας παράλληλα τα πράγματα σε τάξη.

916
00:54:42,600 --> 00:54:47,540
Και ακόμα κι αν αισθάνεται σαν να έχεις σε μια ταξινομημένη λίστα, που αισθάνθηκε σαν να πήρε λίγο χρόνο.

917
00:54:47,540 --> 00:54:51,060
Στην πραγματικότητα, αυτό που έκανε ο Rob ήταν ακριβώς αυτός ο αλγόριθμος.

918
00:54:51,060 --> 00:54:56,780
Πήρε πρώτα το πρόβλημα μεγέθους n, διαιρείται το σε ένα αριστερό μισό και το δεξί μισό.

919
00:54:56,780 --> 00:54:59,380
Αυτό είναι όταν μετακόμισε τα κύπελλα. Στη συνέχεια, επανέλαβε ότι η διαδικασία.

920
00:54:59,380 --> 00:55:03,390
Χώρισε 4 σε 2 σετ από 2 εδώ και εδώ.

921
00:55:03,390 --> 00:55:08,520
Στη συνέχεια, επανέλαβε ότι η διαδικασία χωρίζεται και 2 σε 2 σετ από 1 για καθένα από αυτά τα διάφορα κύπελλα.

922
00:55:08,520 --> 00:55:11,000
Και αυτό είναι όπου η λαμπρή ευκαιρία.

923
00:55:11,000 --> 00:55:15,840
Σε εκείνο το σημείο στην ιστορία, ο Rob είχε 8 λίστες του μεγέθους 1,

924
00:55:15,840 --> 00:55:18,860
όλα από τα οποία είχαν ήδη ταξινόμηση.

925
00:55:18,860 --> 00:55:20,630
>> Και τότε τι έκανε προχωρήσει να κάνει;

926
00:55:20,630 --> 00:55:25,260
Ζεύγη πήρε αυτή την ταξινομημένη λίστα και αυτή την ταξινομημένη λίστα και συγχώνευση τους.

927
00:55:25,260 --> 00:55:28,200
Στη συνέχεια, πήρε το ένα και συγχώνευσε τους, τότε αυτό το ένα και συγχώνευση τους,

928
00:55:28,200 --> 00:55:30,670
τότε αυτό και τους συγχωνεύονται.

929
00:55:30,670 --> 00:55:32,390
Και τότε τι έκανε το επόμενο βήμα;

930
00:55:32,390 --> 00:55:36,580
Στη συνέχεια εκ νέου συγχώνευσε τις μεγαλύτερες λίστες και στη συνέχεια εκ νέου συγχώνευσε τις μεγαλύτερες λίστες.

931
00:55:36,580 --> 00:55:41,170
Και αν νομίζετε ότι για αυτό ακριβώς διαισθητικά για τώρα, τι πραγματικά κάνει ο ίδιος;

932
00:55:41,170 --> 00:55:45,450
Ήταν διαιρώντας το πρόβλημα σε ένα δεύτερο, κατά το ήμισυ, σε ένα δεύτερο, σε ένα δεύτερο

933
00:55:45,450 --> 00:55:47,600
για να πάρει αυτά τα μικρά σούπερ λίστες.

934
00:55:47,600 --> 00:55:51,290
Τότε ήταν το είδος του συνδυασμού διπλό, διπλό, διπλό, διπλό.

935
00:55:51,290 --> 00:55:54,120
Έτσι έκανε το διπλάσιο έργο όπως έχουμε δει μέχρι στιγμής

936
00:55:54,120 --> 00:55:56,930
με οτιδήποτε συνεπάγεται διαίρει και βασίλευε, αλλά δεν είναι μεγάλη υπόθεση.

937
00:55:56,930 --> 00:55:59,630
Δύο φορές όσο η εργασία δεν είναι μια τέτοια μεγάλη υπόθεση. Είναι απλά ένα σταθερό παράγοντα.

938
00:55:59,630 --> 00:56:03,920
Και σαν έκφραση αριθμητική μας πριν, είμαι απλώς πρόκειται να περάσουν από σταθερούς παράγοντες

939
00:56:03,920 --> 00:56:10,170
όπως φορές 2. Ποιος νοιάζεται; Αν είναι 2 δισεκατομμύρια φορές 2, που είναι ακόμα πολλά βήματα.

940
00:56:10,170 --> 00:56:13,160
Έτσι, αυτή η συγχώνευση βήμα φαίνεται να είναι η βασική εικόνα.

941
00:56:13,160 --> 00:56:17,000
Ας δούμε αυτό ακριβώς αριθμητικά πριν - Ω, αυτό δεν είναι για να συνεχιστεί ακόμα.

942
00:56:17,000 --> 00:56:22,890
Ας δούμε αυτό μόνο αριθμητικά πραγματικά να δούμε πώς αυτό παίζει έξω.

943
00:56:22,890 --> 00:56:25,940
Αυτό είναι ως επί το πλείστον μόνο κίνηση ενός μικρού φτωχού.

944
00:56:25,940 --> 00:56:27,750
Ας προτείνουν αυτό.

945
00:56:27,750 --> 00:56:31,480
Ο χρόνος εκτέλεσης του είδους συγχώνευση - χρειαζόμαστε μόνο έναν τρόπο να μιλάμε γι 'αυτό.

946
00:56:31,480 --> 00:56:34,380
Αυτό δεν είναι μαθηματικά? Αυτό είναι ακριβώς το είδος του τρόπο συνοπτικό της εκφραζόμαστε.

947
00:56:34,380 --> 00:56:39,080
Έτσι Τ αντιπροσωπεύει το χρόνο και ν αντιπροσωπεύει ό, τι; >> [Φοιτητής] Το μέγεθος του -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] Το μέγεθος του προβλήματος, ο αριθμός των ανθρώπων.

949
00:56:41,400 --> 00:56:45,470
Έτσι είμαι υποστηρίζοντας ότι ο χρόνος εκτέλεσης να ταξινομήσετε n άνθρωποι πρόκειται να είναι 0 χρονικό διάστημα

950
00:56:45,470 --> 00:56:50,290
αν το n είναι μικρότερο από 2, γιατί αν έχετε 1 φλιτζάνι ή δεν κύπελλα, δεν έχετε τίποτα να ταξινομήσετε.

951
00:56:50,290 --> 00:56:55,160
Αλλά γενικότερα, Πάω να προτείνουν ότι ο χρόνος εκτέλεσης να ταξινομήσετε n στοιχεία

952
00:56:55,160 --> 00:56:59,350
πρόκειται να είναι ο χρόνος που χρειάζεται για να ταξινομήσει το αριστερό μισό συν το δεξί μισό

953
00:56:59,350 --> 00:57:03,110
συν - τι είναι αυτή η πρόσθετη + n; >> [Φοιτητής] είδος συγχώνευσης.

954
00:57:03,110 --> 00:57:07,260
[Malan] Είναι πραγματικά συγχώνευση, γιατί αν έχετε n / 2 στοιχεία εδώ

955
00:57:07,260 --> 00:57:11,500
και έχετε n / 2 στοιχεία εδώ, πόσος χρόνος χρειάζεται για να τους συγχωνεύσω;

956
00:57:11,500 --> 00:57:15,050
Ακριβώς όπως ο Rob, θα πρέπει να κόβω το ένα πάνω εδώ, ίσως κόβω εδώ,

957
00:57:15,050 --> 00:57:17,120
κόβω εδώ, κόβω εδώ, κόβω εδώ.

958
00:57:17,120 --> 00:57:19,400
Θα πρέπει να αγγίξει κάθε ένα από τα φλιτζάνια φορά.

959
00:57:19,400 --> 00:57:22,030
Και αν υπάρχει 4 φλιτζάνια συν 4 κύπελλα, αυτό είναι 8 φλιτζάνια

960
00:57:22,030 --> 00:57:25,200
ή, γενικότερα, 8 κύπελλα n.

961
00:57:25,200 --> 00:57:28,470
Έτσι, η συγχώνευση βήμα μπορούμε να εκφράσουμε ως n,

962
00:57:28,470 --> 00:57:31,330
και αυτό περιλαμβάνει κυριολεκτικά τον αριθμό των φορών που ο Rob φυσικά άγγιξε

963
00:57:31,330 --> 00:57:33,410
ένα από αυτά τα φελιζόλ κύπελλα.

964
00:57:33,410 --> 00:57:35,850
Ας κάνουμε τώρα μια αυθαίρετη παράδειγμα.

965
00:57:35,850 --> 00:57:41,850
Αν υπάρχει 16 φλυτζάνια, τι είναι ο χρόνος εκτέλεσης της ταξινόμησης, χρησιμοποιώντας τον αλγόριθμο του Rob, 16 κύπελλα;

966
00:57:41,850 --> 00:57:44,710
Είναι 2 φορές την ποσότητα του χρόνου που χρειάζεται για να γκρουπάρετε 8 φλιτζάνια

967
00:57:44,710 --> 00:57:46,920
επειδή έχουμε 8 φλιτζάνια εδώ, 8 φλιτζάνια εδώ.

968
00:57:46,920 --> 00:57:51,520
Δεν ξέρω πόσο καιρό που λαμβάνει, έτσι ώστε να είμαστε γενίκευση ως T προς το παρόν.

969
00:57:51,520 --> 00:57:53,320
Ποιος ξέρει τι είναι;

970
00:57:53,320 --> 00:57:58,990
Αλλά τώρα μπορώ να ταξινομήσετε του αναδρομικά ή κατ 'επανάληψη ζητήσει από την ίδια ερώτηση.

971
00:57:58,990 --> 00:58:01,920
Πόσο χρόνο χρειάζεται για να ταξινομήσετε 8 ποτήρια;

972
00:58:01,920 --> 00:58:07,030
8 φλιτζάνια Πάω να πω παίρνει την ποσότητα του χρόνου που χρειάζεται για να ταξινομήσετε 4 φλιτζάνια συν 4 φλιτζάνια,

973
00:58:07,030 --> 00:58:08,880
τότε μαζί τους συγχώνευση.

974
00:58:08,880 --> 00:58:13,080
Πρόστιμο. Είμαστε εμπλακούμε σε έναν κύκλο ήδη. Πόσο καιρό παίρνει για να ταξινομήσετε 4 φλιτζάνια;

975
00:58:13,080 --> 00:58:19,150
Ο χρόνος που χρειάζεται για να ταξινομήσετε 4 φλιτζάνια είναι 2 φλιτζάνια συν 2 φλιτζάνια διαλογής καθώς και η διαδικασία συγχώνευσης.

976
00:58:19,150 --> 00:58:21,440
Πρόστιμο. Πόσο καιρό παίρνει για να ταξινομήσετε 2 φλιτζάνια;

977
00:58:21,440 --> 00:58:26,290
2 φλυτζάνια είναι η ποσότητα του χρόνου που χρειάζεται για να γκρουπάρετε 1 φλυτζάνι συν το χρόνο που χρειάζεται για να γκρουπάρετε άλλο ένα φλιτζάνι

978
00:58:26,290 --> 00:58:29,040
συν το ποσό του χρόνου που απαιτείται για τη συγχώνευση, η οποία είναι μόλις 2.

979
00:58:29,040 --> 00:58:33,340
>> Πρόστιμο. Τελευταία ερώτηση. Πόσο καιρό παίρνει για να ταξινομήσετε 1 φλιτζάνι;

980
00:58:33,340 --> 00:58:37,260
Εδώ είναι η βασική περίπτωση είχαμε προβλέψει ότι είχαμε χτυπήσει νωρίτερα.

981
00:58:37,260 --> 00:58:42,250
Το γεγονός ότι δεν παίρνει καμία απολύτως εργασία για να ταξινομήσετε το μικρότερο από τα προβλήματα

982
00:58:42,250 --> 00:58:44,120
σημαίνει ότι τώρα, το είδος του στυλ σχολείο βαθμού,

983
00:58:44,120 --> 00:58:46,460
μπορούμε απλά να αρχίσει να συνδέσετε αυτούς τους αριθμούς πίσω μέσα

984
00:58:46,460 --> 00:58:50,630
Τώρα ξέρουμε τι Τ 1 είναι, ώστε να μπορώ να συνδέσετε σε 0 για T από 1.

985
00:58:50,630 --> 00:58:54,420
Αυτό θα μου δώσει την απάντηση του Τ 2, την οποία στη συνέχεια, να συνδέσετε ψηλά.

986
00:58:54,420 --> 00:58:56,930
Αυτό θα μου δώσει T 4, το οποίο μπορώ να συνδέσετε ψηλά.

987
00:58:56,930 --> 00:58:58,920
Αυτό θα μου δώσει T της 8, το οποίο μπορώ να συνδέσετε ψηλά.

988
00:58:58,920 --> 00:59:04,330
Και αν εγώ πραγματικά να κάνουμε ότι μαθηματικά, συνδέοντας αυτές τις απαντήσεις,

989
00:59:04,330 --> 00:59:08,590
Στη συνέχεια να πάρει T των 16 είναι 64.

990
00:59:08,590 --> 00:59:12,090
Και τι κάνει 64 αντιπροσωπεύουν;

991
00:59:12,090 --> 00:59:15,700
Αν Τ είναι 16, ναι, είναι 16 φορές 4.

992
00:59:15,700 --> 00:59:20,120
Γι 'αυτό και ισχυρίζονται τώρα ότι ο χρόνος εκτέλεσης του αυτό το πράγμα που ονομάζεται συγχώνευση είδος -

993
00:59:20,120 --> 00:59:22,590
και αυτό πρόκειται να είναι το πιο μοντέρνο από αυτά που έχουμε δει μέχρι στιγμής -

994
00:59:22,590 --> 00:59:26,160
πρόκειται να ονομάζεται n log n

995
00:59:26,160 --> 00:59:31,140
γιατί πόσες φορές μπορεί να χωριστεί Rob ένα σωρό φλιτζάνια στο ημίχρονο; Σύνδεση n.

996
00:59:31,140 --> 00:59:34,370
Είναι το ίδιο με το παράδειγμα του τηλεφωνικού καταλόγου, είναι το ίδιο με το αυτο-μέτρηση παράδειγμα.

997
00:59:34,370 --> 00:59:36,380
>> Πόσες φορές μπορεί να σας χωρίσει κάτι στη μέση;

998
00:59:36,380 --> 00:59:38,410
Ωστόσο, υπάρχει αυτή η συγχώνευση βήμα.

999
00:59:38,410 --> 00:59:42,920
Ίσως χρειαστεί να διαιρέσει τα κύπελλα σε μισό ξανά και ξανά και ξανά,

1000
00:59:42,920 --> 00:59:45,640
αλλά κάθε φορά που θα πάμε να πρέπει να συγχωνευθούν.

1001
00:59:45,640 --> 00:59:48,270
Και είπαμε νωρίτερα ότι η συγχώνευση n φλιτζάνια παίρνει n βήματα

1002
00:59:48,270 --> 00:59:52,060
γιατί πρέπει να κόβω ένα κύπελλο, κόβω ένα κύπελλο, και θα πρέπει να αγγίξει κάθε φλιτζάνι μια φορά,

1003
00:59:52,060 --> 00:59:53,510
ακριβώς όπως έκανε ο Rob.

1004
00:59:53,510 --> 00:59:59,430
Έτσι, αν κάνουμε κάτι log n φορές και κάνουμε τα πράγματα ν για κάθε μία από αυτές τις επαναλήψεις,

1005
00:59:59,430 --> 01:00:03,090
κάθε μία από αυτές halvings, έχουμε n log n φορές.

1006
01:00:03,090 --> 01:00:07,220
Έτσι, αν συνδέσετε το 16 σε αυτό το παράδειγμα, 16 φορές συνδεθείτε από 16 -

1007
01:00:07,220 --> 01:00:10,600
Δεν χρειάζεται να ανησυχείτε σχετικά με το γιατί αυτή είναι η περίπτωση για τώρα γιατί δεν έχω επιστήσει την βάση -

1008
01:00:10,600 --> 01:00:16,100
αλλά καταγραφής της βάσης 2 από 16 είναι 4, 16 φορές 4 είναι 64.

1009
01:00:16,100 --> 01:00:22,350
Αλλά αντίθετα, αν είχαμε χρησιμοποιήσει είδος φούσκα ή επιλογή είδος ή είδος εισαγωγής με 16 αριθμούς,

1010
01:00:22,350 --> 01:00:26,420
τι θα ο χρόνος εκτέλεσης ήταν αν n είναι 16;

1011
01:00:26,420 --> 01:00:33,310
Θα είναι 16 τετράγωνο, το οποίο είναι 256, το οποίο ακόμα και αν δεν έχουν ακολουθήσει αρκετά όλα τα μαθηματικά,

1012
01:00:33,310 --> 01:00:38,390
256 είναι μεγαλύτερο από 64. Αυτό είναι πραγματικά το μαγικό πακέτο εδώ.

1013
01:00:38,390 --> 01:00:41,990
Και συνειδητοποιούν ότι εργάζονται με αυτό σε μικρότερα παραδείγματα, όπως θα σε PSET

1014
01:00:41,990 --> 01:00:44,260
καθιστά πολύ πιο έξυπνο.

1015
01:00:44,260 --> 01:00:49,070
Αλλά τι πραγματικά σημαίνει αυτό όσον αφορά την αίσθηση αυτού του αλγορίθμου είναι η εξής:

1016
01:00:49,070 --> 01:00:54,520
Αν θέλουμε πραγματικά να κοιτάξουμε στο είδος συγχώνευσης εδώ - επιτρέψτε μου να το τραβήξει επάνω σε αυτό το παράθυρο εδώ -

1017
01:00:54,520 --> 01:00:58,560
αυτό είναι ένα ελαφρώς διαφορετικό παράδειγμα όπου έχουμε όλων των 3 αυτών των αλγορίθμων -

1018
01:00:58,560 --> 01:01:01,440
φούσκα, επιλογή, και η συγχώνευση - ακριβώς δίπλα-δίπλα.

1019
01:01:01,440 --> 01:01:03,740
>> Έχουν όλα ξεκίνησαν με τυχαία μπαρ, και αυτό είναι καλό.

1020
01:01:03,740 --> 01:01:06,240
Κανείς δεν έχει ένα βασικό πλεονέκτημα έναντι του άλλου.

1021
01:01:06,240 --> 01:01:09,500
Πάω να σε μια στιγμή κλικ σε κάθε από αυτά τα κινούμενα σχέδια - Έναρξη, Start, Start -

1022
01:01:09,500 --> 01:01:13,270
όσο πιο γρήγορα μπορώ έτσι ώστε, χονδρικά, όλες ξεκινούν την ίδια στιγμή,

1023
01:01:13,270 --> 01:01:17,450
και ας αναλογιστούμε ότι η χειρότερη περίπτωση είδος φούσκα που τρέχει ο χρόνος είναι ό, τι; >> [Φοιτητής] Ν τετράγωνο.

1024
01:01:17,450 --> 01:01:21,560
Ν τετράγωνο. Χειρότερη περίπτωση επιλογής του είδους που τρέχει ο χρόνος είναι; Ν τετράγωνο.

1025
01:01:21,560 --> 01:01:25,150
Και συγχώνευση είδος είναι προφανώς - ακόμα και αν δεν ακολουθούν αρκετά όλα τα μαθηματικά τώρα,

1026
01:01:25,150 --> 01:01:30,610
αυτό θα γίνει πολύ πιο έξυπνο την πάροδο του χρόνου - είναι, διεκδικούμε, n log n φορές.

1027
01:01:30,610 --> 01:01:35,210
Και επειδή log n είναι αυστηρά λιγότερο από μια φορά n έχουμε μεγάλους αριθμούς,

1028
01:01:35,210 --> 01:01:40,230
n φορές log n είναι μικρότερο από n φορές n ή n τετράγωνο.

1029
01:01:40,230 --> 01:01:44,410
Έτσι, αυτό που νιώθεις πραγματικά να είναι μια καλύτερη αλγόριθμος από την άποψη της διάρκειας,

1030
01:01:44,410 --> 01:01:50,380
n log n φορές σε αντίθεση με n τετράγωνο; Εδώ πάμε. Κάντε κλικ, κλικ, κλικ.

1031
01:01:55,690 --> 01:01:58,650
>> Αυτό είναι το τι σημαίνει να χρησιμοποιήσετε κάτι σαν είδος συγχώνευσης.

1032
01:01:58,650 --> 01:02:01,680
Έχουμε μια στιγμή. Ας δούμε τι συμβαίνει εδώ.

1033
01:02:09,440 --> 01:02:12,440
[Συγκρατημένα γέλια] των οποίων τα χρήματα είναι είδος φούσκα;

1034
01:02:14,960 --> 01:02:16,730
Εξαρτάται μάλλον από την είσοδο μερικές φορές.

1035
01:02:16,730 --> 01:02:18,120
Ας δούμε.

1036
01:02:18,120 --> 01:02:23,320
Έλα. Αισθάνεται σαν να είναι το χαμένο έδαφος. >> [Φοιτητής] Go, είδος φούσκα!

1037
01:02:23,320 --> 01:02:27,370
[Φοιτητές μουρμουρίζοντας]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Ναι, ναι.

1039
01:02:29,120 --> 01:02:34,520
[Φοιτητές μουρμουρίζοντας] Πάμε, πάμε, πάμε!

1040
01:02:37,210 --> 01:02:40,450
[Όλα επευφημίες] [χειροκροτήματα]

1041
01:02:40,450 --> 01:02:46,240
Έτσι, τώρα τελευταία με 1, τελική demo, αν και είναι λίγο δύσκολο να τυλίξουν το μυαλό σας γύρω από τα μαθηματικά

1042
01:02:46,240 --> 01:02:49,280
ή το είδος της απεικόνισης εκεί, μπορείτε να ακούσετε πραγματικά τις ταχύτητες

1043
01:02:49,280 --> 01:02:51,000
των διαφορετικών αλγορίθμων διαφορετικά.

1044
01:02:51,000 --> 01:02:53,900
Πρόκειται για μια κίνηση που κάποιος ότι στην πραγματικότητα συνεργάτες ακούγεται

1045
01:02:53,900 --> 01:02:56,980
με τη διαδικασία της swapping και το ύψος των ράβδων.

1046
01:02:56,980 --> 01:03:00,440
Όπως θα δούμε εδώ, υπάρχει μερικές ακόμα αλγορίθμων ταξινόμησης εκεί έξω ότι οι λαοί έχουν σκεφτεί.

1047
01:03:00,440 --> 01:03:03,660
Το πρώτο θα είναι είδος εισαγωγής, και αυτό θα πετάξει μέσα

1048
01:03:03,660 --> 01:03:07,090
και να σας δώσει μια ακουστική αίσθηση για το πώς αυτά τα διάφορα εργασία αλγορίθμων.

1049
01:03:07,090 --> 01:03:09,080
Εδώ είναι είδος εισαγωγής.

1050
01:03:09,080 --> 01:03:18,410
[Ηλεκτρονικό μπιπ]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bubble sort.

1052
01:03:20,730 --> 01:03:46,850
[Γρηγορότερα ηλεκτρονικό μπιπ]

1053
01:03:46,850 --> 01:03:48,950
[Malan] είδος επιλογής.

1054
01:03:48,950 --> 01:04:03,580
[Γρηγορότερα ηλεκτρονικό μπιπ]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Συγχώνευση είδος.

1056
01:04:05,770 --> 01:04:17,270
[Ηλεκτρονικό μπιπ]

1057
01:04:17,270 --> 01:04:20,180
[Χτυπάει επιβραδύνει] [γέλια]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome είδος.

1059
01:04:22,590 --> 01:04:38,580
[Ηλεκτρονικό μπιπ]

1060
01:04:39,740 --> 01:04:46,150
>> Αυτό είναι CS50. Θα σας δούμε την επόμενη εβδομάδα. [Χειροκροτήματα και επευφημίες]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]