1
00:00:00,000 --> 00:00:11,904
>> [Παίζει μουσική]

2
00:00:11,904 --> 00:00:12,910
>> ΚΑΘΗΓΗΤΗΣ: Εντάξει.

3
00:00:12,910 --> 00:00:16,730
Αυτό είναι CS50 και αυτό είναι
το τέλος τριών εβδομάδων.

4
00:00:16,730 --> 00:00:20,230
Έτσι, είμαστε εδώ σήμερα, δεν είναι σε Sanders
Θέατρο, αντί σε Weidner Βιβλιοθήκη.

5
00:00:20,230 --> 00:00:23,170
Εντός του οποίου υπάρχει ένα στούντιο
γνωστή ως Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
ή ας πούμε Studio H, ή θα
εμείς say-- Αν σας άρεσε αυτό το αστείο,

7
00:00:28,310 --> 00:00:30,540
Είναι πραγματικά από
συμμαθητής του, Μαρκ, σε απευθείας σύνδεση,

8
00:00:30,540 --> 00:00:32,420
ο οποίος πρότεινε τόσο μέσω του Twitter.

9
00:00:32,420 --> 00:00:34,270
Τώρα τι είναι δροσερό για
είναι εδώ σε ένα στούντιο

10
00:00:34,270 --> 00:00:38,410
είναι ότι είμαι περιβάλλεται από αυτές τις πράσινες
τοίχοι, μια πράσινη οθόνη ή chromakey,

11
00:00:38,410 --> 00:00:43,290
να το πω έτσι, πράγμα που σημαίνει ότι το CS50
Η ομάδα παραγωγής, εν αγνοία μου

12
00:00:43,290 --> 00:00:47,380
αυτή τη στιγμή, θα μπορούσε να είναι βάζοντας
με πιο οπουδήποτε στον κόσμο,

13
00:00:47,380 --> 00:00:48,660
προς το καλύτερο ή προς το χειρότερο.

14
00:00:48,660 --> 00:00:51,800
>> Τώρα, τι βρίσκεται μπροστά μας, που το πρόβλημα
δύο είναι στα χέρια σας για αυτή την εβδομάδα,

15
00:00:51,800 --> 00:00:53,830
αλλά με το πρόβλημα που
τρεις την ερχόμενη εβδομάδα,

16
00:00:53,830 --> 00:00:56,600
θα κληθούν με
η λεγόμενη παιχνίδι του 15,

17
00:00:56,600 --> 00:00:58,960
ένα παλιό μέρος χάρη ότι
Ίσως να θυμάστε τη λήψη

18
00:00:58,960 --> 00:01:02,030
ως παιδί που έχει ένα σωρό
των αριθμών που μπορεί να ολισθαίνει πάνω, κάτω,

19
00:01:02,030 --> 00:01:05,790
αριστερά και δεξιά, και υπάρχει ένα χάσμα
εντός του παζλ, στις οποίες μπορείτε

20
00:01:05,790 --> 00:01:07,840
μπορεί να γλιστρήσει στην πραγματικότητα αυτά τα κομμάτια του παζλ.

21
00:01:07,840 --> 00:01:11,150
Τελικά θα λάβετε αυτό
παζλ σε κάποια ημι τυχαία σειρά,

22
00:01:11,150 --> 00:01:12,940
και ο στόχος είναι να
να ταξινομήσετε, πάνω προς τα κάτω,

23
00:01:12,940 --> 00:01:16,310
αριστερά προς τα δεξιά, από τη μία
σε όλη τη διαδρομή μέσα από 15.

24
00:01:16,310 --> 00:01:19,360
>> Δυστυχώς, η εφαρμογή
θα έχετε στο χέρι

25
00:01:19,360 --> 00:01:21,590
πρόκειται να είναι το λογισμικό
με βάση, όχι σωματικά.

26
00:01:21,590 --> 00:01:25,280
Είσαι πραγματικά θα πρέπει να γράψετε
κωδικός με τον οποίο ένας μαθητής ή ο χρήστης μπορεί να

27
00:01:25,280 --> 00:01:26,760
παίζουν το παιχνίδι των 15.

28
00:01:26,760 --> 00:01:29,030
Και στην πραγματικότητα, στην χάκερ
έκδοση του παιχνιδιού των 15,

29
00:01:29,030 --> 00:01:32,155
θα είναι μια πρόκληση για την εφαρμογή της,
όχι μόνο η αναπαραγωγή αυτού του παλιού σχολείου

30
00:01:32,155 --> 00:01:35,010
παιχνίδι, αλλά μάλλον η επίλυση
αυτής, την εφαρμογή κατάσταση θεός,

31
00:01:35,010 --> 00:01:38,280
να το πω έτσι, ότι στην πραγματικότητα
λύνει το παζλ για τον άνθρωπο,

32
00:01:38,280 --> 00:01:41,080
παρέχοντάς τους με υπόδειξη,
μετά από υπόδειξη, μετά την υπόδειξη.

33
00:01:41,080 --> 00:01:42,280
Έτσι, περισσότερα για αυτό την επόμενη εβδομάδα.

34
00:01:42,280 --> 00:01:43,720
Αλλά αυτό είναι ό, τι βρίσκεται μπροστά μας.

35
00:01:43,720 --> 00:01:47,610
>> Προς το παρόν Υπενθυμίζουμε ότι νωρίτερα αυτή την εβδομάδα
είχαμε αυτή τη δραματική στιγμή, αν θέλετε,

36
00:01:47,610 --> 00:01:52,560
οπότε το καλύτερο που κάναμε διαλογής
σοφός ήταν ένα άνω φράγμα των μεγάλων o Ν

37
00:01:52,560 --> 00:01:53,210
τετράγωνο.

38
00:01:53,210 --> 00:01:56,520
Με άλλα λόγια, bubble sort,
ταξινόμηση με επιλογή, ταξινόμηση με εισαγωγή,

39
00:01:56,520 --> 00:01:59,120
όλα αυτά, ενώ οι διαφορετικές
κατά την εφαρμογή τους,

40
00:01:59,120 --> 00:02:03,480
ανατίθεται σε ένα τετράγωνο n τρέχει
φορά στην πολύ χειρότερη περίπτωση.

41
00:02:03,480 --> 00:02:06,010
Και γενικά να υποθέσουμε ότι
η ίδια η χειρότερη περίπτωση για τη διαλογή

42
00:02:06,010 --> 00:02:08,814
είναι αυτή που εισόδους σας
είναι τελείως προς τα πίσω.

43
00:02:08,814 --> 00:02:11,980
Και πράγματι, χρειάστηκαν αρκετά βήματα
να εφαρμόσει κάθε ένα από αυτά αλγορίθμων.

44
00:02:11,980 --> 00:02:15,110
>> Τώρα στο τέλος της τάξης
ανάκληση, συγκρίναμε bubble sort

45
00:02:15,110 --> 00:02:19,390
Ταξινόμηση κατά επιλογή ένας εναντίον του άλλου
ότι καλέσαμε τη συγχώνευση του είδους εκείνη την εποχή,

46
00:02:19,390 --> 00:02:22,120
και προτείνω ότι πρόκειται για τη λήψη
Επωφεληθείτε από ένα μάθημα από εβδομάδα

47
00:02:22,120 --> 00:02:24,060
μηδέν, διαίρει και βασίλευε.

48
00:02:24,060 --> 00:02:28,810
Και κατά κάποιο τρόπο την επίτευξη κάποιου είδους
λογαριθμική χρόνος λειτουργίας σε τελική ανάλυση,

49
00:02:28,810 --> 00:02:31,024
αντί για κάτι
αυτό είναι καθαρά τετραγωνική.

50
00:02:31,024 --> 00:02:33,440
Και δεν είναι αρκετά λογαριθμική,
είναι λίγο περισσότερο από αυτό.

51
00:02:33,440 --> 00:02:36,520
Αλλά αν θυμάστε από την τάξη,
ήταν πολύ, πολύ πιο γρήγορα.

52
00:02:36,520 --> 00:02:38,210
Ας ρίξουμε μια ματιά στο πού είχαμε μείνει.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Bubble sort έναντι επιλογή
Ταξινόμηση έναντι ταξινόμηση με συγχώνευση.

55
00:02:45,370 --> 00:02:47,700
Τώρα είναι όλα τρέχουν, σε
θεωρία, την ίδια στιγμή.

56
00:02:47,700 --> 00:02:50,510
Η CPU τρέχει με την ίδια ταχύτητα.

57
00:02:50,510 --> 00:02:54,990
Αλλά μπορείτε να αισθανθείτε πόσο βαρετό αυτό
είναι πολύ γρήγορα θα γίνει,

58
00:02:54,990 --> 00:02:58,790
και πόσο γρήγορα, όταν κάνετε την ένεση
ένα κομμάτι των αλγορίθμων εβδομάδας μηδενικά,

59
00:02:58,790 --> 00:03:00,080
μπορούμε να επιταχυνθούν τα πράγματα.

60
00:03:00,080 --> 00:03:01,630
>> Έτσι, το σήμα του είδους μοιάζει καταπληκτικά.

61
00:03:01,630 --> 00:03:05,220
Πώς μπορούμε να την αξιοποιήσουν, προκειμένου
να ταξινομήσετε τους αριθμούς πιο γρήγορα.

62
00:03:05,220 --> 00:03:07,140
Λοιπόν ας σκεφτούμε πίσω
σε ένα συστατικό που θα

63
00:03:07,140 --> 00:03:10,380
είχε πίσω στο μηδέν εβδομάδες, εκείνη της
ψάχνουν για κάποιον σε ένα τηλεφωνικό κατάλογο,

64
00:03:10,380 --> 00:03:12,380
και υπενθυμίζουν ότι η
ψευδοκώδικα που προτείναμε,

65
00:03:12,380 --> 00:03:14,560
μέσω του οποίου μπορούμε να βρούμε
κάποιον σαν τον Mike Smith,

66
00:03:14,560 --> 00:03:16,310
κοίταξε λίγο κάτι σαν αυτό.

67
00:03:16,310 --> 00:03:20,820
>> Τώρα ρίξτε μια ματιά στο συγκεκριμένο
στη γραμμή 7 και 8, και 10 και 11,

68
00:03:20,820 --> 00:03:25,240
που επάγουν αυτό το βρόχο, σύμφωνα με την οποία διατηρήσαμε
πηγαίνει πίσω στη γραμμή 3 ξανά, και ξανά,

69
00:03:25,240 --> 00:03:26,520
και πάλι.

70
00:03:26,520 --> 00:03:31,790
Αλλά αποδεικνύεται ότι μπορούμε να δείτε
Αυτός ο αλγόριθμος, εδώ σε ψευδοκώδικα,

71
00:03:31,790 --> 00:03:33,620
λίγο πιο ολιστικά.

72
00:03:33,620 --> 00:03:35,960
Στην πραγματικότητα, αυτό που ψάχνω
στο εδώ στην οθόνη,

73
00:03:35,960 --> 00:03:41,180
είναι ένας αλγόριθμος για την αναζήτηση
Ο Mike Smith ανάμεσα σε κάποιο σύνολο σελίδων.

74
00:03:41,180 --> 00:03:45,520
Και πράγματι, θα μπορούσε να απλουστευθεί αυτή
αλγόριθμος σε αυτές τις γραμμές 7 και 8,

75
00:03:45,520 --> 00:03:49,860
και 10 και 11 να πω μόνο αυτό,
την οποία έχω εδώ παρουσιάζονται με κίτρινο χρώμα.

76
00:03:49,860 --> 00:03:52,210
Με άλλα λόγια, αν ο Mike
Smith είναι νωρίτερα στο βιβλίο,

77
00:03:52,210 --> 00:03:55,004
δεν χρειάζεται να καθορίσετε το βήμα
από το βήμα τώρα πώς να πάει να τον βρει.

78
00:03:55,004 --> 00:03:56,920
Δεν έχουμε να καθορίσετε
να επιστρέψει στη γραμμή 3,

79
00:03:56,920 --> 00:03:58,960
γιατί να μην το κάνουμε εμείς απλά αντ 'αυτού,
ας πούμε, γενικότερα,

80
00:03:58,960 --> 00:04:01,500
αναζήτηση Mike στο
αριστερό μισό του βιβλίου.

81
00:04:01,500 --> 00:04:03,960
>> Αντίθετα, αν ο Mike είναι
στην πραγματικότητα αργότερα στο βιβλίο,

82
00:04:03,960 --> 00:04:07,540
γιατί δεν μπορούμε να σας το αναφέρω unquote αναζήτηση
για Mike στο δεξί ήμισυ του βιβλίου.

83
00:04:07,540 --> 00:04:11,030
Με άλλα λόγια, γιατί να μην το κάνουμε εμείς απλά
είδος λίρα στους εαυτούς μας λέει,

84
00:04:11,030 --> 00:04:13,130
αναζήτηση για Mike σε αυτό
υποσύνολο του βιβλίου,

85
00:04:13,130 --> 00:04:16,279
και να αφήσει στις υπάρχουσες μας
αλγόριθμο για να μας πείτε

86
00:04:16,279 --> 00:04:18,750
πώς να ψάξει για τον Mike στο
ότι το αριστερό μισό του βιβλίου.

87
00:04:18,750 --> 00:04:20,750
Με άλλα λόγια, μας
αλγόριθμος λειτουργεί είτε πρόκειται για

88
00:04:20,750 --> 00:04:24,670
ένα τηλεφωνικό αυτού του πάχους, αυτό
πάχος, ή για οποιοδήποτε λόγο πάχους.

89
00:04:24,670 --> 00:04:27,826
Έτσι μπορούμε αναδρομικά
ορίσετε αυτόν τον αλγόριθμο.

90
00:04:27,826 --> 00:04:29,950
Με άλλα λόγια, σχετικά με την
οθόνη εδώ, είναι ένας αλγόριθμος

91
00:04:29,950 --> 00:04:33,130
για την αναζήτηση Mike Smith
μεταξύ των σελίδων ενός βιβλίου τηλέφωνο.

92
00:04:33,130 --> 00:04:37,410
Έτσι, σύμφωνα 7 και 10, ας
απλώς να πω ακριβώς αυτό.

93
00:04:37,410 --> 00:04:40,250
Και μπορώ να χρησιμοποιήσω αυτόν τον όρο μια στιγμή
πριν, και μάλιστα, αναδρομή

94
00:04:40,250 --> 00:04:42,450
είναι το τσιτάτο για τώρα,
και είναι αυτή η διαδικασία

95
00:04:42,450 --> 00:04:47,210
να κάνει κάτι κυκλική με κάποιο τρόπο
χρησιμοποιώντας τον κωδικό που ήδη έχετε,

96
00:04:47,210 --> 00:04:49,722
και καλώντας και πάλι,
και ξανά, και ξανά.

97
00:04:49,722 --> 00:04:51,930
Τώρα πρόκειται να είναι σημαντικό
ότι κατά κάποιο τρόπο κάτω

98
00:04:51,930 --> 00:04:53,821
έξω, και δεν το κάνουμε αυτό απείρως μεγάλο.

99
00:04:53,821 --> 00:04:56,070
Διαφορετικά θα πάμε να
έχουν πράγματι ένα άπειρο βρόχο.

100
00:04:56,070 --> 00:04:59,810
Αλλά ας δούμε αν μπορούμε να δανειστούμε αυτή την ιδέα
της αναδρομής, κάνει και πάλι κάτι

101
00:04:59,810 --> 00:05:03,600
και ξανά και ξανά, να λύσει
η διαλογή πρόβλημα μέσω της συγχώνευσης

102
00:05:03,600 --> 00:05:05,900
του είδους, όλο και πιο αποτελεσματικά.

103
00:05:05,900 --> 00:05:06,970
>> Έτσι σας δίνω ταξινόμηση με συγχώνευση.

104
00:05:06,970 --> 00:05:07,920
Ας ρίξουμε μια ματιά.

105
00:05:07,920 --> 00:05:10,850
Έτσι, εδώ είναι ψευδοκώδικας, με
η οποία θα μπορούσε να εφαρμόσει τη διαλογή,

106
00:05:10,850 --> 00:05:12,640
χρησιμοποιώντας αυτόν τον αλγόριθμο που ονομάζεται ταξινόμηση με συγχώνευση.

107
00:05:12,640 --> 00:05:13,880
Και είναι πολύ απλά αυτό.

108
00:05:13,880 --> 00:05:15,940
Την είσοδο του n στοιχεία,
Με άλλα λόγια, αν είστε

109
00:05:15,940 --> 00:05:18,830
δεδομένο n στοιχεία και αριθμούς και
γράμματα ή ό, τι η είσοδος είναι,

110
00:05:18,830 --> 00:05:22,430
αν δοθεί n στοιχεία, εάν
n είναι μικρότερη από 2, μόλις επιστρέψει.

111
00:05:22,430 --> 00:05:22,930
Σωστά;

112
00:05:22,930 --> 00:05:26,430
Διότι εάν το η είναι μικρότερο από 2, ότι
σημαίνει ότι η λίστα μου με τα στοιχεία

113
00:05:26,430 --> 00:05:30,446
είναι είτε 0 ή μεγέθους 1, και
και στις δύο αυτές περιπτώσεις ασήμαντα,

114
00:05:30,446 --> 00:05:31,570
η λίστα είναι ήδη ταξινομημένο.

115
00:05:31,570 --> 00:05:32,810
Εάν δεν υπάρχει κατάλογος, είναι ταξινομημένο.

116
00:05:32,810 --> 00:05:35,185
Και αν υπάρχει μια λίστα μήκους
1, είναι προφανώς ταξινομημένο.

117
00:05:35,185 --> 00:05:38,280
Έτσι ο αλγόριθμος χρειάζεται μόνο να
πραγματικά κάτι ενδιαφέρον,

118
00:05:38,280 --> 00:05:40,870
αν έχουμε δύο ή περισσότερα
τα στοιχεία που μας δόθηκαν.

119
00:05:40,870 --> 00:05:42,440
Ας ρίξουμε μια ματιά στο μαγικό συνέχεια.

120
00:05:42,440 --> 00:05:47,500
Αλλιώς ταξινομήσετε το αριστερό μισό των στοιχείων,
Στη συνέχεια ταξινομήσετε το δεξί μισό του στοιχείων,

121
00:05:47,500 --> 00:05:49,640
Στη συνέχεια συγχωνεύσει τα μισά ταξινομημένο.

122
00:05:49,640 --> 00:05:52,440
Και τι είναι το είδος του νου κάμψης
εδώ, είναι ότι δεν μου

123
00:05:52,440 --> 00:05:56,190
φαίνεται να έχουν πει
τίποτα ακόμα, έτσι δεν είναι;

124
00:05:56,190 --> 00:05:59,560
Όλα τα έχω πει είναι, δίνεται μια λίστα με
n στοιχεία, να ταξινομήσετε το αριστερό μισό,

125
00:05:59,560 --> 00:06:01,800
Στη συνέχεια το δεξί μισό, τότε
συγχώνευση των ταξινομημένο μισά,

126
00:06:01,800 --> 00:06:03,840
αλλά πού είναι η πραγματική μυστική συνταγή;

127
00:06:03,840 --> 00:06:05,260
Πού είναι ο αλγόριθμος;

128
00:06:05,260 --> 00:06:09,150
Λοιπόν αποδεικνύεται ότι οι δύο αυτές γραμμές
Κατ 'αρχάς, το είδος αριστερό μισό του στοιχείων,

129
00:06:09,150 --> 00:06:13,970
και το είδος δεξί μισό του στοιχείων,
είναι αναδρομικές κλήσεις, να το πω έτσι.

130
00:06:13,970 --> 00:06:16,120
>> Μετά από όλα, σε αυτό
χρονική στιγμή, έχω

131
00:06:16,120 --> 00:06:18,950
ένας αλγόριθμος με την οποία να
ταξινομήσετε ένα σωρό στοιχεία;

132
00:06:18,950 --> 00:06:19,450
Ναι.

133
00:06:19,450 --> 00:06:20,620
Είναι ακριβώς εδώ.

134
00:06:20,620 --> 00:06:25,180
Είναι ακριβώς εδώ στην οθόνη, και
έτσι ώστε να μπορώ να χρησιμοποιήσω το ίδιο σύνολο βημάτων

135
00:06:25,180 --> 00:06:28,500
για να ταξινομήσετε το αριστερό μισό,
όσο μπορώ το δεξί μισό.

136
00:06:28,500 --> 00:06:30,420
Και πράγματι, και πάλι, και πάλι.

137
00:06:30,420 --> 00:06:34,210
Έτσι ή τον άλλο τρόπο, και σύντομα θα
δείτε αυτό, τη μαγεία της συγχώνευσης είδους

138
00:06:34,210 --> 00:06:37,967
είναι ενσωματωμένο σε αυτό το πολύ τελικό
γραμμή, η συγχώνευση των ταξινομημένων μισά.

139
00:06:37,967 --> 00:06:39,300
Και αυτό φαίνεται αρκετά έξυπνο.

140
00:06:39,300 --> 00:06:41,050
Παίρνετε δύο μισά, και,
κατά κάποιο τρόπο, να συγχωνευθούν,

141
00:06:41,050 --> 00:06:43,260
και θα δούμε αυτό
συγκεκριμένα σε μια στιγμή.

142
00:06:43,260 --> 00:06:45,080
>> Αλλά αυτό είναι ένα πλήρες αλγόριθμο.

143
00:06:45,080 --> 00:06:46,640
Και ας δούμε ακριβώς γιατί.

144
00:06:46,640 --> 00:06:50,912
Λοιπόν ας υποθέσουμε ότι μας δίνεται αυτές τις ίδιες
οκτώ στοιχεία εδώ στην οθόνη, μια

145
00:06:50,912 --> 00:06:53,120
μέσω οκτώ, αλλά είναι
σε φαινομενικά τυχαία σειρά.

146
00:06:53,120 --> 00:06:55,320
Και ο στόχος είναι στο χέρι
για να ταξινομήσετε τα στοιχεία αυτά.

147
00:06:55,320 --> 00:06:58,280
Λοιπόν, πώς μπορώ να πάω για
κάνει το χρησιμοποιείτε, και πάλι,

148
00:06:58,280 --> 00:07:00,407
ταξινόμηση με συγχώνευση, σύμφωνα με την παρούσα ψευδοκώδικα;

149
00:07:00,407 --> 00:07:02,740
Και πάλι, αυτό εμβάπτω
το μυαλό σας, μόνο για μια στιγμή.

150
00:07:02,740 --> 00:07:05,270
Η πρώτη περίπτωση είναι αρκετά
ασήμαντο, αν είναι μικρότερη από 2,

151
00:07:05,270 --> 00:07:07,060
μόλις επιστρέψει, δεν υπάρχει δουλειά να γίνει.

152
00:07:07,060 --> 00:07:09,290
Έτσι, πραγματικά υπάρχει μόνο τρεις
βήματα για να κρατήσει πραγματικά στο μυαλό.

153
00:07:09,290 --> 00:07:11,081
Και πάλι, και ξανά, είμαι
πρόκειται να θέλουν να έχουν

154
00:07:11,081 --> 00:07:13,980
για να ταξινομήσετε το αριστερό μισό,
ταξινομήσετε το δεξί μισό,

155
00:07:13,980 --> 00:07:15,890
και στη συνέχεια μία φορά τους
Τα δύο μισά ταξινομούνται,

156
00:07:15,890 --> 00:07:18,710
Θέλω να τα συγχωνεύσει μαζί
σε μία ταξινομημένη λίστα.

157
00:07:18,710 --> 00:07:19,940
Έτσι κρατήστε αυτό κατά νου.

158
00:07:19,940 --> 00:07:21,310
>> Τόσο εδώ είναι η αρχική λίστα.

159
00:07:21,310 --> 00:07:23,510
Ας το εξετάσουμε ως μια
σειρά, όπως αρχίσαμε να

160
00:07:23,510 --> 00:07:25,800
σε δύο εβδομάδας, η οποία είναι μια
συνεχόμενο μπλοκ μνήμης.

161
00:07:25,800 --> 00:07:28,480
Στην περίπτωση αυτή, περιέχει οκτώ
αριθμούς, πλάτη με πλάτη με πλάτη.

162
00:07:28,480 --> 00:07:30,700
Και τώρα ας ισχύουν ταξινόμηση με συγχώνευση.

163
00:07:30,700 --> 00:07:33,300
Έτσι, θέλω καταρχάς να ταξινομήσετε
το αριστερό μισό του εν λόγω καταλόγου,

164
00:07:33,300 --> 00:07:37,370
και ας, ως εκ τούτου,
επικεντρωθεί σε 4, 8, 6, και 2.

165
00:07:37,370 --> 00:07:41,000
>> Τώρα, πώς μπορώ να πάω για
διαλογή μια λίστα με μέγεθος 4;

166
00:07:41,000 --> 00:07:45,990
Λοιπόν, πρέπει να εξετάσουμε τώρα
διαλογή το αριστερό του αριστερού μισο.

167
00:07:45,990 --> 00:07:47,720
Και πάλι, ας τα πίσω για μια στιγμή.

168
00:07:47,720 --> 00:07:51,010
Αν ο ψευδοκώδικας είναι αυτό,
και μου δίνουν οκτώ στοιχεία,

169
00:07:51,010 --> 00:07:53,230
8 είναι προφανώς μεγαλύτερη
από ή ίσο με 2.

170
00:07:53,230 --> 00:07:54,980
Έτσι, με την πρώτη περίπτωση δεν ισχύει.

171
00:07:54,980 --> 00:07:58,120
Έτσι για να ταξινομήσετε τα οκτώ στοιχεία, για πρώτη φορά
ταξινομήσετε το αριστερό μισό του στοιχείων,

172
00:07:58,120 --> 00:08:01,930
τότε μπορώ να ταξινομήσω το δεξί μισό, τότε θα συγχωνευθούν
οι δύο ταξινομημένων μισά, το καθένα μεγέθους 4.

173
00:08:01,930 --> 00:08:02,470
ΕΝΤΆΞΕΙ.

174
00:08:02,470 --> 00:08:07,480
>> Αλλά αν έχετε μόλις μου είπε, η ταξινόμηση
αριστερό μισό, το οποίο είναι πλέον μεγέθους 4,

175
00:08:07,480 --> 00:08:09,350
Πώς μπορώ να ταξινομήσω το αριστερό μισό;

176
00:08:09,350 --> 00:08:11,430
Λοιπόν αν έχω
εισόδου των τεσσάρων στοιχείων,

177
00:08:11,430 --> 00:08:14,590
Θέλω πρώτα να ταξινομήσετε το αριστερό
δύο, τότε η σωστή δυο,

178
00:08:14,590 --> 00:08:16,210
και στη συνέχεια να τα συγχωνεύσει μαζί.

179
00:08:16,210 --> 00:08:18,700
Έτσι και πάλι, αυτό γίνεται λίγο
του νου κάμψης παιχνίδι εδώ,

180
00:08:18,700 --> 00:08:21,450
γιατί, το είδος, πρέπει να
να θυμάστε πού είστε στην ιστορία,

181
00:08:21,450 --> 00:08:23,620
αλλά στο τέλος της ημέρας,
δεδομένου οποιοδήποτε αριθμό στοιχείων,

182
00:08:23,620 --> 00:08:25,620
θα πρέπει πρώτα να λύσουμε το
αριστερό μισό, τότε το δεξί μισό,

183
00:08:25,620 --> 00:08:26,661
Στη συνέχεια τα συγχωνεύσει μαζί.

184
00:08:26,661 --> 00:08:28,630
Ας αρχίσουμε να κάνουμε ακριβώς αυτό.

185
00:08:28,630 --> 00:08:30,170
Εδώ είναι η είσοδος των οκτώ στοιχείων.

186
00:08:30,170 --> 00:08:31,910
Τώρα ψάχνουμε στο αριστερό μισό εδώ.

187
00:08:31,910 --> 00:08:33,720
Πώς μπορώ να ταξινομήσω τα τέσσερα στοιχεία;

188
00:08:33,720 --> 00:08:35,610
Λοιπόν πρώτα ταξινομήσετε το αριστερό μισό.

189
00:08:35,610 --> 00:08:37,720
Τώρα, πώς μπορώ να ταξινομήσω το αριστερό μισό;

190
00:08:37,720 --> 00:08:39,419
Καλά που μου έχουν δώσει τα δύο στοιχεία.

191
00:08:39,419 --> 00:08:41,240
Ας λύσουμε αυτά τα δύο στοιχεία.

192
00:08:41,240 --> 00:08:44,540
2 είναι μεγαλύτερη από ή
ίση με 2, φυσικά.

193
00:08:44,540 --> 00:08:46,170
Έτσι, η πρώτη περίπτωση δεν ισχύει.

194
00:08:46,170 --> 00:08:49,010
>> Γι 'αυτό και τώρα πρέπει να ταξινομήσετε το αριστερό
ένα δεύτερο από αυτά τα δύο στοιχεία.

195
00:08:49,010 --> 00:08:50,870
Το αριστερό μισό, φυσικά, είναι μόλις 4.

196
00:08:50,870 --> 00:08:54,020
Λοιπόν, πώς μπορώ να ταξινομήσετε μια λίστα ενός στοιχείου;

197
00:08:54,020 --> 00:08:57,960
Καλά τώρα, ότι η ειδική περίπτωση βάσης
επάνω στην κορυφή, να το πω έτσι, ισχύει.

198
00:08:57,960 --> 00:09:01,470
1 είναι μικρότερη από 2, και μου
κατάλογος είναι πράγματι μεγέθους 1.

199
00:09:01,470 --> 00:09:02,747
Γι 'αυτό και μόλις επιστρέψει.

200
00:09:02,747 --> 00:09:03,580
Δεν κάνω τίποτα.

201
00:09:03,580 --> 00:09:06,770
Και πράγματι, να δούμε τι έχω
γίνεται, 4 είναι ήδη ταξινομημένο.

202
00:09:06,770 --> 00:09:09,220
Όπως είμαι ήδη
εν μέρει επιτυχής εδώ.

203
00:09:09,220 --> 00:09:11,750
>> Τώρα που φαίνεται χαζό
να διεκδικήσει, αλλά είναι αλήθεια.

204
00:09:11,750 --> 00:09:13,700
4 είναι μια λίστα με μέγεθος 1.

205
00:09:13,700 --> 00:09:15,090
Είναι ήδη διευθετηθεί.

206
00:09:15,090 --> 00:09:16,270
Αυτό είναι το αριστερό μισό.

207
00:09:16,270 --> 00:09:18,010
Τώρα μπορώ να ταξινομήσω το δεξί μισό.

208
00:09:18,010 --> 00:09:22,310
Εισόδου μου είναι ένα στοιχείο, 8
Ομοίως, έχει ήδη διευθετηθεί.

209
00:09:22,310 --> 00:09:25,170
Stupid, πάρα πολύ, αλλά και πάλι,
Αυτή η βασική αρχή

210
00:09:25,170 --> 00:09:28,310
θα μας επιτρέψει να οικοδομήσουμε τώρα
πάνω από αυτό με επιτυχία.

211
00:09:28,310 --> 00:09:32,260
4 διαλογή, 8 ταξινόμηση, τώρα
τι ήταν αυτό το τελευταίο βήμα;

212
00:09:32,260 --> 00:09:35,330
Έτσι το τρίτο και τελικό βήμα, οποιαδήποτε
φορά που είστε διαλογή μια λίστα, ανάκληση,

213
00:09:35,330 --> 00:09:38,310
ήταν να συγχωνευθούν οι δύο μισά,
το αριστερό και το δεξί.

214
00:09:38,310 --> 00:09:39,900
Έτσι, ας κάνουμε ακριβώς αυτό.

215
00:09:39,900 --> 00:09:41,940
Αριστερό μισό μου είναι, φυσικά, 4.

216
00:09:41,940 --> 00:09:43,310
Δεξιό μισό μου είναι 8.

217
00:09:43,310 --> 00:09:44,100
>> Ας το κάνουμε αυτό.

218
00:09:44,100 --> 00:09:46,410
Πρώτη Πάω να διαθέσει
κάποια πρόσθετη μνήμη,

219
00:09:46,410 --> 00:09:48,680
πως θα εκπροσωπώ εδώ,
όπως ακριβώς μια δευτερεύουσα διάταξη,

220
00:09:48,680 --> 00:09:49,660
ότι είναι αρκετά μεγάλο για να χωρέσει αυτό.

221
00:09:49,660 --> 00:09:52,243
Αλλά μπορείτε να φανταστείτε την παράταση
το ορθογώνιο αυτό όλο το μήκος,

222
00:09:52,243 --> 00:09:53,290
αν χρειαζόμαστε περισσότερο αργότερα.

223
00:09:53,290 --> 00:09:58,440
Πώς μπορώ να πάρω 4 και 8, και τη συγχώνευση
οι δύο λίστες του μεγέθους 1 μαζί;

224
00:09:58,440 --> 00:10:00,270
Εδώ, επίσης, αρκετά απλή.

225
00:10:00,270 --> 00:10:03,300
4 έρχεται πρώτο, τότε έρχεται 8.

226
00:10:03,300 --> 00:10:07,130
Διότι, αν θέλω να ταξινομήσετε
αριστερό μισό, τότε το δεξί μισό,

227
00:10:07,130 --> 00:10:09,900
και στη συνέχεια τη συγχώνευση αυτών των δύο ημίχρονα
μαζί, σε ταξινομημένη σειρά,

228
00:10:09,900 --> 00:10:11,940
4 έρχεται πρώτο, τότε έρχεται 8.

229
00:10:11,940 --> 00:10:15,810
>> Γι 'αυτό φαίνεται να σημειώνει πρόοδο, ακόμη και
αν και δεν έχω κάνει καμία πραγματική εργασία.

230
00:10:15,810 --> 00:10:17,800
Αλλά να θυμάστε πού βρισκόμαστε στην ιστορία.

231
00:10:17,800 --> 00:10:19,360
Εμείς αρχικά πήρε οκτώ στοιχεία.

232
00:10:19,360 --> 00:10:21,480
Εμείς ταξινομημένο το αριστερό μισό, το οποίο είναι 4.

233
00:10:21,480 --> 00:10:24,450
Τότε θα διευθετηθεί το αριστερό μισό
του αριστερού ένα δεύτερο, το οποίο ήταν 2.

234
00:10:24,450 --> 00:10:25,270
Και εδώ πηγαίνουμε.

235
00:10:25,270 --> 00:10:26,920
Εμείς τελειώσαμε με αυτό το βήμα.

236
00:10:26,920 --> 00:10:29,930
>> Έτσι, αν έχουμε την ταξινόμηση
αριστερό μισό του 2, τώρα είμαστε

237
00:10:29,930 --> 00:10:32,130
Πρέπει να λύσουμε το δεξί μισό του 2.

238
00:10:32,130 --> 00:10:35,710
Έτσι το δεξί μισό του 2
Αυτές οι δύο τιμές εδώ, 6 και 2.

239
00:10:35,710 --> 00:10:40,620
Ας ρίξουμε τώρα μια είσοδο του μεγέθους
2, και να ταξινομήσετε το αριστερό μισό, και στη συνέχεια,

240
00:10:40,620 --> 00:10:42,610
το δεξί μισό, και στη συνέχεια,
συγχώνευσή τους μαζί.

241
00:10:42,610 --> 00:10:45,722
Λοιπόν, πώς μπορώ να ταξινομήσετε μια λίστα με μέγεθος
1, που περιέχει μόνο τον αριθμό 6;

242
00:10:45,722 --> 00:10:46,430
Είμαι ήδη γίνει.

243
00:10:46,430 --> 00:10:48,680
Ο εν λόγω κατάλογος μεγέθους 1 ταξινομείται.

244
00:10:48,680 --> 00:10:52,140
>> Πώς μπορώ να ταξινομήσω μια άλλη λίστα
μέγεθος 1, το λεγόμενο δεξιό μισό.

245
00:10:52,140 --> 00:10:54,690
Καλά, επίσης, είναι ήδη ταξινομημένο.

246
00:10:54,690 --> 00:10:56,190
Ο αριθμός 2 είναι μόνη της.

247
00:10:56,190 --> 00:11:00,160
Έτσι τώρα έχω δύο μισά, αριστερά και
σωστά, θα πρέπει να τα συγχωνεύσει μαζί.

248
00:11:00,160 --> 00:11:01,800
Επιτρέψτε μου να δώσω στον εαυτό μου κάποια επιπλέον χώρο.

249
00:11:01,800 --> 00:11:05,580
Και τίθεται 2 εκεί,
Στη συνέχεια 6 εκεί, έτσι

250
00:11:05,580 --> 00:11:10,740
διαλογή του εν λόγω καταλόγου, αριστερά και δεξιά,
και τη συγχώνευση, σε τελική ανάλυση.

251
00:11:10,740 --> 00:11:12,160
Έτσι, είμαι σε ελαφρώς καλύτερη κατάσταση.

252
00:11:12,160 --> 00:11:16,250
Δεν είμαι κάνει, γιατί προφανώς 4, 8, 2,
6 δεν είναι η τελική κατάταξη που θέλω.

253
00:11:16,250 --> 00:11:20,640
Αλλά έχω τώρα δύο καταλόγους του μεγέθους 2, ότι
και οι δύο, αντίστοιχα, έχουν διευθετηθεί.

254
00:11:20,640 --> 00:11:24,580
Έτσι τώρα, αν πίσω στο μυαλό σας
μάτι, πού αυτός μας αφήνει;

255
00:11:24,580 --> 00:11:28,520
Ξεκίνησα με οκτώ στοιχεία, τότε
αποσβεστούν τα κάτω στο αριστερό μισό του 4,

256
00:11:28,520 --> 00:11:31,386
τότε το αριστερό μισό του 2, και
Στη συνέχεια το δεξί μισό του 2,

257
00:11:31,386 --> 00:11:34,510
Τελείωσα, ως εκ τούτου, τη διαλογή στην αριστερή
εξάμηνο του 2, και το δεξί μισό του 2,

258
00:11:34,510 --> 00:11:37,800
ναι, ποιο είναι το τρίτο και τελευταίο στάδιο εδώ;

259
00:11:37,800 --> 00:11:41,290
Έχω να συγχωνευθούν
δύο καταλόγους του μεγέθους 2.

260
00:11:41,290 --> 00:11:42,040
Ας πάμε μπροστά.

261
00:11:42,040 --> 00:11:43,940
Και στην οθόνη εδώ, να δώσει
Θέλω κάποια πρόσθετη μνήμη,

262
00:11:43,940 --> 00:11:47,170
αν και τεχνικά, παρατηρώ ότι έχω
πήρε ένα σωρό κενό επάνω στην κορυφή

263
00:11:47,170 --> 00:11:47,670
εκεί.

264
00:11:47,670 --> 00:11:50,044
Αν θέλω να είναι ιδιαίτερα
αποδοτική χώρο σοφός,

265
00:11:50,044 --> 00:11:52,960
Θα μπορούσα απλά να αρχίσει να κινείται τα στοιχεία
εμπρός και πίσω, πάνω και κάτω.

266
00:11:52,960 --> 00:11:55,460
Αλλά ακριβώς για οπτική ευκρίνεια,
Πάω να το βάλετε κάτω κάτω,

267
00:11:55,460 --> 00:11:56,800
για να κρατήσει τα πράγματα ωραία και καθαρή.

268
00:11:56,800 --> 00:11:58,150
>> Έτσι έχω δύο καταλόγους μεγέθους 2.

269
00:11:58,150 --> 00:11:59,770
Ο πρώτος κατάλογος έχει 4 και 8.

270
00:11:59,770 --> 00:12:01,500
Ο δεύτερος κατάλογος έχει 2 και 6.

271
00:12:01,500 --> 00:12:03,950
Ας συγχωνεύσει εκείνους
μαζί σε ταξινομημένη σειρά.

272
00:12:03,950 --> 00:12:09,910
2, φυσικά, έρχεται πρώτο,
τότε 4, τότε 6, τότε 8.

273
00:12:09,910 --> 00:12:12,560
Και τώρα φαίνεται να παίρνει
κάπου ενδιαφέρουσα.

274
00:12:12,560 --> 00:12:15,720
Τώρα έχω ταξινομημένο το ήμισυ του
λίστα, και συμπτωματικά, είναι

275
00:12:15,720 --> 00:12:18,650
όλοι οι ζυγοί αριθμοί, αλλά ότι
Είναι, πράγματι, απλά μια σύμπτωση.

276
00:12:18,650 --> 00:12:22,220
Και τώρα έχουν ταξινομηθεί στην αριστερή
ένα δεύτερο, έτσι ώστε να είναι 2, 4, 6, και 8.

277
00:12:22,220 --> 00:12:23,430
Τίποτα δεν είναι εκτός λειτουργίας.

278
00:12:23,430 --> 00:12:24,620
Αυτό μοιάζει με την πρόοδο.

279
00:12:24,620 --> 00:12:26,650
>> Τώρα αισθάνεται σαν να έχω
μιλήσει για πάντα τώρα,

280
00:12:26,650 --> 00:12:29,850
έτσι αυτό που μένει να δούμε αν αυτή η
αλγόριθμος είναι, πράγματι, πιο αποτελεσματική.

281
00:12:29,850 --> 00:12:31,766
Αλλά θα πάμε μέσα
το σούπερ μεθοδικά.

282
00:12:31,766 --> 00:12:34,060
Ένας υπολογιστής, φυσικά,
θα το κάνετε έτσι.

283
00:12:34,060 --> 00:12:34,840
Πού βρισκόμαστε λοιπόν;

284
00:12:34,840 --> 00:12:36,180
Ξεκινήσαμε με οκτώ στοιχεία.

285
00:12:36,180 --> 00:12:37,840
Θα διευθετηθεί το αριστερό μισό του 4.

286
00:12:37,840 --> 00:12:39,290
Μου φαίνεται πρέπει να γίνει με αυτό.

287
00:12:39,290 --> 00:12:42,535
Έτσι τώρα το επόμενο βήμα είναι να
ταξινομήσετε το δεξί μισό του 4.

288
00:12:42,535 --> 00:12:44,410
Και αυτό το μέρος μπορούμε να πάμε
μέσω μιας λίγο πιο

289
00:12:44,410 --> 00:12:47,140
γρήγορα, αν είστε
Καλώς ήλθατε στο πίσω ή παύση, απλά

290
00:12:47,140 --> 00:12:49,910
σκεφτείτε μέσω αυτής με την
το δικό σας ρυθμό, αλλά τι

291
00:12:49,910 --> 00:12:53,290
έχουμε τώρα είναι μια ευκαιρία να
κάνουν ακριβώς το ίδιο αλγόριθμο για τέσσερις

292
00:12:53,290 --> 00:12:54,380
διαφορετικούς αριθμούς.

293
00:12:54,380 --> 00:12:57,740
>> Ας πάμε μπροστά, και να επικεντρωθεί στην
το δεξί μισό, που είμαστε εδώ.

294
00:12:57,740 --> 00:13:01,260
Το αριστερό μισό του ότι
δεξιό μισό, και τώρα η

295
00:13:01,260 --> 00:13:04,560
αριστερό ήμισυ του αριστερού
το ήμισυ του εν λόγω δικαιώματος μισό,

296
00:13:04,560 --> 00:13:08,030
και πώς μπορώ να ταξινομήσετε μια λίστα με μέγεθος
1 που περιέχει μόνο τον αριθμό 1;

297
00:13:08,030 --> 00:13:09,030
Είναι ήδη γίνει.

298
00:13:09,030 --> 00:13:11,830
Πώς μπορώ να κάνω το ίδιο για μια λίστα
μεγέθους 1 που περιέχει μόλις 7;

299
00:13:11,830 --> 00:13:12,840
Είναι ήδη γίνει.

300
00:13:12,840 --> 00:13:16,790
Βήμα τρίτο για αυτό το εξάμηνο στη συνέχεια,
είναι να συγχωνευθούν τα δύο αυτά στοιχεία

301
00:13:16,790 --> 00:13:20,889
σε ένα νέο κατάλογο του μεγέθους 2, 1 και 7.

302
00:13:20,889 --> 00:13:23,180
Δεν φαίνεται να έχουν κάνει όλα
ότι πολύ ενδιαφέρουσα δουλειά.

303
00:13:23,180 --> 00:13:24,346
Ας δούμε τι θα συμβεί στη συνέχεια.

304
00:13:24,346 --> 00:13:29,210
Απλά ταξινομημένο το αριστερό μισό του
δεξιό μισό της αρχικής εισόδου μου.

305
00:13:29,210 --> 00:13:32,360
Τώρα ας λύσουμε το δικαίωμα
ένα δεύτερο, το οποίο περιέχει 5 και 3.

306
00:13:32,360 --> 00:13:35,740
Ας δούμε και πάλι στα αριστερά
ήμισυ, διαλογή, δεξί μισό, διαλογή,

307
00:13:35,740 --> 00:13:39,120
και η συγχώνευση των δύο αυτών μαζί,
σε κάποια επιπλέον χώρο,

308
00:13:39,120 --> 00:13:41,670
3 έρχεται πρώτο, τότε έρχεται 5.

309
00:13:41,670 --> 00:13:46,190
Και έτσι τώρα, έχουμε την ταξινόμηση
αριστερό μισό του δεξιού μισού

310
00:13:46,190 --> 00:13:49,420
του αρχικού προβλήματος, και
το δεξί μισό του δεξιού ημίσεως

311
00:13:49,420 --> 00:13:50,800
του αρχικού προβλήματος.

312
00:13:50,800 --> 00:13:52,480
Ποιο είναι το τρίτο και τελευταίο βήμα;

313
00:13:52,480 --> 00:13:54,854
Λοιπόν αυτές να συγχωνευτούν δύο μισά μαζί.

314
00:13:54,854 --> 00:13:57,020
Επιτρέψτε μου λοιπόν τον εαυτό μου να πάρει κάποια
επιπλέον χώρο, αλλά, και πάλι,

315
00:13:57,020 --> 00:13:58,699
θα μπορούσε να χρησιμοποιεί αυτή την ελεύθερος χώρος επάνω στην κορυφή.

316
00:13:58,699 --> 00:14:00,490
Αλλά θα πάμε για να κρατήσει
απλό οπτικά.

317
00:14:00,490 --> 00:14:07,070
Επιτρέψτε μου τώρα να συγχωνεύσει σε 1, και
τότε 3, και, στη συνέχεια, 5, και στη συνέχεια 7.

318
00:14:07,070 --> 00:14:10,740
Αφήνοντας έτσι μου τώρα με το
δεξιό μισό του αρχικού προβλήματος

319
00:14:10,740 --> 00:14:12,840
ότι είναι απόλυτα ταξινομημένο.

320
00:14:12,840 --> 00:14:13,662
>> Οπότε τι μένει;

321
00:14:13,662 --> 00:14:16,120
Νιώθω σαν να κρατήσει λέγοντας ότι η
ίδια πράγματα ξανά και ξανά,

322
00:14:16,120 --> 00:14:18,700
αλλά αυτό είναι αντανακλαστική του
γεγονός ότι χρησιμοποιούμε αναδρομή.

323
00:14:18,700 --> 00:14:21,050
Η διαδικασία χρησιμοποιώντας ένα
αλγόριθμο ξανά, και ξανά,

324
00:14:21,050 --> 00:14:23,940
σε μικρότερα υποσύνολα
το αρχικό πρόβλημα.

325
00:14:23,940 --> 00:14:27,580
Γι 'αυτό και τώρα έχουν μια αριστερή ταξινομημένο
το μισό του αρχικού προβλήματος.

326
00:14:27,580 --> 00:14:30,847
Έχω το δικαίωμα ταξινομημένη εξάμηνο
του αρχικού προβλήματος.

327
00:14:30,847 --> 00:14:32,180
Τι είναι το τρίτο και τελευταίο στάδιο;

328
00:14:32,180 --> 00:14:33,590
Ω, αυτό είναι που συγχωνεύονται.

329
00:14:33,590 --> 00:14:34,480
Ας το κάνουμε αυτό.

330
00:14:34,480 --> 00:14:36,420
Ας διαθέσει κάποια πρόσθετα
μνήμη, αλλά ο Θεός μου,

331
00:14:36,420 --> 00:14:37,503
θα μπορούσε να τεθεί οπουδήποτε τώρα.

332
00:14:37,503 --> 00:14:40,356
Έχουμε στη διάθεσή μας τόσο πολύ χώρο
για εμάς, αλλά εμείς θα το κρατήσουμε απλό.

333
00:14:40,356 --> 00:14:42,730
Αντί να πάει πίσω και να
εμπρός με την αρχική μνήμη μας,

334
00:14:42,730 --> 00:14:44,480
ας το κάνουμε
οπτικά εδώ κάτω κάτω,

335
00:14:44,480 --> 00:14:47,240
να τελειώσει συγχώνευση των
αριστερό μισό και το δεξί μισό.

336
00:14:47,240 --> 00:14:49,279
>> Έτσι, από τη συγχώνευση, τι πρέπει να κάνω;

337
00:14:49,279 --> 00:14:50,820
Θέλω να πάρω τα στοιχεία σε σειρά.

338
00:14:50,820 --> 00:14:53,230
Έτσι, εξετάζοντας αριστερό μισό,
Βλέπω ο πρώτος αριθμός είναι 2.

339
00:14:53,230 --> 00:14:55,230
Κοιτάζω το δεξί μισό,
Βλέπω τον πρώτο αριθμό

340
00:14:55,230 --> 00:14:58,290
είναι 1, οπότε προφανώς η οποία
αριθμός θέλω να κόβω έξω,

341
00:14:58,290 --> 00:15:00,430
και παρουσίασε για πρώτη φορά στην τελική λίστα μου;

342
00:15:00,430 --> 00:15:01,449
Φυσικά, 1.

343
00:15:01,449 --> 00:15:02,990
Τώρα θέλω να ρωτήσω την ίδια ερώτηση.

344
00:15:02,990 --> 00:15:05,040
Στο αριστερό μισό, έχω
εξακολουθεί να πήρε τον αριθμό 2.

345
00:15:05,040 --> 00:15:07,490
Στη δεξιά πλευρά,
Έχω τον αριθμό 3.

346
00:15:07,490 --> 00:15:08,930
Ποιο από τα δύο δεν θέλω να επιλέξω;

347
00:15:08,930 --> 00:15:11,760
Φυσικά, ο αριθμός 2 και
σήμερα παρατηρούμε ότι οι υποψήφιοι

348
00:15:11,760 --> 00:15:13,620
είναι 4 στα αριστερά, 3 στα δεξιά.

349
00:15:13,620 --> 00:15:15,020
Ας, φυσικά, να επιλέξουν 3.

350
00:15:15,020 --> 00:15:18,020
Τώρα οι υποψήφιοι είναι 4 στις
το αριστερό, 5 στα δεξιά.

351
00:15:18,020 --> 00:15:19,460
Εμείς, φυσικά, επιλέξτε 4.

352
00:15:19,460 --> 00:15:21,240
6 στα αριστερά, 5 στα δεξιά.

353
00:15:21,240 --> 00:15:22,730
Εμείς, φυσικά, να επιλέξουν 5.

354
00:15:22,730 --> 00:15:25,020
6 στα αριστερά, 7 στα δεξιά.

355
00:15:25,020 --> 00:15:29,320
Επιλέγουμε 6, και στη συνέχεια θα
επιλέξτε 7, και στη συνέχεια επιλέγουμε 8.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Έτσι, ένας τεράστιος αριθμός των λέξεων αργότερα,
έχουν ταξινομηθεί σε αυτή τη λίστα των οκτώ στοιχείων

358
00:15:34,370 --> 00:15:38,450
σε μια λίστα με ένα έως οκτώ,
ότι αυξάνεται συνεχώς με κάθε βήμα,

359
00:15:38,450 --> 00:15:40,850
αλλά πόσο χρόνο έκανε
θα μας πάρει για να το κάνουμε αυτό.

360
00:15:40,850 --> 00:15:43,190
Λοιπόν έχω σκόπιμα
στρωμένο πράγματα εικονογραφικά

361
00:15:43,190 --> 00:15:46,330
εδώ, έτσι ώστε να μπορούμε να το είδος του
δείτε ή να εκτιμήσουν τη διαίρεση

362
00:15:46,330 --> 00:15:49,060
στην κατάκτηση που είναι ήδη συμβαίνει.

363
00:15:49,060 --> 00:15:52,830
>> Πράγματι, αν κοιτάξουμε πίσω μετά,
Έχω αφήσει όλες αυτές τις διακεκομμένες γραμμές

364
00:15:52,830 --> 00:15:55,660
σε κατόχους θέση, μπορείτε,
είδος, βλέπε, σε αντίστροφη σειρά,

365
00:15:55,660 --> 00:15:58,800
αν το είδος των κοιτάξουμε πίσω στο
ιστορία τώρα, η αρχική λίστα μου

366
00:15:58,800 --> 00:16:00,250
είναι, φυσικά, από το μέγεθος 8.

367
00:16:00,250 --> 00:16:03,480
Και στη συνέχεια, στο παρελθόν, ήμουν
που ασχολούνται με δύο καταλόγους του μεγέθους 4,

368
00:16:03,480 --> 00:16:08,400
και στη συνέχεια τέσσερις λίστες του μεγέθους 2,
και στη συνέχεια οκτώ λίστες μέγεθος 1.

369
00:16:08,400 --> 00:16:10,151
>> Έτσι, αυτό που κάνει αυτό,
είδος, σου θυμίζει;

370
00:16:10,151 --> 00:16:11,858
Λοιπόν, πράγματι, καμία από
οι αλγόριθμοι έχουμε

371
00:16:11,858 --> 00:16:14,430
κοίταξε μέχρι σήμερα όπου
διαίρει και χάσμα, και χάσμα,

372
00:16:14,430 --> 00:16:19,500
έχοντας κρατήσει τα πράγματα και πάλι, και
πάλι, ως αποτέλεσμα σε αυτήν την γενική ιδέα.

373
00:16:19,500 --> 00:16:23,100
Και έτσι υπάρχει κάτι
λογαριθμική συμβαίνει εδώ.

374
00:16:23,100 --> 00:16:26,790
Και δεν είναι αρκετά καταγραφής των n, αλλά
υπάρχει μια λογαριθμική συστατικό

375
00:16:26,790 --> 00:16:28,280
σε ό, τι έχουμε κάνει ακριβώς.

376
00:16:28,280 --> 00:16:31,570
>> Τώρα ας εξετάσουμε πώς αυτό πραγματικά είναι.

377
00:16:31,570 --> 00:16:34,481
Έτσι log Ν, και πάλι ήταν
ένα μεγάλο χρονικό διάστημα λειτουργίας,

378
00:16:34,481 --> 00:16:36,980
όταν κάναμε κάτι σαν
δυαδική αναζήτηση, όπως ονομάζουμε σήμερα,

379
00:16:36,980 --> 00:16:40,090
η στρατηγική διαίρει και βασίλευε
μέσω του οποίου βρήκαμε Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Τώρα τεχνικά.

381
00:16:41,020 --> 00:16:43,640
Αυτό είναι αρχείο καταγραφής βάσης 2 του ν, ακόμη και
αν και στις περισσότερες τάξεις μαθηματικά,

382
00:16:43,640 --> 00:16:45,770
10 είναι συνήθως η βάση που θα αναλάβει.

383
00:16:45,770 --> 00:16:48,940
Αλλά οι επιστήμονες υπολογιστών σχεδόν πάντα
σκεφτεί και να μιλήσει από την άποψη της βάσης 2,

384
00:16:48,940 --> 00:16:52,569
έτσι γενικά μόνο να πω καταγραφής των
n, αντί του log βάσης 2 του n,

385
00:16:52,569 --> 00:16:55,110
αλλά είναι ακριβώς το ένα και το
ίδιο στον κόσμο των υπολογιστών

386
00:16:55,110 --> 00:16:57,234
επιστήμη, και ως ένα μέρος,
υπάρχει ένα σταθερό συντελεστή

387
00:16:57,234 --> 00:17:01,070
διαφορά μεταξύ των δύο, έτσι είναι
αμφισβητήσιμο ούτως ή άλλως, για περισσότερες τυπικούς λόγους.

388
00:17:01,070 --> 00:17:04,520
>> Αλλά για τώρα, αυτό που μας ενδιαφέρει
για παράδειγμα είναι αυτό.

389
00:17:04,520 --> 00:17:08,520
Οπότε ας μην αποδειχθούν με το παράδειγμά μας, αλλά και σε
τουλάχιστον χρησιμοποιήσουμε ένα παράδειγμα από τους αριθμούς

390
00:17:08,520 --> 00:17:10,730
στο χέρι σαν ένας έλεγχος λογική, αν θέλετε.

391
00:17:10,730 --> 00:17:14,510
Έτσι στο παρελθόν ο τύπος ήταν βάσης καταγραφής
2 του n, αλλά αυτό που είναι n σε αυτήν την περίπτωση.

392
00:17:14,510 --> 00:17:18,526
Είχα n αρχικών αριθμών, ή 8
του αρχικού αριθμού συγκεκριμένα.

393
00:17:18,526 --> 00:17:20,359
Τώρα αυτό είναι μια μικρή
ενώ, αλλά είμαι αρκετά

394
00:17:20,359 --> 00:17:25,300
βεβαιωθείτε ότι καταγραφής βάσης 2
της αξίας 8 είναι 3,

395
00:17:25,300 --> 00:17:29,630
και μάλιστα, ό, τι είναι καλό γι 'αυτό είναι
ότι 3 είναι ακριβώς ο αριθμός των φορών

396
00:17:29,630 --> 00:17:33,320
ότι μπορείτε να διαιρέσει μια λίστα
μήκους 8 και πάλι, και πάλι,

397
00:17:33,320 --> 00:17:36,160
και ξανά, μέχρι να αφήνεστε
καταλόγους με μόλις 1 μέγεθος.

398
00:17:36,160 --> 00:17:36,660
Σωστά;

399
00:17:36,660 --> 00:17:40,790
8 πηγαίνει στο 4, πηγαίνει στο 2,
πηγαίνει στο 1, και αυτό είναι

400
00:17:40,790 --> 00:17:43,470
αντανακλούν ακριβώς ότι
εικόνα που είχαμε πριν από λίγο.

401
00:17:43,470 --> 00:17:47,160
Επομένως, λίγη λογική ελέγχει ως προς το πού
ο λογάριθμος είναι πραγματικά εμπλέκονται.

402
00:17:47,160 --> 00:17:50,180
>> Έτσι τώρα, τι άλλο περιλαμβάνεται εδώ; Ν.

403
00:17:50,180 --> 00:17:53,440
Έτσι, παρατηρούμε ότι κάθε
χώρισα χρόνο τον κατάλογο,

404
00:17:53,440 --> 00:17:58,260
έστω και με την αντίστροφη σειρά στην ιστορία
Εδώ, έκανα ήταν ν πράγματα.

405
00:17:58,260 --> 00:18:02,320
Αυτό το βήμα απαιτείται η συγχώνευση
Αγγίζω κάθε έναν από τους αριθμούς,

406
00:18:02,320 --> 00:18:05,060
προκειμένου να διολισθήσει σε
κατάλληλη θέση του.

407
00:18:05,060 --> 00:18:10,760
Έτσι, ακόμη και αν το ύψος αυτού του
διάγραμμα είναι του μεγέθους του αρχείου καταγραφής ν ν ή 3,

408
00:18:10,760 --> 00:18:13,860
Συγκεκριμένα, με άλλα λόγια,
Έκανα τρία τμήματα εδώ.

409
00:18:13,860 --> 00:18:18,800
Πόση δουλειά έκανα οριζόντια
κατά μήκος αυτό το διάγραμμα κάθε φορά;

410
00:18:18,800 --> 00:18:21,110
>> Λοιπόν, έκανα n βήματα
λειτουργήσει, γιατί αν έχω

411
00:18:21,110 --> 00:18:24,080
πήρε τέσσερα στοιχεία και τα τέσσερα στοιχεία,
και εγώ πρέπει να τα συγχωνεύσει μαζί.

412
00:18:24,080 --> 00:18:26,040
Θα πρέπει να περάσουν από
αυτά τα τέσσερα και αυτά τα τέσσερα,

413
00:18:26,040 --> 00:18:28,123
τελικά να τα συγχωνεύσει
πίσω σε οκτώ στοιχεία.

414
00:18:28,123 --> 00:18:32,182
Αν αντιθέτως έχω οκτώ δάχτυλα
εδώ, το οποίο εγώ δεν κάνω, και οκτώ

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- αν έχω
πήρε τέσσερα δάχτυλα πάνω από εδώ,

416
00:18:34,390 --> 00:18:37,380
που το κάνω, τέσσερα δάχτυλα
εδώ, το οποίο κάνω,

417
00:18:37,380 --> 00:18:40,590
τότε αυτό είναι το ίδιο
παράδειγμα όπως και πριν, αν το κάνω

418
00:18:40,590 --> 00:18:44,010
έχει οκτώ δάχτυλα αν και σε
Συνολικά, τα οποία μπορώ, το είδος του, το κάνουν.

419
00:18:44,010 --> 00:18:47,950
Μπορώ να κάνω ακριβώς εδώ,
τότε σίγουρα μπορεί να

420
00:18:47,950 --> 00:18:50,370
συγχωνεύσει όλες αυτές τις λίστες
μεγέθους 1 μαζί.

421
00:18:50,370 --> 00:18:54,050
Αλλά σίγουρα πρέπει να εξετάσουμε
σε κάθε στοιχείο ακριβώς μια φορά.

422
00:18:54,050 --> 00:18:59,640
Έτσι, το ύψος αυτής της διαδικασίας είναι log n,
το πλάτος αυτής της διαδικασίας, να το πω έτσι,

423
00:18:59,640 --> 00:19:02,490
είναι n, οπότε αυτό που φαίνεται
να έχει, τελικά, είναι

424
00:19:02,490 --> 00:19:06,470
ένας χρόνος τρέχει μεγέθους n log n φορές.

425
00:19:06,470 --> 00:19:08,977
>> Με άλλα λόγια, χωρίσαμε
η λίστα, log n φορές,

426
00:19:08,977 --> 00:19:11,810
αλλά κάθε φορά που το κάναμε αυτό, είχαμε
να αγγίξει κάθε ένα από τα στοιχεία

427
00:19:11,810 --> 00:19:13,560
προκειμένου να τα συγχωνεύσει
όλοι μαζί, το οποίο

428
00:19:13,560 --> 00:19:18,120
ήταν n βήμα, έτσι έχουμε n log n φορές,
ή ως ένας επιστήμονας υπολογιστών θα έλεγα,

429
00:19:18,120 --> 00:19:20,380
ασυμπτωτικά, η οποία
θα είναι η μεγάλη λέξη

430
00:19:20,380 --> 00:19:22,810
για να περιγράψει το ανώτερο
δεσμεύεται σε ένα χρόνο λειτουργίας,

431
00:19:22,810 --> 00:19:28,010
θα είναι ανοιχτά σε μια μεγάλη o
του log n χρόνου, να το πω έτσι.

432
00:19:28,010 --> 00:19:31,510
>> Τώρα αυτό είναι σημαντικό, διότι
θυμηθούμε τι οι χρόνοι εκτέλεσης ήταν

433
00:19:31,510 --> 00:19:34,120
με bubble sort, και επιλογή
είδος, και ταξινόμηση με εισαγωγή,

434
00:19:34,120 --> 00:19:38,200
και ακόμη και μερικά άλλα που υπάρχουν,
n τετράγωνο ήταν όταν ήμασταν στο.

435
00:19:38,200 --> 00:19:39,990
Και μπορείτε, είδος, δείτε αυτό εδώ.

436
00:19:39,990 --> 00:19:45,720
Εάν n τετράγωνο είναι προφανώς n φορές
n, αλλά εδώ έχουμε n log n φορές,

437
00:19:45,720 --> 00:19:48,770
και γνωρίζουμε ήδη από την εβδομάδα
μηδέν, δηλαδή log n, η λογαριθμική,

438
00:19:48,770 --> 00:19:50,550
είναι καλύτερη από ό, τι κάτι γραμμικό.

439
00:19:50,550 --> 00:19:52,930
Μετά από όλα, ας θυμηθούμε την εικόνα
με το κόκκινο και το κίτρινο

440
00:19:52,930 --> 00:19:56,500
και οι πράσινες γραμμές που συντάξαμε, η
πράσινο λογαριθμική γραμμή ήταν πολύ χαμηλότερη.

441
00:19:56,500 --> 00:20:00,920
Και ως εκ τούτου, πολύ καλύτερα και γρηγορότερα
από τις ευθείες κίτρινες και κόκκινες γραμμές,

442
00:20:00,920 --> 00:20:05,900
n log n φορές είναι, πράγματι, την καλύτερη
από φορές n n ή n τετράγωνο.

443
00:20:05,900 --> 00:20:09,110
>> Γι 'αυτό και φαίνεται να έχουν
εντόπισε συγχώνευση αλγόριθμο

444
00:20:09,110 --> 00:20:11,870
είδος που τρέχει σε πολύ
ταχύτερο χρόνο, και πράγματι,

445
00:20:11,870 --> 00:20:16,560
γι 'αυτό, νωρίτερα αυτή την εβδομάδα, όταν
Είδαμε ότι διαγωνισμό μεταξύ φούσκα

446
00:20:16,560 --> 00:20:20,750
είδος, ταξινόμηση με επιλογή, και να συγχωνεύσει
είδος, ταξινόμηση με συγχώνευση πραγματικά, πραγματικά κέρδισε.

447
00:20:20,750 --> 00:20:23,660
Και πράγματι, δεν είχαμε καν περιμένετε
για bubble sort και ταξινόμηση με επιλογή

448
00:20:23,660 --> 00:20:24,790
να τελειωσω.

449
00:20:24,790 --> 00:20:27,410
>> Τώρα ας ρίξουμε άλλο ένα πέρασμα
σε αυτό, από μια ελαφρώς πιο

450
00:20:27,410 --> 00:20:31,030
επίσημη άποψη, μόνο στην
περίπτωση, αυτό αντηχεί καλύτερα

451
00:20:31,030 --> 00:20:33,380
από αυτό το υψηλότερο επίπεδο συζήτησης.

452
00:20:33,380 --> 00:20:34,880
Έτσι, εδώ είναι και πάλι ο αλγόριθμος.

453
00:20:34,880 --> 00:20:36,770
Ας αναρωτηθούμε,
ό, τι ο χρόνος τρέχει

454
00:20:36,770 --> 00:20:39,287
Είναι αυτή η Αλγόριθμοι διάφορα βήματα;

455
00:20:39,287 --> 00:20:41,620
Ας το χωρίσουμε σε πρώτη
περίπτωση και η δεύτερη περίπτωση.

456
00:20:41,620 --> 00:20:46,280
Η ΕΠΕΥ και ο άλλος στην περίπτωση κατά την οποία,
Εάν n είναι μικρότερη από 2, μόλις επιστρέψει.

457
00:20:46,280 --> 00:20:47,580
Αίσθηση σαν χρονική σταθερά.

458
00:20:47,580 --> 00:20:50,970
Είναι, είδος, σαν δύο στάδια,
Εάν n είναι μικρότερη από 2, στη συνέχεια επιστρέφουν.

459
00:20:50,970 --> 00:20:54,580
Αλλά, όπως είπαμε, τη Δευτέρα,
σταθερά χρόνου, ή μεγάλα o 1,

460
00:20:54,580 --> 00:20:57,130
μπορεί να είναι δύο βήματα, τρεις
βήματα, ακόμη και 1.000 βήματα.

461
00:20:57,130 --> 00:20:59,870
Αυτό που έχει σημασία είναι ότι είναι
ένα σταθερό αριθμό βημάτων.

462
00:20:59,870 --> 00:21:03,240
Έτσι το κίτρινο τόνισε ψευδοκώδικα
εδώ τρέχει σε, θα το ονομάσουμε,

463
00:21:03,240 --> 00:21:04,490
σταθερά χρόνου.

464
00:21:04,490 --> 00:21:06,780
Έτσι, πιο επίσημα, και
θα πάμε to-- αυτό

465
00:21:06,780 --> 00:21:09,910
θα είναι η έκταση στην οποία θα
επισημοποιήσει αυτό το δικαίωμα now-- Τ Ν,

466
00:21:09,910 --> 00:21:15,030
ο χρόνος εκτέλεσης ενός προβλήματος
ότι χρειάζεται ν Κάτι σαν είσοδο,

467
00:21:15,030 --> 00:21:19,150
ισούται με μεγάλα o του ενός,
Εάν n είναι μικρότερη από 2.

468
00:21:19,150 --> 00:21:20,640
Έτσι είναι προϋπόθεση για αυτό.

469
00:21:20,640 --> 00:21:24,150
Έτσι για να είναι σαφές, αν το n είναι μικρότερο από
2, έχουμε μια πολύ μικρή λίστα, στη συνέχεια,

470
00:21:24,150 --> 00:21:29,151
ο χρόνος τρέχει, Τ n, όπου n είναι
1 ή 0, σε αυτή την πολύ ειδική περίπτωση,

471
00:21:29,151 --> 00:21:30,650
είναι ακριβώς πρόκειται να είναι σταθερά χρόνου.

472
00:21:30,650 --> 00:21:32,691
Είναι πρόκειται να πάρει ένα
βήμα, δύο βήματα, οτιδήποτε.

473
00:21:32,691 --> 00:21:33,950
Είναι ένα σταθερό αριθμό βημάτων.

474
00:21:33,950 --> 00:21:38,840
>> Έτσι, το ζουμερό μέρος πρέπει σίγουρα να είναι σε
Η άλλη περίπτωση στην ψευδοκώδικα.

475
00:21:38,840 --> 00:21:40,220
Η υπόθεση ΑΛΛΟ.

476
00:21:40,220 --> 00:21:44,870
Ταξινόμηση αριστερό μισό του στοιχείων, να ταξινομήσετε σωστά
το ήμισυ των στοιχείων, η συγχώνευση ταξινομημένο μισά.

477
00:21:44,870 --> 00:21:46,800
Πόσος χρόνος χρειάζεται για κάθε ένα από αυτά τα βήματα λάβει;

478
00:21:46,800 --> 00:21:49,780
Λοιπόν, εάν η λειτουργία
χρόνο για να ταξινομήσετε τα n στοιχεία

479
00:21:49,780 --> 00:21:53,010
είναι, ας το ονομάσουμε πολύ
γενικά, Τ n,

480
00:21:53,010 --> 00:21:55,500
Στη συνέχεια η διαλογή στην αριστερή
ένα δεύτερο από τα στοιχεία

481
00:21:55,500 --> 00:21:59,720
είναι, το είδος του, σαν να λέμε,
Τ n διαιρείται με 2,

482
00:21:59,720 --> 00:22:03,000
και ομοίως διαλογής το δεξί μισό
των στοιχείων είναι, το είδος του, σαν να λέμε,

483
00:22:03,000 --> 00:22:06,974
Τ n διαιρείται 2, και στη συνέχεια
συγχώνευση των ταξινομημένο μισά.

484
00:22:06,974 --> 00:22:08,890
Λοιπόν, αν έχω κάποια
αριθμό στοιχείων εδώ,

485
00:22:08,890 --> 00:22:11,230
όπως τέσσερα, και κάποια σειρά
των στοιχείων εδώ, όπως και τέσσερα,

486
00:22:11,230 --> 00:22:14,650
και έχω να συγχωνεύσει κάθε ένα από αυτά τα τέσσερα
in, και κάθε ένα από αυτά τα τέσσερα μέσα, μια

487
00:22:14,650 --> 00:22:17,160
μετά το άλλο, έτσι ώστε να
τελικά έχω οκτώ στοιχεία.

488
00:22:17,160 --> 00:22:20,230
Αισθάνεται σαν να είναι μεγάλη o του n βήματα;

489
00:22:20,230 --> 00:22:23,500
Αν έχω ν δάχτυλα και καθένα από τα
τους θα πρέπει να συγχωνευθούν σε θέση,

490
00:22:23,500 --> 00:22:25,270
αυτό είναι σαν ένα άλλο n βήματα.

491
00:22:25,270 --> 00:22:27,360
>> Έτσι πράγματι formulaically,
μπορούμε να εκφράσουμε αυτό,

492
00:22:27,360 --> 00:22:29,960
αν και λίγο τρομακτικά στην αρχή
ματιά, αλλά είναι κάτι

493
00:22:29,960 --> 00:22:31,600
ότι αποτυπώνει ακριβώς αυτή τη λογική.

494
00:22:31,600 --> 00:22:35,710
Ο χρόνος τρέχει, Τ Ν, αν το n
είναι μεγαλύτερο από ή ίσο με 2.

495
00:22:35,710 --> 00:22:42,500
Σε αυτή την περίπτωση, η υπόθεση άλλο, είναι Τ Ν
διαιρούμενο με 2, συν Τ Ν διαιρείται με 2,

496
00:22:42,500 --> 00:22:45,320
συν μεγάλες o Ν, μερικοί
γραμμική αριθμό των βημάτων,

497
00:22:45,320 --> 00:22:51,630
ίσως ακριβώς n, ίσως και 2 φορές
n, αλλά είναι κατά προσέγγιση, προκειμένου ν.

498
00:22:51,630 --> 00:22:54,060
Έτσι ώστε, επίσης, είναι το πώς μπορούμε να
εκφράσουν αυτό formulaically.

499
00:22:54,060 --> 00:22:56,809
Τώρα δεν θα το γνωρίζουν αυτό, εκτός αν
έχετε εγγραφεί στο μυαλό σας,

500
00:22:56,809 --> 00:22:58,710
ή να το αναζητήσετε στο
πίσω του ένα βιβλίο, ότι

501
00:22:58,710 --> 00:23:00,501
θα μπορούσε να έχει μια μικρή
εξαπατήσει φύλλο στο τέλος,

502
00:23:00,501 --> 00:23:03,940
αλλά αυτό είναι, πράγματι, πρόκειται να
μας δίνουν μια μεγάλη o του n log n,

503
00:23:03,940 --> 00:23:06,620
επειδή η υποτροπή που
που βλέπετε εδώ στην οθόνη,

504
00:23:06,620 --> 00:23:09,550
αν πραγματικά το έκανε έξω, με
ένας άπειρος αριθμός παραδειγμάτων,

505
00:23:09,550 --> 00:23:13,000
ή το κάνατε formulaically, θα κάνατε
δείτε ότι αυτό, γιατί αυτόν τον τύπο

506
00:23:13,000 --> 00:23:17,100
η ίδια έχει επαναληπτικό, με τόνους
n πάνω από κάτι σχετικά με το δικαίωμα,

507
00:23:17,100 --> 00:23:21,680
και t των Ν πάνω στο αριστερό, αυτό μπορεί
πράγματι να εκφράζεται, εν τέλει,

508
00:23:21,680 --> 00:23:24,339
τόσο μεγάλη πάει n log n.

509
00:23:24,339 --> 00:23:26,130
Εάν δεν πεισθεί, ότι είναι
πρόστιμο για τώρα, απλά

510
00:23:26,130 --> 00:23:28,960
αναλάβει την πίστη, ότι είναι, πράγματι,
τι επανάληψη οδηγεί,

511
00:23:28,960 --> 00:23:31,780
αλλά αυτό είναι μόνο ένα κομμάτι περισσότερο από ένα
μαθηματική προσέγγιση προκειμένου να διερευνηθεί

512
00:23:31,780 --> 00:23:36,520
κατά το χρόνο λειτουργίας της συγχώνευσης είδους
με βάση ψευδοκώδικας της και μόνο.

513
00:23:36,520 --> 00:23:39,030
>> Τώρα, ας ρίξουμε ένα κομμάτι από ένα
ανάσα από όλα αυτά,

514
00:23:39,030 --> 00:23:41,710
και να ρίξετε μια ματιά σε ένα
ορισμένους πρώην γερουσιαστής, ο οποίος

515
00:23:41,710 --> 00:23:44,260
μπορεί να μοιάζει λίγο γνωστά,
ο οποίος κάθισε με τον Eric της Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, πριν από λίγο καιρό, για μια συνέντευξη
στη σκηνή, μπροστά σε ένα σωρό

517
00:23:48,410 --> 00:23:53,710
των ανθρώπων, μιλάμε τελικά για
ένα θέμα, αυτό είναι αρκετά γνωστό πια.

518
00:23:53,710 --> 00:23:54,575
Ας ρίξουμε μια ματιά.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Τώρα γερουσιαστής,
είστε εδώ στη Google,

521
00:24:03,890 --> 00:24:09,490
και μου αρέσει να σκέφτομαι το
της προεδρίας ως μια συνέντευξη για δουλειά.

522
00:24:09,490 --> 00:24:11,712
Τώρα είναι δύσκολο να βρουν μια θέση εργασίας ως πρόεδρος.

523
00:24:11,712 --> 00:24:12,670
Πρόεδρος Ομπάμα: Σωστά.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Και είσαι
πρόκειται να κάνει [δεν ακούγεται] τώρα.

525
00:24:13,940 --> 00:24:15,523
Είναι επίσης δύσκολο να βρουν μια θέση εργασίας στην Google.

526
00:24:15,523 --> 00:24:17,700
Πρόεδρος Ομπάμα: Σωστά.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Έχουμε ερωτήσεις,
και ζητάμε από τους υποψηφίους στις ερωτήσεις μας,

528
00:24:21,330 --> 00:24:24,310
και αυτό είναι από Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> Πρόεδρος Ομπάμα: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: Τι;

531
00:24:27,005 --> 00:24:28,130
Εσείς νομίζετε ότι αστειεύομαι;

532
00:24:28,130 --> 00:24:30,590
Είναι ακριβώς εδώ.

533
00:24:30,590 --> 00:24:33,490
Ποιος είναι ο πιο αποτελεσματικός τρόπος για να
ταξινομήσετε μια ακέραιοι εκατομμύρια 32 bit;

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> Πρόεδρος Ομπάμα: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Μερικές φορές,
ίσως Λυπάμαι, maybe--

537
00:24:41,020 --> 00:24:42,750
Πρόεδρος Ομπάμα: Όχι, όχι,
Όχι, όχι, όχι, εγώ think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Αυτό δεν είναι it--

539
00:24:43,240 --> 00:24:45,430
Πρόεδρος Ομπάμα: Ι
σκέφτομαι, νομίζω ότι η φούσκα

540
00:24:45,430 --> 00:24:46,875
του είδους θα είναι ο λάθος τρόπος να πάει.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Έλα.

543
00:24:50,535 --> 00:24:52,200
Ποιος τον είπε αυτό;

544
00:24:52,200 --> 00:24:54,020
ΕΝΤΆΞΕΙ.

545
00:24:54,020 --> 00:24:55,590
Δεν είχα την επιστήμη των υπολογιστών on--

546
00:24:55,590 --> 00:24:58,986
>> Πρόεδρος Ομπάμα: Έχουμε
πήρε κατασκόπους μας εκεί.

547
00:24:58,986 --> 00:24:59,860
ΚΑΘΗΓΗΤΗΣ: Εντάξει.

548
00:24:59,860 --> 00:25:03,370
Ας αφήσουμε πίσω μας το τώρα
θεωρητική κόσμο των αλγορίθμων

549
00:25:03,370 --> 00:25:06,520
στην ασυμπτωτική ανάλυση
αυτών, και να επιστρέψει σε ορισμένα θέματα

550
00:25:06,520 --> 00:25:09,940
από την εβδομάδα μηδέν και το ένα, και της έναρξης
για να αφαιρέσετε κάποιες βοηθητικές ρόδες,

551
00:25:09,940 --> 00:25:10,450
αν θέλετε.

552
00:25:10,450 --> 00:25:13,241
Έτσι ώστε να μπορείτε πραγματικά να καταλάβω
τελικά από το μηδέν, τι είναι

553
00:25:13,241 --> 00:25:16,805
συμβαίνει κάτω από την κουκούλα, όταν
γράψετε, μεταγλωττίσετε και να εκτελέσετε προγράμματα.

554
00:25:16,805 --> 00:25:19,680
Υπενθυμίζουμε συγκεκριμένα, ότι αυτό ήταν
Το πρώτο πρόγραμμα C κοιτάξαμε,

555
00:25:19,680 --> 00:25:22,840
ένα κανονικό, απλό πρόγραμμα
του είδους, μιλώντας σχετικά,

556
00:25:22,840 --> 00:25:24,620
όπου, εκτυπώνει, Hello World.

557
00:25:24,620 --> 00:25:27,610
Και υπενθυμίζουν ότι είπα, η διαδικασία
ότι ο κώδικας πηγής περνά

558
00:25:27,610 --> 00:25:28,430
Είναι ακριβώς αυτό.

559
00:25:28,430 --> 00:25:31,180
Μπορείτε να πάρετε τον πηγαίο κώδικα σας, περάστε
μέσω ενός μεταγλωττιστή, όπως Clang,

560
00:25:31,180 --> 00:25:34,650
και έξω έρχεται αντικειμενικού κώδικα, ότι
θα μπορούσε να μοιάζει με αυτό, μηδενικά και μονάδες

561
00:25:34,650 --> 00:25:37,880
ότι η CPU του υπολογιστή, κεντρική
μονάδα επεξεργασίας ή τον εγκέφαλο,

562
00:25:37,880 --> 00:25:39,760
τελικά καταλαβαίνει.

563
00:25:39,760 --> 00:25:42,460
>> Αποδεικνύεται ότι αυτό είναι ένα
κομμάτι μιας υπεραπλούστευση,

564
00:25:42,460 --> 00:25:44,480
ότι είμαστε τώρα σε μια
θέση να δώσουμε έμφαση, εκτός

565
00:25:44,480 --> 00:25:46,720
να καταλάβει τι πραγματικά έχει
συμβαίνει κάτω από το καπό

566
00:25:46,720 --> 00:25:48,600
κάθε φορά που θα εκτελέσετε
Clang, ή γενικότερα,

567
00:25:48,600 --> 00:25:53,040
κάθε φορά που κάνετε ένα πρόγραμμα,
Κάντε χρήση και CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Ειδικότερα, τέτοια πράγματα
αυτή είναι η πρώτη που παράγονται,

569
00:25:56,760 --> 00:25:58,684
όταν για πρώτη φορά καταρτίσει το πρόγραμμά σας.

570
00:25:58,684 --> 00:26:00,600
Με άλλα λόγια, όταν
πάρετε τον πηγαίο κώδικα

571
00:26:00,600 --> 00:26:04,390
και το υπολογίσουν, τι η πρώτη
που εξάγονται από Clang

572
00:26:04,390 --> 00:26:06,370
Είναι κάτι γνωστό ως κώδικα assembly.

573
00:26:06,370 --> 00:26:08,990
Και στην πραγματικότητα, μοιάζει ακριβώς με αυτό.

574
00:26:08,990 --> 00:26:11,170
>> Έτρεξα μια εντολή στη
γραμμή εντολών νωρίτερα.

575
00:26:11,170 --> 00:26:16,260
Hello.c Clang παύλα κεφαλαίου της,
και αυτό δημιούργησε ένα αρχείο

576
00:26:16,260 --> 00:26:19,490
για μένα που ονομάζεται hello.s,
μέσα από τις οποίες ήταν ακριβώς

577
00:26:19,490 --> 00:26:22,290
αυτά τα περιεχόμενα, και λίγο πιο
παραπάνω και λίγο περισσότερο κατωτέρω,

578
00:26:22,290 --> 00:26:25,080
αλλά έχω βάλει το juiciest
πληροφορίες εδώ στην οθόνη.

579
00:26:25,080 --> 00:26:29,190
Και αν κοιτάξετε προσεκτικά, θα δείτε
τουλάχιστον μερικά γνωστά λέξεις-κλειδιά.

580
00:26:29,190 --> 00:26:31,330
Έχουμε κύρια στην κορυφή.

581
00:26:31,330 --> 00:26:35,140
Έχουμε printf κάτω στη μέση.

582
00:26:35,140 --> 00:26:38,670
Και έχουμε επίσης hello world
ανάστροφη κάθετο n σε εισαγωγικά ορίζονται κατωτέρω.

583
00:26:38,670 --> 00:26:42,450
>> Και ό, τι άλλο εδώ
είναι οδηγίες πολύ χαμηλό επίπεδο

584
00:26:42,450 --> 00:26:45,500
ότι η CPU του υπολογιστή καταλαβαίνει.

585
00:26:45,500 --> 00:26:50,090
CPU οδηγίες που κινούνται μνήμη
γύρω, ότι οι χορδές φορτίο από τη μνήμη,

586
00:26:50,090 --> 00:26:52,750
και, τελικά, εκτύπωση
τα πράγματα στην οθόνη.

587
00:26:52,750 --> 00:26:56,780
Τώρα τι θα συμβεί αν μετά
αυτός ο κώδικας συνέλευση δημιουργείται;

588
00:26:56,780 --> 00:26:59,964
Τελικά, το κάνετε, πράγματι,
εξακολουθούν να παράγουν κώδικα αντικειμένου.

589
00:26:59,964 --> 00:27:02,630
Αλλά τα βήματα που έχουν πραγματικά
συνεχίζεται κάτω από την κουκούλα

590
00:27:02,630 --> 00:27:04,180
κοιτάξουμε λίγο περισσότερο σαν αυτό.

591
00:27:04,180 --> 00:27:08,390
Ο πηγαίος κώδικας καθίσταται κώδικα assembly,
το οποίο στη συνέχεια γίνεται αντικειμενικού κώδικα,

592
00:27:08,390 --> 00:27:11,930
και οι λειτουργικές λέξεις εδώ είναι ότι,
κατά τη μεταγλώττιση του πηγαίου κώδικα σας,

593
00:27:11,930 --> 00:27:16,300
έξω έρχεται κώδικα assembly, και στη συνέχεια,
όταν συναρμολογείτε τον κωδικό σας συγκρότημα,

594
00:27:16,300 --> 00:27:17,800
έρχεται έξω αντικειμενικού κώδικα.

595
00:27:17,800 --> 00:27:20,360
>> Τώρα Clang είναι εξαιρετικά περίπλοκο,
σαν μια παρτίδα των compilers,

596
00:27:20,360 --> 00:27:23,151
και να κάνει όλα αυτά τα βήματα
μαζί, και αυτό δεν σημαίνει απαραίτητα

597
00:27:23,151 --> 00:27:25,360
εξόδου κάθε ενδιάμεσο
αρχεία που μπορείτε ακόμη και να δείτε.

598
00:27:25,360 --> 00:27:28,400
Συντάσσει απλά πράγματα,
που είναι ο γενικός όρος που

599
00:27:28,400 --> 00:27:30,000
περιγράφει όλη διαδικασία.

600
00:27:30,000 --> 00:27:32,000
Αλλά εάν θέλετε πραγματικά
να είναι συγκεκριμένα, δεν υπάρχει

601
00:27:32,000 --> 00:27:34,330
πολύ περισσότερο συμβαίνει εκεί καθώς και.

602
00:27:34,330 --> 00:27:38,860
>> Αλλά ας εξετάσουμε τώρα ότι ακόμη και
ότι σούπερ απλό πρόγραμμα, hello.c,

603
00:27:38,860 --> 00:27:40,540
ονομάζεται συνάρτηση.

604
00:27:40,540 --> 00:27:41,870
Κάλεσε printf.

605
00:27:41,870 --> 00:27:46,900
Αλλά δεν είχα γράψει printf, πράγματι,
που έρχεται με c, να το πω έτσι.

606
00:27:46,900 --> 00:27:51,139
Είναι μια λειτουργία ανάκλησης που είναι
δηλώνονται στο πρότυπο io.h, η οποία

607
00:27:51,139 --> 00:27:53,180
είναι ένα αρχείο κεφαλίδας, το οποίο
είναι ένα θέμα που πραγματικά θα

608
00:27:53,180 --> 00:27:55,780
βουτιά σε περισσότερο βάθος πριν από καιρό.

609
00:27:55,780 --> 00:27:58,000
Αλλά ένα αρχείο κεφαλίδας είναι
συνήθως συνοδεύεται

610
00:27:58,000 --> 00:28:02,920
από ένα αρχείο κώδικα, το αρχείο πηγαίου κώδικα, ώστε
σαν υπάρχει πρότυπο io.h.

611
00:28:02,920 --> 00:28:05,930
>> Κάποτε, κάποιος,
ή Κάποιοι, έγραψε επίσης

612
00:28:05,930 --> 00:28:11,040
ένα αρχείο που ονομάζεται πρότυπο io.c, σε
την οποία η πραγματική τους ορισμούς,

613
00:28:11,040 --> 00:28:15,220
ή υλοποιήσεις της printf,
και τσαμπιά από άλλες λειτουργίες,

614
00:28:15,220 --> 00:28:16,870
Τα πραγματικά γραφτεί.

615
00:28:16,870 --> 00:28:22,140
Έτσι, δεδομένου ότι, αν λάβουμε υπόψη έχοντας
εδώ στα αριστερά, hello.c, ότι όταν

616
00:28:22,140 --> 00:28:26,250
καταρτίζονται, μας δίνει hello.s, ακόμη και αν
Clang δεν ενοχλεί εξοικονόμηση σε ένα μέρος

617
00:28:26,250 --> 00:28:31,360
μπορούμε να το δούμε, και ότι ο κώδικας συναρμολόγησης
παίρνει συναρμολογούνται σε hello.o, η οποία

618
00:28:31,360 --> 00:28:34,630
Είναι, πράγματι, το προεπιλεγμένο όνομα
δίνεται κάθε φορά που μεταγλωτίσουμε

619
00:28:34,630 --> 00:28:39,350
κώδικα σε κώδικα αντικειμένου, αλλά δεν είναι
αρκετά έτοιμος για να το εκτελέσει ακόμα,

620
00:28:39,350 --> 00:28:41,460
γιατί ένα άλλο βήμα
πρέπει να συμβεί, και έχει

621
00:28:41,460 --> 00:28:44,440
συμβαίνει για τους λίγους παρελθόν
εβδομάδες, ίσως εν αγνοία σας.

622
00:28:44,440 --> 00:28:47,290
>> Συγκεκριμένα κάπου
σε CS50 IDE, και αυτό,

623
00:28:47,290 --> 00:28:49,870
πάρα πολύ, θα είναι ένα κομμάτι από ένα
υπεραπλούστευση για μια στιγμή,

624
00:28:49,870 --> 00:28:54,670
υπάρχει, ή ήταν κι έναν καιρό,
ένα αρχείο που ονομάζεται πρότυπο io.c,

625
00:28:54,670 --> 00:28:58,440
ότι κάποιος συγκεντρώνονται σε
πρότυπο io.s ή το ισοδύναμο,

626
00:28:58,440 --> 00:29:02,010
ότι τότε κάποιος συναρμολογούνται
σε τυποποιημένα io.o,

627
00:29:02,010 --> 00:29:04,600
ή αποδεικνύεται σε ένα
ελαφρώς διαφορετικό αρχείο

628
00:29:04,600 --> 00:29:07,220
μορφή που μπορεί να έχει διαφορετική
επέκταση αρχείου συνολικά,

629
00:29:07,220 --> 00:29:11,720
αλλά θεωρητικά και εννοιολογικά, ακριβώς
Στα στάδια αυτά έπρεπε να συμβεί σε κάποια μορφή.

630
00:29:11,720 --> 00:29:14,060
Ποια είναι να πούμε, ότι τώρα
όταν γράφω ένα πρόγραμμα,

631
00:29:14,060 --> 00:29:17,870
hello.c, ότι ακριβώς λέει, hello world,
και είμαι με τη χρήση κώδικα κάποιου άλλου

632
00:29:17,870 --> 00:29:22,480
όπως printf, η οποία ήταν μια φορά κι έναν
χρόνο, σε ένα αρχείο που ονομάζεται πρότυπο io.c,

633
00:29:22,480 --> 00:29:26,390
τότε με κάποιο τρόπο πρέπει να πάρω μου
Κωδικός αντικειμένου, μηδενικά και μονάδες μου,

634
00:29:26,390 --> 00:29:29,260
και το αντικείμενο του εν λόγω προσώπου
κώδικα, ή μηδενικά και αυτοί,

635
00:29:29,260 --> 00:29:34,970
και με κάποιο τρόπο να τα συνδέσει μεταξύ τους σε
ένα τελικό αρχείο, που ονομάζεται Γεια σας, ότι

636
00:29:34,970 --> 00:29:38,070
έχει όλα τα μηδενικά και
αυτά από την κύρια λειτουργία μου,

637
00:29:38,070 --> 00:29:40,830
και όλα τα μηδενικά
και εκείνες για printf.

638
00:29:40,830 --> 00:29:44,900
>> Και πράγματι, ότι η τελευταία διαδικασία είναι
ονομάζεται, που συνδέει τον κωδικό σας αντικείμενο.

639
00:29:44,900 --> 00:29:47,490
Η έξοδος του οποίου
είναι ένα εκτελέσιμο αρχείο.

640
00:29:47,490 --> 00:29:49,780
Έτσι, για να είμαστε δίκαιοι, κατά τη
τέλος της ημέρας, τίποτα

641
00:29:49,780 --> 00:29:52,660
έχει αλλάξει από μία εβδομάδα, όταν θα
για πρώτη φορά άρχισε την κατάρτιση προγραμμάτων.

642
00:29:52,660 --> 00:29:55,200
Πράγματι, όλα αυτά ήταν
συμβαίνει κάτω από την κουκούλα,

643
00:29:55,200 --> 00:29:57,241
αλλά τώρα είμαστε σε θέση
όπου μπορούμε πραγματικά

644
00:29:57,241 --> 00:29:58,794
πειράζω εκτός αυτών των διαφόρων σταδίων.

645
00:29:58,794 --> 00:30:00,710
Και πράγματι, στο τέλος
της ημέρας, είμαστε ακόμα

646
00:30:00,710 --> 00:30:04,480
αριστερά με μηδενικά και μονάδες, οι οποίες
Είναι πραγματικά μια μεγάλη segue τώρα

647
00:30:04,480 --> 00:30:08,620
σε μια άλλη ικανότητα C, ότι
Εμείς δεν είχαμε να αξιοποιήσουν πιο πιθανό

648
00:30:08,620 --> 00:30:11,250
μέχρι σήμερα, γνωστό ως φορείς bitwise.

649
00:30:11,250 --> 00:30:15,220
Με άλλα λόγια, μέχρι σήμερα, οποτεδήποτε έχουμε
ασχολήθηκε με δεδομένα σε μεταβλητές C ή σε C,

650
00:30:15,220 --> 00:30:17,660
είχαμε τα πράγματα όπως
χαρακτήρες και άρματα και ins

651
00:30:17,660 --> 00:30:21,990
και λαχταρά και δίκλινα και τα παρόμοια, αλλά
όλα αυτά είναι τουλάχιστον οκτώ bits.

652
00:30:21,990 --> 00:30:25,550
Έχουμε ποτέ δεν είναι ακόμη σε θέση να
χειριστείτε μεμονωμένα κομμάτια,

653
00:30:25,550 --> 00:30:28,970
ακόμη και αν ένα άτομο λίγο, εμείς
γνωρίζουν, μπορεί να αντιπροσωπεύει ένα 0 και 1.

654
00:30:28,970 --> 00:30:32,640
Τώρα αποδεικνύεται ότι σε C, που
μπορούν να αποκτήσουν πρόσβαση σε μεμονωμένα κομμάτια,

655
00:30:32,640 --> 00:30:35,530
αν γνωρίζετε τη σύνταξη,
με την οποία για να πάρει σε αυτά.

656
00:30:35,530 --> 00:30:38,010
>> Έτσι, ας ρίξουμε μια ματιά
στην bitwise φορείς.

657
00:30:38,010 --> 00:30:41,700
Έτσι απεικονίζονται εδώ είναι μερικά σύμβολα που
έχουμε, το είδος, το είδος, ξαναδεί.

658
00:30:41,700 --> 00:30:45,580
Βλέπω ένα σύμβολο, μια κάθετη
μπαρ, και κάποιοι άλλοι, καθώς και,

659
00:30:45,580 --> 00:30:49,430
και θυμηθούμε ότι εμπορικό και εμπορικό και
Είναι κάτι που έχουμε ξαναδεί.

660
00:30:49,430 --> 00:30:54,060
Η λογική ΚΑΙ χειριστή, όπου έχετε
δυο μαζί, ή το λογικό OR

661
00:30:54,060 --> 00:30:56,300
χειριστή, όπου μπορείτε
έχουν δύο κάθετες μπάρες.

662
00:30:56,300 --> 00:31:00,550
Bitwise φορείς, η οποία θα
δείτε λειτουργούν σε κομμάτια ξεχωριστά,

663
00:31:00,550 --> 00:31:03,810
απλά χρησιμοποιήστε ένα μοναδικό σύμβολο, ένα
μονή κάθετη γραμμή, το καρέ σύμβολο

664
00:31:03,810 --> 00:31:06,620
έρχεται το επόμενο, το μικρό
περισπωμένη, και στη συνέχεια αφήνεται

665
00:31:06,620 --> 00:31:08,990
στήριγμα αριστερά στήριγμα, ή
δεξιά παρένθεση δεξιά αγκύλη.

666
00:31:08,990 --> 00:31:10,770
Κάθε ένα από αυτά έχει διαφορετικές σημασίες.

667
00:31:10,770 --> 00:31:11,950
>> Στην πραγματικότητα, ας ρίξουμε μια ματιά.

668
00:31:11,950 --> 00:31:16,560
Ας πάμε παλιό σχολείο σήμερα, και η χρήση
μια οθόνη αφής από χτες,

669
00:31:16,560 --> 00:31:18,002
γνωστή ως ένα λευκό του σκάφους.

670
00:31:18,002 --> 00:31:19,710
Και αυτό το λευκό του σκάφους
θα μας επιτρέψει

671
00:31:19,710 --> 00:31:27,360
να εκφράσω μερικές αρκετά απλά σύμβολα,
ή μάλλον κάποιοι αρκετά απλές φόρμουλες,

672
00:31:27,360 --> 00:31:29,560
να μπορέσουμε στη συνέχεια, τελικά,
μόχλευση, προκειμένου

673
00:31:29,560 --> 00:31:33,230
να έχουν πρόσβαση σε μεμονωμένες
bits μέσα σε ένα πρόγραμμα C.

674
00:31:33,230 --> 00:31:34,480
Με άλλα λόγια, ας κάνουμε αυτό.

675
00:31:34,480 --> 00:31:37,080
Ας μιλήσουμε πρώτα για την
στιγμή για σύμβολο,

676
00:31:37,080 --> 00:31:39,560
το οποίο είναι το bitwise τελεστή AND.

677
00:31:39,560 --> 00:31:42,130
Με άλλα λόγια, πρόκειται για
ένας φορέας που να επιτρέπει

678
00:31:42,130 --> 00:31:45,930
Θέλω να έχουμε μια μεταβλητή αριστερά
τυπικά, και μια μεταβλητή δεξιά,

679
00:31:45,930 --> 00:31:50,640
ή μια συγκεκριμένη τιμή, ότι αν και
μαζί, μου δίνει ένα τελικό αποτέλεσμα.

680
00:31:50,640 --> 00:31:51,560
Λοιπόν, τι εννοώ;

681
00:31:51,560 --> 00:31:54,840
Εάν σε ένα πρόγραμμα, έχετε μια μεταβλητή
ότι τα καταστήματα μία από αυτές τις αξίες,

682
00:31:54,840 --> 00:31:58,000
ή ας το κρατήσουμε απλό, και απλά
γράψτε μηδέν και ατομικά,

683
00:31:58,000 --> 00:32:00,940
εδώ είναι το πώς λειτουργεί ο χειριστής ampersand.

684
00:32:00,940 --> 00:32:06,400
0 0 εμπορικό και πρόκειται να ισούται με 0.

685
00:32:06,400 --> 00:32:07,210
Τώρα γιατί συμβαίνει αυτό;

686
00:32:07,210 --> 00:32:09,291
>> Είναι πολύ παρόμοια με
Boolean εκφράσεις,

687
00:32:09,291 --> 00:32:10,540
ότι έχουμε συζητήσει μέχρι στιγμής.

688
00:32:10,540 --> 00:32:15,800
Αν νομίζετε ότι μετά από όλα, το 0 είναι
ψευδείς, 0 είναι ψευδή, ψευδής και ψευδής

689
00:32:15,800 --> 00:32:18,720
είναι, όπως έχουμε συζητήσει
λογικά, επίσης εσφαλμένη.

690
00:32:18,720 --> 00:32:20,270
Έτσι έχουμε το 0 ως εδώ καλά.

691
00:32:20,270 --> 00:32:24,390
Εάν πάρετε 0 Ampersand
1, και ότι, επίσης,

692
00:32:24,390 --> 00:32:29,890
πρόκειται να είναι μηδέν, επειδή γι 'αυτό
έκφραση αριστερή πλευρά για να είναι αληθινό ή 1,

693
00:32:29,890 --> 00:32:32,360
θα πρέπει να είναι αληθινή και πραγματική.

694
00:32:32,360 --> 00:32:36,320
Αλλά εδώ έχουμε ψευδή
και αλήθεια, ή 0 και 1.

695
00:32:36,320 --> 00:32:42,000
Τώρα πάλι, αν έχουμε 1 Ampersand
0, ότι, επίσης, πρόκειται να είναι 0,

696
00:32:42,000 --> 00:32:47,240
και αν έχουμε 1 ampersand 1,
Τέλος έχουμε ένα 1 bit.

697
00:32:47,240 --> 00:32:50,340
Έτσι με άλλα λόγια, αν δεν κάνει
κάτι ενδιαφέρον με αυτόν τον τελεστή

698
00:32:50,340 --> 00:32:51,850
ακριβώς ακόμα, ο φορέας αυτός Ampersand.

699
00:32:51,850 --> 00:32:53,780
Είναι το bitwise τελεστή AND.

700
00:32:53,780 --> 00:32:57,290
Αλλά αυτά είναι τα συστατικά
μέσω του οποίου μπορούμε να κάνουμε

701
00:32:57,290 --> 00:32:59,240
ενδιαφέροντα πράγματα, όπως θα δούμε σύντομα.

702
00:32:59,240 --> 00:33:02,790
>> Τώρα, ας δούμε λίγο την ενιαία
κάθετη μπάρα εδώ στα δεξιά.

703
00:33:02,790 --> 00:33:06,710
Αν έχω ένα bit 0 και Ι
Ή με το bitwise

704
00:33:06,710 --> 00:33:11,030
Χειριστή ή άλλο bit 0,
ότι πρόκειται να μου δώσει 0.

705
00:33:11,030 --> 00:33:17,540
Αν πάρω ένα bit 0 και OR με
το bit 1, τότε είμαι πρόκειται να πάρει 1.

706
00:33:17,540 --> 00:33:19,830
Και στην πραγματικότητα, μόνο για
σαφήνειας, επιτρέψτε μου να πάω πίσω,

707
00:33:19,830 --> 00:33:23,380
έτσι ώστε κάθετες μπάρες μου
Δεν είναι λάθος για 1 '.

708
00:33:23,380 --> 00:33:26,560
Επιτρέψτε μου να ξαναγράψει το σύνολο του
1 μου είναι λίγο πιο

709
00:33:26,560 --> 00:33:32,700
σαφώς, έτσι ώστε να δούμε την επόμενη, αν
έχουν 1 ή 0, αυτό πρόκειται να είναι ένα 1,

710
00:33:32,700 --> 00:33:39,060
και αν έχω ένα 1 ή 1 ότι,
πάρα πολύ, θα είναι 1.

711
00:33:39,060 --> 00:33:42,900
Έτσι μπορείτε να δείτε ότι η λογική OR
φορέας συμπεριφέρεται πολύ διαφορετικά.

712
00:33:42,900 --> 00:33:48,070
Αυτό μου δίνει 0 ή 0 0 μου δίνει, αλλά
κάθε άλλος συνδυασμός μου δίνει 1.

713
00:33:48,070 --> 00:33:52,480
Εφ 'όσον έχω ένα 1 στην
τύπο, το αποτέλεσμα θα είναι 1.

714
00:33:52,480 --> 00:33:55,580
>> Σε αντίθεση με το ΚΑΙ
χειριστής, ο σύμβολο,

715
00:33:55,580 --> 00:34:00,940
μόνο αν έχω δύο 1 στο
εξίσωση, μπορώ πραγματικά να πάρετε μια 1 έξω.

716
00:34:00,940 --> 00:34:02,850
Τώρα υπάρχει μια μερικά άλλα
φορέων, καθώς και.

717
00:34:02,850 --> 00:34:04,810
Ένας από αυτούς είναι λίγο πιο περίπλοκη.

718
00:34:04,810 --> 00:34:07,980
Επιτρέψτε μου λοιπόν να πάει μπροστά και να διαγράψει
αυτό για να ελευθερώσετε λίγο χώρο.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
Και ας ρίξουμε μια ματιά στο
δρομέα σύμβολο, μόνο για μια στιγμή.

721
00:34:16,460 --> 00:34:18,210
Αυτό είναι συνήθως ένα
χαρακτήρας μπορείτε να πληκτρολογήσετε

722
00:34:18,210 --> 00:34:21,420
στην εκμετάλλευσή του πληκτρολογίου σας και το Shift
Στη συνέχεια ένας από τους αριθμούς σας στην κορυφή των ΗΠΑ

723
00:34:21,420 --> 00:34:22,250
πληκτρολόγιο.

724
00:34:22,250 --> 00:34:26,190
>> Έτσι, αυτό είναι το αποκλειστικό
Ή φορέα, αποκλειστικό OR.

725
00:34:26,190 --> 00:34:27,790
Έτσι, είδαμε μόνο τον φορέα εκμετάλλευσης ή.

726
00:34:27,790 --> 00:34:29,348
Αυτό είναι ο αποκλειστικός ή φορέα.

727
00:34:29,348 --> 00:34:30,639
Ποια είναι πραγματικά η διαφορά;

728
00:34:30,639 --> 00:34:34,570
Λοιπόν ας δούμε τον τύπο,
και χρησιμοποιήστε το σαν συστατικά τελικά.

729
00:34:34,570 --> 00:34:37,690
0 0 XOR.

730
00:34:37,690 --> 00:34:39,650
Πάω να πω είναι πάντα 0.

731
00:34:39,650 --> 00:34:41,400
Αυτός είναι ο ορισμός του XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 θα είναι 1.

733
00:34:47,104 --> 00:34:58,810
1 0 XOR πρόκειται να είναι 1,
και 1 XOR 1 πρόκειται να είναι;

734
00:34:58,810 --> 00:34:59,890
Λάθος;

735
00:34:59,890 --> 00:35:00,520
Ή δεξιά;

736
00:35:00,520 --> 00:35:01,860
Δεν γνωρίζω.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Τώρα, τι συμβαίνει εδώ;

739
00:35:04,700 --> 00:35:06,630
Καλά σκεφτείτε το
το όνομα του εν λόγω οργανισμού.

740
00:35:06,630 --> 00:35:09,980
Αποκλειστικό Ή, έτσι ώστε ο
όνομα, είδος, προτείνει,

741
00:35:09,980 --> 00:35:13,940
η απάντηση είναι μόνο θα είναι
α 1, εάν οι είσοδοι είναι αποκλειστική,

742
00:35:13,940 --> 00:35:15,560
αποκλειστικά διαφορετικά.

743
00:35:15,560 --> 00:35:18,170
Μέχρι εδώ οι είσοδοι είναι η
ίδιο, έτσι ώστε η έξοδος είναι μηδέν.

744
00:35:18,170 --> 00:35:20,700
Εδώ οι είσοδοι είναι η
ίδιο, έτσι ώστε η έξοδος είναι μηδέν.

745
00:35:20,700 --> 00:35:25,640
Εδώ είναι οι έξοδοι είναι διαφορετικές,
είναι αποκλειστικό, και έτσι η έξοδος είναι 1.

746
00:35:25,640 --> 00:35:28,190
Έτσι είναι πολύ παρόμοια με
Και, είναι πολύ παρόμοια,

747
00:35:28,190 --> 00:35:32,760
ή μάλλον είναι πολύ παρόμοια με
Ή, αλλά μόνο σε ένα αποκλειστικό τρόπο.

748
00:35:32,760 --> 00:35:36,210
Αυτός δεν είναι πλέον ένα 1,
επειδή έχουμε δύο 1, η

749
00:35:36,210 --> 00:35:38,621
και όχι αποκλειστικά, μόνο ένα από αυτά.

750
00:35:38,621 --> 00:35:39,120
Εντάξει.

751
00:35:39,120 --> 00:35:40,080
Τι γίνεται με τους άλλους;

752
00:35:40,080 --> 00:35:44,220
Λοιπόν η περισπωμένη, εν τω μεταξύ, είναι
πραγματικά ωραίο και απλό, ευτυχώς.

753
00:35:44,220 --> 00:35:46,410
Και αυτό είναι ένα μοναδιαίος
φορέα, το οποίο σημαίνει

754
00:35:46,410 --> 00:35:50,400
αυτό είναι εφαρμόστηκαν μόνο σε μία είσοδο,
ένα τελεστή, να το πω έτσι.

755
00:35:50,400 --> 00:35:51,800
Όχι σε αριστερό και το δικαίωμα.

756
00:35:51,800 --> 00:35:56,050
Με άλλα λόγια, αν πάρετε περισπωμένη του
0, η απάντηση θα είναι το αντίθετο.

757
00:35:56,050 --> 00:35:59,710
Και αν πάρετε περισπωμένη 1, η
απάντηση θα είναι εκεί το αντίθετο.

758
00:35:59,710 --> 00:36:02,570
Έτσι, η περισπωμένη χειριστής
ένας τρόπος αναιρώντας λίγο,

759
00:36:02,570 --> 00:36:06,000
ή να ρίχνεις ένα κομμάτι από
0 έως 1, ή 1 έως μηδέν.

760
00:36:06,000 --> 00:36:09,820
>> Και αυτό μας αφήνει επιτέλους
με μόλις δύο τελικούς φορείς,

761
00:36:09,820 --> 00:36:13,840
η λεγόμενη αριστερή στροφή, και η
λεγόμενη δεξιά στροφή χειριστή.

762
00:36:13,840 --> 00:36:16,620
Ας ρίξουμε μια ματιά στο πώς αυτά τα εργασία.

763
00:36:16,620 --> 00:36:20,780
Ο χειριστής αριστερή στροφή, γραπτή
με δύο αγκύλες, όπως ότι,

764
00:36:20,780 --> 00:36:22,110
λειτουργεί ως εξής.

765
00:36:22,110 --> 00:36:27,390
Εάν η είσοδος μου, ή τελεστή μου, προς τα αριστερά
χειριστής αλλαγή είναι πολύ απλά 1.

766
00:36:27,390 --> 00:36:33,750
Και εγώ τότε πείτε στον υπολογιστή να
αριστερή στροφή ότι το 1, δηλαδή επτά θέσεις,

767
00:36:33,750 --> 00:36:37,150
το αποτέλεσμα είναι σαν να
κάνει αυτό το 1, και να το μετακινήσετε

768
00:36:37,150 --> 00:36:40,160
επτά θέσεις πάνω στην
αριστερά, και από προεπιλογή,

769
00:36:40,160 --> 00:36:42,270
θα πάμε να υποθέσουμε ότι
ο χώρος προς τα δεξιά

770
00:36:42,270 --> 00:36:44,080
πρόκειται να παραγεμισμένο με μηδενικά.

771
00:36:44,080 --> 00:36:50,316
Με άλλα λόγια, 1 αριστερή στροφή 7 πρόκειται
να μου δώσει ότι το 1, ακολουθούμενο από 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 μηδενικά.

773
00:36:54,060 --> 00:36:57,380
Έτσι, κατά κάποιο τρόπο, αυτό σας επιτρέπει να
να λάβει ένα μικρό αριθμό όπως το 1,

774
00:36:57,380 --> 00:37:00,740
και σαφώς αυτό κάνει πολύ
πολύ, πολύ μεγαλύτερο με αυτόν τον τρόπο,

775
00:37:00,740 --> 00:37:06,460
αλλά είμαστε πραγματικά πρόκειται να δείτε
πιο έξυπνη προσεγγίσεις για αυτό

776
00:37:06,460 --> 00:37:08,080
Αντ 'αυτού, καθώς και,

777
00:37:08,080 --> 00:37:08,720
>> Εντάξει.

778
00:37:08,720 --> 00:37:10,060
Αυτό είναι για τρεις εβδομάδες.

779
00:37:10,060 --> 00:37:11,400
Θα σας δούμε την επόμενη φορά.

780
00:37:11,400 --> 00:37:12,770
Αυτό ήταν CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [Παίζει μουσική]

783
00:37:22,243 --> 00:37:25,766
>> ΟΜΙΛΗΤΗΣ 1: Ήταν στο σνακ
bar τρώγοντας ένα ζεστό φοντάν παγωτό.

784
00:37:25,766 --> 00:37:28,090
Εκείνος τα είχε όλα πάνω από το πρόσωπό του.

785
00:37:28,090 --> 00:37:30,506
Φοράει ότι η σοκολάτα σαν μια γενειάδα

786
00:37:30,506 --> 00:37:31,756
ΟΜΙΛΗΤΗΣ 2: Τι κάνεις;

787
00:37:31,756 --> 00:37:32,422
ΟΜΙΛΗΤΗΣ 3: Χμμμ;

788
00:37:32,422 --> 00:37:33,500
Τι?

789
00:37:33,500 --> 00:37:36,800
>> ΟΜΙΛΗΤΗΣ 2: Μήπως ακριβώς διπλή ύφεση;

790
00:37:36,800 --> 00:37:38,585
Μπορείτε διπλό βουτηγμένα το τσιπ.

791
00:37:38,585 --> 00:37:39,460
ΟΜΙΛΗΤΗΣ 3: Με συγχωρείτε.

792
00:37:39,460 --> 00:37:44,440
ΟΜΙΛΗΤΗΣ 2: Μπορείτε βυθίζεται το τσιπ, θα
πήρε ένα δάγκωμα, και θα επαναβυθίζεται.

793
00:37:44,440 --> 00:37:44,940
ΟΜΙΛΗΤΗΣ 3:

794
00:37:44,940 --> 00:37:48,440
ΟΜΙΛΗΤΗΣ 2: Έτσι, αυτό είναι σαν να βάζουμε
το σύνολο των δικαιωμάτων στόμα σας στο βουτιά.

795
00:37:48,440 --> 00:37:52,400
Την επόμενη φορά που παίρνετε ένα τσιπ,
απλά βουτιά μια φορά, και το τέλος αυτό.

796
00:37:52,400 --> 00:37:53,890
>> ΟΜΙΛΗΤΗΣ 3: Ξέρεις κάτι, Dan;

797
00:37:53,890 --> 00:37:58,006
Βυθίζετε τον τρόπο που θέλετε να βουτιά.

798
00:37:58,006 --> 00:38:01,900
Θα βουτιά με τον τρόπο που θέλω να βουτιά.

799
00:38:01,900 --> 00:38:03,194