1
00:00:00,000 --> 00:00:00,030

2
00:00:00,030 --> 00:00:00,460
>> DAVID Malan: Εντάξει.

3
00:00:00,460 --> 00:00:01,094
Είμαστε πίσω.

4
00:00:01,094 --> 00:00:04,260
Έτσι, σε αυτό το τμήμα σχετικά με τον προγραμματισμό τι
Σκέφτηκα ότι θα κάνουμε είναι ένας συνδυασμός πραγμάτων.

5
00:00:04,260 --> 00:00:06,340
Ένα, κάνετε λίγη
κάτι hands-on,

6
00:00:06,340 --> 00:00:08,690
αν και χρησιμοποιώντας μια πιο παιχνιδιάρικη
environment-- προγραμματισμού

7
00:00:08,690 --> 00:00:11,620
ένα που είναι εκδηλωτικός του
ακριβώς τα είδη των ιδεών

8
00:00:11,620 --> 00:00:14,220
έχουμε μιλήσει για,
αλλά λίγο πιο επίσημα.

9
00:00:14,220 --> 00:00:18,200
Δύο, να δούμε μερικά από τα
οι περισσότερες τεχνικές τρόπους

10
00:00:18,200 --> 00:00:21,520
ότι ένας προγραμματιστής θα λύσει πραγματικά
προβλήματα, όπως η αναζήτηση πρόβλημα

11
00:00:21,520 --> 00:00:24,530
ότι εξετάσαμε πριν και
Επίσης, μια πιο ριζικά

12
00:00:24,530 --> 00:00:26,020
ενδιαφέρον πρόβλημα της διαλογής.

13
00:00:26,020 --> 00:00:28,840
>> Εμείς μόλις ανέλαβε από το να πάει
ότι το τηλεφωνικό ήταν ταξινομημένο,

14
00:00:28,840 --> 00:00:31,980
αλλά αυτό από μόνο του είναι πραγματικά το είδος της μια
δύσκολο πρόβλημα με πολλούς διαφορετικούς τρόπους

15
00:00:31,980 --> 00:00:32,479
για την επίλυσή του.

16
00:00:32,479 --> 00:00:34,366
Έτσι θα χρησιμοποιήσουμε αυτά ως
μια κατηγορία προβλημάτων

17
00:00:34,366 --> 00:00:36,740
εκπρόσωπος των πραγμάτων που
θα μπορούσε να λυθεί σε γενικές γραμμές.

18
00:00:36,740 --> 00:00:38,980
Και τότε θα μιλήσουμε
σχετικά με κάποια λεπτομέρεια τι

19
00:00:38,980 --> 00:00:42,360
καλούνται δεδομένα structures--
φανταχτερό τρόπους, όπως συνδεδεμένες λίστες

20
00:00:42,360 --> 00:00:46,290
και οι πίνακες κατακερματισμού και δέντρα που
ένας προγραμματιστής θα είναι στην πραγματικότητα

21
00:00:46,290 --> 00:00:48,890
χρησιμοποιήσει και χρησιμοποιούν γενικά
σε έναν πίνακα για να ζωγραφίσει

22
00:00:48,890 --> 00:00:51,840
μια εικόνα του τι αυτός ή αυτή
οραματίζεται για την εφαρμογή

23
00:00:51,840 --> 00:00:52,980
κάποιο κομμάτι του λογισμικού.

24
00:00:52,980 --> 00:00:55,130
>> Έτσι, ας κάνουμε τα hands-on πρώτο τμήμα.

25
00:00:55,130 --> 00:01:00,090
Έτσι απλά λερώσετε τα χέρια σας με μια
περιβάλλον που ονομάζεται scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Αυτό είναι ένα εργαλείο που χρησιμοποιούμε
σε προπτυχιακό τάξη μας.

27
00:01:02,636 --> 00:01:04,510
Ακόμα κι αν αυτό είναι σχεδιασμένο
για τις ηλικίες 12 και πάνω,

28
00:01:04,510 --> 00:01:07,570
το χρησιμοποιούμε για την δημιουργία
μέρος αυτής της αρκετά ένα κομμάτι

29
00:01:07,570 --> 00:01:10,020
δεδομένου ότι είναι ένα ωραίο, διασκεδαστικό
γραφικό τρόπο μάθησης

30
00:01:10,020 --> 00:01:12,160
ένα μικρό κάτι για τον προγραμματισμό.

31
00:01:12,160 --> 00:01:17,600
Έτσι, το κεφάλι σε αυτό το URL, όπου μπορείτε
Πρέπει να δείτε μια σελίδα αρκετά όπως αυτό,

32
00:01:17,600 --> 00:01:23,330
και να προχωρήσει και κάντε κλικ
Γίνετε μέλος Scratch στην πάνω δεξιά

33
00:01:23,330 --> 00:01:28,300
και να επιλέξετε ένα όνομα χρήστη και ένα
κωδικό και τελικά να πάρει τον εαυτό σας

34
00:01:28,300 --> 00:01:29,970
μια account-- scratch.mit.edu.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Νόμιζα ότι είχα χρησιμοποιήσει αυτό ως ένα
ευκαιρία πρώτα να το αποδείξει αυτό.

37
00:01:34,665 --> 00:01:39,120
Ένα ερώτημα που τέθηκε κατά τη διάρκεια του διαλείμματος
για ποιο κωδικό μοιάζει πραγματικά.

38
00:01:39,120 --> 00:01:41,315
Και μιλούσαμε
κατά τη διάρκεια του διαλείμματος για το C,

39
00:01:41,315 --> 00:01:45,060
σε particular-- ιδιαίτερα ένα
χαμηλότερο επίπεδο σε μια παλαιότερη γλώσσα.

40
00:01:45,060 --> 00:01:47,750
Και εγώ απλά έκανα μια γρήγορη
Αναζήτηση στο Google για να βρείτε τον κωδικό C

41
00:01:47,750 --> 00:01:51,574
για δυαδική αναζήτηση, τον αλγόριθμο που θα
χρησιμοποιείται για την αναζήτηση το βιβλίο του τηλεφώνου νωρίτερα.

42
00:01:51,574 --> 00:01:54,240
Αυτό το συγκεκριμένο παράδειγμα, φυσικά,
δεν αναζητήσετε ένα τηλεφωνικό κατάλογο.

43
00:01:54,240 --> 00:01:57,840
Ψάχνει μόνο ένα σωρό
αριθμούς στη μνήμη του υπολογιστή.

44
00:01:57,840 --> 00:02:01,000
Αλλά αν θέλετε να πάρετε μόνο μια οπτική
αίσθηση του τι ένα πραγματικό προγραμματισμό

45
00:02:01,000 --> 00:02:05,370
γλώσσα μοιάζει, φαίνεται
ένα μικρό κάτι σαν αυτό.

46
00:02:05,370 --> 00:02:09,759
Γι 'αυτό είναι περίπου 20-plus,
30 ή έτσι γραμμές κώδικα,

47
00:02:09,759 --> 00:02:12,640
αλλά η συνομιλία μας
Ήταν έχοντας πάνω από διάλειμμα

48
00:02:12,640 --> 00:02:16,000
ήταν για το πώς αυτή η πραγματικότητα
παίρνει μεταμορφωθεί σε μηδενικά και μονάδες

49
00:02:16,000 --> 00:02:19,200
και αν δεν μπορείτε απλά να επανέλθει ότι
επεξεργαστεί και να πάει από μηδενικά και μονάδες

50
00:02:19,200 --> 00:02:20,210
πίσω στον κώδικα.

51
00:02:20,210 --> 00:02:22,620
>> Δυστυχώς, η διαδικασία
Είναι τόσο μετασχηματιστική

52
00:02:22,620 --> 00:02:24,890
ότι είναι πολύ πιο εύκολο στα λόγια παρά στην πράξη.

53
00:02:24,890 --> 00:02:29,400
Πήγα μπροστά και στην πραγματικότητα αποδείχθηκε
ότι το πρόγραμμα, δυαδική αναζήτηση,

54
00:02:29,400 --> 00:02:32,700
σε μηδενικά και μονάδες μέσω ενός
πρόγραμμα που ονομάζεται ο compiler ότι εγώ,

55
00:02:32,700 --> 00:02:34,400
τυχαίνει να έχουμε εδώ δικαίωμα στο Mac μου.

56
00:02:34,400 --> 00:02:37,850
Και αν κοιτάξετε στην οθόνη
Εδώ, με ιδιαίτερη έμφαση

57
00:02:37,850 --> 00:02:43,520
σε αυτά τα μεσαία έξι κίονες μόνο,
θα δείτε μόνο μηδενικά και μονάδες.

58
00:02:43,520 --> 00:02:48,290
Και αυτά είναι τα μηδενικά και αυτοί που
συνθέτουν ακριβώς αυτό το πρόγραμμα αναζήτησης.

59
00:02:48,290 --> 00:02:53,720
>> Και έτσι κάθε κομμάτι από πέντε κομμάτια,
κάθε byte από μηδενικά και αυτοί εδώ,

60
00:02:53,720 --> 00:02:57,310
αντιπροσωπεύουν κάποια εντολή
τυπικά μέσα από έναν υπολογιστή.

61
00:02:57,310 --> 00:03:00,730
Και στην πραγματικότητα, αν έχετε ακούσει το
σύνθημα μάρκετινγκ «Intel Inside» - δηλαδή,

62
00:03:00,730 --> 00:03:04,610
Φυσικά, απλά σημαίνει ότι έχετε ένα
Intel CPU ή τον εγκέφαλο στο εσωτερικό του υπολογιστή.

63
00:03:04,610 --> 00:03:08,000
Και τι σημαίνει αυτό ότι είναι μια CPU είναι
ότι έχετε ένα σύνολο εντολών,

64
00:03:08,000 --> 00:03:08,840
να το πω έτσι.

65
00:03:08,840 --> 00:03:11,620
>> Κάθε CPU στον κόσμο, πολλοί από
τους έκανε από την Intel αυτές τις μέρες,

66
00:03:11,620 --> 00:03:13,690
αντιλαμβάνεται ένα πεπερασμένο
αριθμός οδηγιών.

67
00:03:13,690 --> 00:03:18,690
Και αυτές οι οδηγίες είναι τόσο χαμηλό επίπεδο
ως προσθέσει αυτά τα δύο αριθμούς μαζί,

68
00:03:18,690 --> 00:03:22,560
πολλαπλασιάσουμε αυτά τα δύο αριθμούς μαζί,
μετακινήσετε αυτό το κομμάτι των δεδομένων από εδώ

69
00:03:22,560 --> 00:03:27,340
εδώ στη μνήμη, εκτός από αυτό
πληροφορίες από εδώ εδώ στη μνήμη,

70
00:03:27,340 --> 00:03:32,200
και έτσι forth-- τόσο πολύ, πολύ
χαμηλού επιπέδου, σχεδόν ηλεκτρονικών στοιχείων.

71
00:03:32,200 --> 00:03:34,780
Αλλά με αυτά τα μαθηματικές
λειτουργίες σε συνδυασμό

72
00:03:34,780 --> 00:03:37,410
με ό, τι συζητήσαμε νωρίτερα,
η αναπαράσταση των δεδομένων

73
00:03:37,410 --> 00:03:40,450
ως μηδενικά και μονάδες, μπορεί να
χτίζετε τα πάντα

74
00:03:40,450 --> 00:03:44,180
ότι ένας υπολογιστής μπορεί να κάνει σήμερα, αν
Είναι κειμένου, γραφικών, μουσικής,

75
00:03:44,180 --> 00:03:45,580
ή αλλιώς.

76
00:03:45,580 --> 00:03:49,450
>> Έτσι, αυτό είναι πολύ εύκολο να φτάσετε
χάνεται στα ζιζάνια του γρήγορα.

77
00:03:49,450 --> 00:03:52,150
Και υπάρχει πολλή
συντακτική προκλήσεις

78
00:03:52,150 --> 00:03:56,630
σύμφωνα με την οποία αν κάνετε το πιο απλό,
χαζό των typos κανένας από το πρόγραμμα

79
00:03:56,630 --> 00:03:57,860
θα λειτουργήσει απολύτως.

80
00:03:57,860 --> 00:04:00,366
Και έτσι αντί να χρησιμοποιεί ένα
γλώσσα όπως η C το πρωί,

81
00:04:00,366 --> 00:04:02,240
Σκέφτηκα ότι θα ήταν
πιο διασκεδαστικό να κάνουν πραγματικά

82
00:04:02,240 --> 00:04:04,840
κάτι πιο οπτική, η οποία
ενώ έχουν σχεδιαστεί για τα παιδιά

83
00:04:04,840 --> 00:04:08,079
είναι πραγματικά μια τέλεια εκδήλωση
ενός πραγματικού προγραμματισμού

84
00:04:08,079 --> 00:04:10,370
language-- συμβαίνει ακριβώς να
χρησιμοποιούν εικόνες αντί για κείμενο

85
00:04:10,370 --> 00:04:11,710
να εκπροσωπεί αυτές τις ιδέες.

86
00:04:11,710 --> 00:04:15,470
>> Έτσι, μόλις έχετε πράγματι
λογαριασμό στο scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
κάντε κλικ στο κουμπί Δημιουργία
Στην επάνω αριστερή πλευρά της ιστοσελίδας.

88
00:04:21,070 --> 00:04:24,620
Και θα πρέπει να δείτε ένα περιβάλλον όπως
το ένα είμαι έτοιμος να δείτε στην οθόνη μου

89
00:04:24,620 --> 00:04:26,310
εδώ.

90
00:04:26,310 --> 00:04:29,350
Και θα περάσετε λίγο
λίγο χρόνο παίζοντας εδώ.

91
00:04:29,350 --> 00:04:34,080
Ας δούμε αν μπορούμε, δεν μπορούμε όλοι να λύσει μερικά
προβλήματα μαζί με τον ακόλουθο τρόπο.

92
00:04:34,080 --> 00:04:39,420
>> Έτσι, αυτό που θα δείτε μέσα σε αυτό
environment-- και στην πραγματικότητα απλά αφήστε

93
00:04:39,420 --> 00:04:40,050
με παύση.

94
00:04:40,050 --> 00:04:42,680
Είναι κανείς δεν είναι εδώ;

95
00:04:42,680 --> 00:04:45,070
Όχι εδώ?

96
00:04:45,070 --> 00:04:45,800
ΕΝΤΆΞΕΙ.

97
00:04:45,800 --> 00:04:49,030
Έτσι, επιτρέψτε μου να επισημάνω μερικά
χαρακτηριστικά αυτού του περιβάλλοντος.

98
00:04:49,030 --> 00:04:55,024
>> Έτσι, στο επάνω αριστερό μέρος της οθόνης, εμείς
έχουν στάδιο Scratch, ώστε να μιλήσουν.

99
00:04:55,024 --> 00:04:57,440
Scratch δεν είναι μόνο το όνομα
αυτής της γλώσσας προγραμματισμού?

100
00:04:57,440 --> 00:05:00,356
είναι επίσης το όνομα του γάτα που
μπορείτε να δείτε από προεπιλογή εκεί στην πορτοκαλί.

101
00:05:00,356 --> 00:05:02,160
Είναι σε ένα στάδιο, έτσι
σαν περιέγραψα

102
00:05:02,160 --> 00:05:05,770
η χελώνα νωρίτερα ότι βρίσκονται σε ένα
ορθογώνιο λευκό περιβάλλον του σκάφους.

103
00:05:05,770 --> 00:05:09,800
κόσμο αυτή η γάτα έχει περιοριστεί εξ ολοκλήρου
σε αυτό το ορθογώνιο επάνω στην κορυφή εκεί.

104
00:05:09,800 --> 00:05:12,210
>> Εν τω μεταξύ, στη δεξιά
πλευρά εδώ, είναι

105
00:05:12,210 --> 00:05:15,610
απλά μια περιοχή σενάρια, ένα
κενή πλάκα αν θέλετε.

106
00:05:15,610 --> 00:05:18,590
Αυτό είναι όπου θα πάμε να γράψω
τα προγράμματά μας σε μια στιγμή.

107
00:05:18,590 --> 00:05:22,935
Και τα δομικά στοιχεία ότι θα
χρησιμοποιήσετε για να γράψω αυτό program-- το παζλ

108
00:05:22,935 --> 00:05:25,310
κομμάτια, αν είστε will--
εκείνους ακριβώς εδώ στη μέση,

109
00:05:25,310 --> 00:05:27,500
και από όπου και αν κατηγοριοποιούνται
με τη λειτουργικότητα.

110
00:05:27,500 --> 00:05:31,000
Έτσι, για παράδειγμα, Πάω να πάει μπροστά
και επιδεικνύουν τουλάχιστον μία από αυτές.

111
00:05:31,000 --> 00:05:33,690
Πάω να προχωρήσει και κάντε κλικ
η κατηγορία ελέγχου επάνω στην κορυφή.

112
00:05:33,690 --> 00:05:35,720
>> Αυτές είναι λοιπόν οι κατηγορίες επάνω στην κορυφή.

113
00:05:35,720 --> 00:05:39,410
Πάω να κάντε κλικ στην κατηγορία Ελέγχου.

114
00:05:39,410 --> 00:05:44,020
Αντίθετα, Πάω να κάνετε κλικ στο Εκδηλώσεις
κατηγορία, η ίδια η πρώτη επάνω στην κορυφή.

115
00:05:44,020 --> 00:05:47,790
Και αν θέλετε να ακολουθήσετε μαζί ακόμα
όπως κάνουμε αυτό, είστε πολύ ευπρόσδεκτοι να.

116
00:05:47,790 --> 00:05:52,180
Πάω να κάνετε κλικ και να σύρετε αυτό
πρώτο, "όταν κάνετε κλικ πράσινη σημαία."

117
00:05:52,180 --> 00:05:58,410
Και τότε εγώ είμαι πρόκειται να το ρίξει λίγο
περίπου στην κορυφή κενό πλάκες μου.

118
00:05:58,410 --> 00:06:01,450
>> Και τι είναι ωραίο για το Ξυστό
είναι ότι αυτό το κομμάτι του παζλ, όταν

119
00:06:01,450 --> 00:06:04,560
συμπλέκονται με άλλα παζλ
κομμάτια, πρόκειται να κάνει κυριολεκτικά

120
00:06:04,560 --> 00:06:06,460
ό, τι αυτά τα κομμάτια του παζλ πει να κάνουμε.

121
00:06:06,460 --> 00:06:09,710
Έτσι, για παράδειγμα, Scratch είναι σωστό
τώρα στη μέση του κόσμου του.

122
00:06:09,710 --> 00:06:14,660
Πάω να πάει μπροστά και να επιλέξετε
Τώρα, ας πούμε, η κατηγορία κίνησης,

123
00:06:14,660 --> 00:06:18,000
αν θέλετε να κάνετε τα
τρόπο-- κατηγορία κίνησης.

124
00:06:18,000 --> 00:06:20,430
Και τώρα παρατηρήσετε έχω ένα ολόκληρο
μάτσο κομμάτια του παζλ εδώ

125
00:06:20,430 --> 00:06:23,370
ότι, και πάλι, το είδος του κάνει ό, τι λένε.

126
00:06:23,370 --> 00:06:28,110
Και Πάω να πάει μπροστά και να μεταφέρετε και
πτώση το μπλοκ κίνηση ακριβώς εδώ.

127
00:06:28,110 --> 00:06:31,860
>> Και παρατηρήσετε ότι μόλις φτάσετε
κοντά στο κάτω μέρος της "πράσινης σημαίας

128
00:06:31,860 --> 00:06:34,580
κλικ "κουμπί, ανακοίνωση
πώς εμφανίζεται μια λευκή γραμμή,

129
00:06:34,580 --> 00:06:36,950
σαν να είναι σχεδόν
μαγνητική, θέλει να πάει εκεί.

130
00:06:36,950 --> 00:06:43,070
Απλά ας πάει, και θα snap
μαζί και τα σχήματα θα ταιριάζουν.

131
00:06:43,070 --> 00:06:46,620
Και τώρα μπορείτε ίσως σχεδόν
μαντέψει όπου θα πάμε με αυτό.

132
00:06:46,620 --> 00:06:51,570
>> Αν κοιτάξετε στο στάδιο Scratch
εδώ και να κοιτάξουμε προς την κορυφή του,

133
00:06:51,570 --> 00:06:55,142
θα δείτε ένα κόκκινο φως, ένα
να σταματήσει σημάδι, και μια πράσινη σημαία.

134
00:06:55,142 --> 00:06:57,100
Και Πάω να πάει μπροστά
και να παρακολουθήσουν screen-- μου

135
00:06:57,100 --> 00:06:58,460
για μια στιγμή, αν μπορούσε.

136
00:06:58,460 --> 00:07:01,960
Πάω να κάνετε κλικ στο
πράσινη σημαία τώρα,

137
00:07:01,960 --> 00:07:07,850
και μετακόμισε ό, τι φαίνεται να είναι 10 βήματα
ή 10 εικονοστοιχεία, 10 κουκκίδες, στην οθόνη.

138
00:07:07,850 --> 00:07:13,390
>> Και έτσι δεν είναι ότι συναρπαστικό,
αλλά επιτρέψτε μου να προτείνω

139
00:07:13,390 --> 00:07:17,440
χωρίς καν να διδάσκει αυτό, απλά
χρησιμοποιώντας το δικό σας intuition-- let

140
00:07:17,440 --> 00:07:22,560
Θέλω να προτείνω να καταλάβω πώς να
κάνει Scratch με τα πόδια δεξιά από το στάδιο.

141
00:07:22,560 --> 00:07:28,700
Τον έχουν κάνει τον τρόπο για τη δεξιά πλευρά της
η οθόνη, σε όλη τη διαδρομή προς τα δεξιά.

142
00:07:28,700 --> 00:07:32,200
Επιτρέψτε μου να σας δώσω μια στιγμή
ή έτσι για να παλέψει με αυτό.

143
00:07:32,200 --> 00:07:37,681
Μπορεί να θέλετε να ρίξετε μια ματιά
σε άλλες κατηγορίες μπλοκ.

144
00:07:37,681 --> 00:07:38,180
Εντάξει.

145
00:07:38,180 --> 00:07:41,290
Έτσι απλά για να ανακεφαλαιώσουμε, όταν έχουμε
η πράσινη σημαία κλικ εδώ

146
00:07:41,290 --> 00:07:44,850
και να κινηθεί 10 βήματα είναι η
μόνο εντολή, κάθε φορά που

147
00:07:44,850 --> 00:07:46,720
κάντε κλικ στην πράσινη σημαία, τι συμβαίνει;

148
00:07:46,720 --> 00:07:50,070
Λοιπόν, αυτό τρέχει το πρόγραμμά μου.

149
00:07:50,070 --> 00:07:52,450
Έτσι θα μπορούσα να κάνω αυτό
ίσως 10 φορές με το χέρι,

150
00:07:52,450 --> 00:07:55,130
αλλά αυτό αισθάνεται λίγο
bit hackish, να το πω έτσι,

151
00:07:55,130 --> 00:07:57,480
σύμφωνα με την οποία δεν είμαι πραγματικά
επίλυση του προβλήματος.

152
00:07:57,480 --> 00:08:00,530
Είμαι απλώς προσπαθούν ξανά και
ξανά και ξανά και ξανά

153
00:08:00,530 --> 00:08:03,180
μέχρι που το είδος της λάθος
επιτευχθεί η οδηγία

154
00:08:03,180 --> 00:08:05,560
ότι έθεσε ως στόχο να επιτευχθεί νωρίτερα.

155
00:08:05,560 --> 00:08:08,200
>> Αλλά γνωρίζουμε από μας
pseudocode νωρίτερα ότι υπάρχει

156
00:08:08,200 --> 00:08:11,870
η έννοια αυτή στον προγραμματισμό του looping,
κάνει κάτι ξανά και ξανά.

157
00:08:11,870 --> 00:08:14,888
Και έτσι είδα ότι ένα μάτσο σας
επιτευχθεί για κομμάτι ποιο παζλ;

158
00:08:14,888 --> 00:08:17,870

159
00:08:17,870 --> 00:08:18,730
Επαναλάβετε μέχρι.

160
00:08:18,730 --> 00:08:21,400
Έτσι θα μπορούσαμε να κάνουμε κάτι
όπως επαναλάβετε μέχρι.

161
00:08:21,400 --> 00:08:23,760
Και τι έκανες επαναλάβετε μέχρι ακριβώς;

162
00:08:23,760 --> 00:08:27,720

163
00:08:27,720 --> 00:08:28,540
>> ΕΝΤΆΞΕΙ.

164
00:08:28,540 --> 00:08:31,974
Και επιτρέψτε μου να πάει με αυτό που είναι
κάπως πιο απλό για μια στιγμή.

165
00:08:31,974 --> 00:08:33,140
Επιτρέψτε μου να προχωρήσει και να το κάνουμε αυτό.

166
00:08:33,140 --> 00:08:35,559
Παρατηρήστε ότι, όπως μπορεί να έχετε
ανακαλύφθηκε κάτω από τον έλεγχο,

167
00:08:35,559 --> 00:08:38,409
υπάρχει αυτή η επανάληψη μπλοκ, το οποίο
δεν μοιάζει να είναι τόσο μεγάλο.

168
00:08:38,409 --> 00:08:41,039
Δεν υπάρχει πολύ χώρο στο
μεταξύ αυτών των δύο κίτρινες γραμμές.

169
00:08:41,039 --> 00:08:43,539
Αλλά, όπως κάποιοι από εσάς μπορεί να έχετε
παρατηρήσει, αν drag and drop,

170
00:08:43,539 --> 00:08:45,150
Παρατηρήστε πώς μεγαλώνει για να γεμίσει το σχήμα.

171
00:08:45,150 --> 00:08:46,274
>> Και μπορείτε ακόμη και να χώνω περισσότερο.

172
00:08:46,274 --> 00:08:48,670
Είναι απλώς θα συνεχίσει να αυξάνεται, αν
μπορείτε να μεταφέρετε και να αιωρούνται πάνω από αυτό.

173
00:08:48,670 --> 00:08:51,110
Και δεν ξέρω τι είναι
καλύτερα εδώ, οπότε ας

174
00:08:51,110 --> 00:08:54,760
μένα τουλάχιστον επαναλάβει πέντε φορές, για
παράδειγμα, και στη συνέχεια να επιστρέψετε στο στάδιο

175
00:08:54,760 --> 00:08:56,720
και κάντε κλικ στο πράσινο σημαία.

176
00:08:56,720 --> 00:08:59,110
Και τώρα παρατηρήσετε ότι δεν είναι αρκετά εκεί.

177
00:08:59,110 --> 00:09:02,400
>> Τώρα κάποιοι από εσάς που προτείνονται, όπως
Victoria ακριβώς έκανε, επαναλάβετε 10 φορές.

178
00:09:02,400 --> 00:09:05,140
Και αυτό το κάνει σε γενικές γραμμές
να τον πάρει σε όλη τη διαδρομή,

179
00:09:05,140 --> 00:09:10,510
αλλά δεν θα υπάρξει μια πιο ισχυρή
τρόπο από ό, τι αυθαίρετα υπολογίζοντας

180
00:09:10,510 --> 00:09:12,640
πόσες κινήσεις να κάνει;

181
00:09:12,640 --> 00:09:17,680
Τι θα μπορούσε να είναι μια καλύτερη μπλοκ
από επαναλάβετε 10 φορές να είναι;

182
00:09:17,680 --> 00:09:20,380
>> Ναι, οπότε γιατί να μην κάνουμε κάτι για πάντα;

183
00:09:20,380 --> 00:09:24,390
Και τώρα επιτρέψτε μου να μετακινήσετε αυτό το κομμάτι του παζλ
εκεί μέσα και να απαλλαγούμε από αυτό.

184
00:09:24,390 --> 00:09:28,300
Τώρα παρατηρήσετε δεν κατηγορία όπου Scratch
εκκινήσεις, πηγαίνει προς την άκρη.

185
00:09:28,300 --> 00:09:30,700
Και ευτυχώς MIT,
που κάνει Ξυστό, απλά

186
00:09:30,700 --> 00:09:33,190
εξασφαλίζει ότι ποτέ δεν
εξαφανίζεται εντελώς.

187
00:09:33,190 --> 00:09:35,360
Μπορείτε πάντα να αρπάξει την ουρά του.

188
00:09:35,360 --> 00:09:37,680
>> Και μόνο διαισθητικά,
γιατί αυτός να προχωρήσουμε;

189
00:09:37,680 --> 00:09:38,892
Τι συμβαίνει εδώ;

190
00:09:38,892 --> 00:09:41,440

191
00:09:41,440 --> 00:09:43,824
Αυτός φαίνεται να έχουν σταματήσει, αλλά
στη συνέχεια, αν έχω πάρει και σύρετε

192
00:09:43,824 --> 00:09:45,240
κρατά θέλουν να πάνε εκεί.

193
00:09:45,240 --> 00:09:46,123
Γιατί αυτό?

194
00:09:46,123 --> 00:09:51,610

195
00:09:51,610 --> 00:09:54,360
Πραγματικά, ένας υπολογιστής είναι κυριολεκτικά
πρόκειται να κάνει ό, τι μπορείτε να πείτε για να το κάνει.

196
00:09:54,360 --> 00:09:58,380
Έτσι, αν το είπε νωρίτερα να κάνει η
ακόλουθα πράγμα για πάντα, κινούνται 10 βήματα,

197
00:09:58,380 --> 00:10:01,860
πρόκειται να συνεχίσω και να πηγαίνει
μέχρι να χτυπήσει το κόκκινο σήμα στοπ

198
00:10:01,860 --> 00:10:04,620
και να σταματήσει το πρόγραμμα συνολικά.

199
00:10:04,620 --> 00:10:06,610
>> Έτσι, ακόμη και αν δεν το έκανε
να το κάνετε αυτό, πώς θα μπορούσα να

200
00:10:06,610 --> 00:10:09,510
κάνει Scratch κινηθεί γρηγορότερα
σε όλη την οθόνη;

201
00:10:09,510 --> 00:10:12,060

202
00:10:12,060 --> 00:10:13,280
Περισσότερα βήματα, έτσι δεν είναι;

203
00:10:13,280 --> 00:10:15,710
Έτσι, αντί να κάνει 10
σε μια στιγμή, γιατί να μην το κάνουμε εμείς

204
00:10:15,710 --> 00:10:20,100
να προχωρήσει και να αλλάξει το to--
τι θα propose-- 50;

205
00:10:20,100 --> 00:10:24,410
Έτσι τώρα θα πάω να κάνετε κλικ στο πράσινο
σημαία, και μάλιστα, πηγαίνει πολύ γρήγορα.

206
00:10:24,410 --> 00:10:27,180
>> Και αυτό, φυσικά, είναι ακριβώς
μια εκδήλωση του animation.

207
00:10:27,180 --> 00:10:28,060
Τι είναι το animation;

208
00:10:28,060 --> 00:10:33,090
Είναι απλά σας δείχνει τον άνθρωπο ένα
σωρό εικόνες ακόμα πολύ,

209
00:10:33,090 --> 00:10:34,160
πραγματικά, πραγματικά γρήγορα.

210
00:10:34,160 --> 00:10:36,500
Και έτσι, αν είμαστε ακριβώς λέει
αυτόν να κινηθεί περισσότερα βήματα,

211
00:10:36,500 --> 00:10:39,750
είμαστε απλά έχοντας το αποτέλεσμα είναι να
αλλαγής, όπου είναι επί της οθόνης

212
00:10:39,750 --> 00:10:42,900
όλα τα πιο γρήγορα ανά μονάδα χρόνου.

213
00:10:42,900 --> 00:10:46,454
>> Τώρα, η επόμενη πρόκληση που πρότεινα
ήταν να τον αναπήδηση από την άκρη.

214
00:10:46,454 --> 00:10:49,120
Και χωρίς να γνωρίζει ποιο παζλ
κομμάτια exist-- γιατί είναι μια χαρά

215
00:10:49,120 --> 00:10:53,030
αν δεν έχετε να το
στάδιο της challenge-- τι

216
00:10:53,030 --> 00:10:54,280
θέλετε να κάνετε διαισθητικά;

217
00:10:54,280 --> 00:10:58,030
Πώς θα έχουμε τον αναπηδήσει πίσω και
εμπρός, ανάμεσα στο αριστερό και το δεξί;

218
00:10:58,030 --> 00:11:02,630

219
00:11:02,630 --> 00:11:03,810
>> Ναι.

220
00:11:03,810 --> 00:11:05,680
Έτσι, χρειαζόμαστε κάποιου είδους
της κατάστασης, και

221
00:11:05,680 --> 00:11:09,710
φαίνεται να έχουν υποθετικοί, έτσι ώστε να
μιλούν, κάτω από την κατηγορία ελέγχου.

222
00:11:09,710 --> 00:11:14,110
Ποια από αυτά τα τμήματα
εμείς μάλλον θα θέλετε;

223
00:11:14,110 --> 00:11:15,200
Ναι, ίσως "αν, τότε."

224
00:11:15,200 --> 00:11:18,780
Έτσι, παρατηρούμε ότι ανάμεσα στα κίτρινα τετράγωνα
έχουμε εδώ, υπάρχει αυτό το "αν"

225
00:11:18,780 --> 00:11:23,920
ή αυτό το «εάν, αλλιώς" μπλοκ που θα
μας επιτρέπουν να λάβει μια απόφαση για να γίνει αυτό

226
00:11:23,920 --> 00:11:25,000
ή να το κάνουμε αυτό.

227
00:11:25,000 --> 00:11:27,380
Και μπορείτε ακόμη και να τους φωλιά
να κάνει πολλαπλές πράγματα.

228
00:11:27,380 --> 00:11:34,910
Ή αν δεν έχετε πάει εδώ ακόμα,
προχωρήστε στην κατηγορία Sensing

229
00:11:34,910 --> 00:11:39,612
and-- ας δούμε αν είναι εδώ.

230
00:11:39,612 --> 00:11:43,050

231
00:11:43,050 --> 00:11:52,050
>> Λοιπόν, τι μπλοκ μπορεί να είναι χρήσιμη εδώ
να ανιχνεύσει αν είναι από τη σκηνή;

232
00:11:52,050 --> 00:11:56,740
Ναι, παρατηρήσετε ότι μερικά από αυτά τα μπλοκ
μπορεί να παραμετροποιημένη, να το πω έτσι.

233
00:11:56,740 --> 00:12:00,706
Μπορούν να είδος προσαρμοστεί, δεν
σε αντίθεση με HTML χθες με χαρακτηριστικά,

234
00:12:00,706 --> 00:12:03,330
όπου αυτά τα χαρακτηριστικά του είδους
προσαρμόσετε τη συμπεριφορά μιας ετικέτας.

235
00:12:03,330 --> 00:12:08,880
Ομοίως εδώ, μπορώ να αρπάξει αυτό το συγκινητικό
μπλοκ και την αλλαγή και να θέσουμε το ερώτημα,

236
00:12:08,880 --> 00:12:11,500
Σας αγγίζουν το ποντίκι
δείκτη, όπως το δρομέα

237
00:12:11,500 --> 00:12:13,250
ή μπορείτε να αγγίξετε την άκρη;

238
00:12:13,250 --> 00:12:15,210
>> Έτσι, επιτρέψτε μου να πάω και να το κάνουμε αυτό.

239
00:12:15,210 --> 00:12:18,130
Πάω για σμίκρυνση για μια στιγμή.

240
00:12:18,130 --> 00:12:21,320
Επιτρέψτε μου να αρπάξει αυτό το κομμάτι του παζλ
Εδώ, αυτό το παζλ κομμάτι αυτό,

241
00:12:21,320 --> 00:12:24,570
και Πάω να συνονθύλευμα
τους επάνω για μια στιγμή.

242
00:12:24,570 --> 00:12:27,620
Πάω να μετακινήσετε αυτό,
αλλάξετε αυτό σε συγκινητικό άκρη,

243
00:12:27,620 --> 00:12:38,590
και θα πάω στην κίνηση το κάνουμε αυτό.

244
00:12:38,590 --> 00:12:40,490
Έτσι, εδώ είναι μερικά συστατικά.

245
00:12:40,490 --> 00:12:42,570
Νομίζω ότι έχω όλα όσα θέλω.

246
00:12:42,570 --> 00:12:47,710
>> Κάποιος θα ήθελα να προτείνω το πώς θα
μπορούν να συνδεθούν αυτά ίσως πάνω προς τα κάτω

247
00:12:47,710 --> 00:12:52,020
προκειμένου να επιλυθεί το πρόβλημα της
Scratch κίνηση δεξιά προς τα αριστερά προς τα δεξιά για να

248
00:12:52,020 --> 00:12:57,020
αριστερά προς τα δεξιά προς τα αριστερά, το καθένα
χρόνο ακριβώς αναπηδούν από τον τοίχο;

249
00:12:57,020 --> 00:12:58,050
Τι θέλω να κάνω;

250
00:12:58,050 --> 00:13:01,097
Ποια μπλοκ θα πρέπει να συνδεθεί με το
"Όταν πράσινη σημαία κλικ πρώτα";

251
00:13:01,097 --> 00:13:04,060

252
00:13:04,060 --> 00:13:06,200
>> ΟΚ, οπότε ας αρχίσουμε με το "για πάντα".

253
00:13:06,200 --> 00:13:07,170
Τι συμβαίνει στο εσωτερικό το επόμενο βήμα;

254
00:13:07,170 --> 00:13:10,290
Κάποιος άλλος.

255
00:13:10,290 --> 00:13:11,850
ΟΚ, μετακινηθείτε βήματα.

256
00:13:11,850 --> 00:13:12,350
Εντάξει.

257
00:13:12,350 --> 00:13:14,470
Τότε τι?

258
00:13:14,470 --> 00:13:15,120
Έτσι, τότε η περίπτωση.

259
00:13:15,120 --> 00:13:17,720
Και παρατηρήσετε, ακόμα κι αν φαίνεται
στριμώχνεται μαζί σφιχτά,

260
00:13:17,720 --> 00:13:19,500
θα αυξηθεί απλά για να γεμίσει.

261
00:13:19,500 --> 00:13:21,500
Θα πηδήσει ακριβώς εκεί που θέλω.

262
00:13:21,500 --> 00:13:25,920
>> Και τι μπορώ να τοποθετήσω μεταξύ
το εάν και τότε;

263
00:13:25,920 --> 00:13:27,180
Πιθανώς "αν αγγίξετε άκρη."

264
00:13:27,180 --> 00:13:31,800
Και ειδοποίηση, και πάλι, αυτό είναι πάρα πολύ μεγάλο
για αυτό, αλλά θα αυξηθεί για να γεμίσει.

265
00:13:31,800 --> 00:13:35,002
Και στη συνέχεια ενεργοποιήστε 15 μοίρες;

266
00:13:35,002 --> 00:13:35,710
Πόσοι βαθμοί?

267
00:13:35,710 --> 00:13:38,800

268
00:13:38,800 --> 00:13:41,196
Ναι, έτσι 180 θα περιστρέψει
Θέλω όλος ο τρόπος γύρω.

269
00:13:41,196 --> 00:13:42,570
Έτσι, ας δούμε αν έχω αυτό το δικαίωμα.

270
00:13:42,570 --> 00:13:43,930
Επιτρέψτε μου σμίκρυνση.

271
00:13:43,930 --> 00:13:45,130
>> Επιτρέψτε μου να σύρετε Scratch επάνω.

272
00:13:45,130 --> 00:13:50,030
Έτσι, αυτός είναι λίγο διαστρεβλωμένη
τώρα, αλλά αυτό είναι εντάξει.

273
00:13:50,030 --> 00:13:52,231
Πώς μπορώ να τον επαναφέρετε εύκολα;

274
00:13:52,231 --> 00:13:59,879

275
00:13:59,879 --> 00:14:01,045
Πάω να εξαπατήσει λίγο.

276
00:14:01,045 --> 00:14:04,074

277
00:14:04,074 --> 00:14:05,990
Έτσι είμαι προσθέτοντας άλλο
μπλοκ, ακριβώς για να είναι σαφής.

278
00:14:05,990 --> 00:14:08,424
Θέλω να επισημάνω 90 μοίρες
προς τα δεξιά, από προεπιλογή,

279
00:14:08,424 --> 00:14:10,840
έτσι είμαι απλώς πρόκειται να του πω
να το κάνουμε αυτό μέσω προγραμματισμού.

280
00:14:10,840 --> 00:14:11,632
Και πάμε.

281
00:14:11,632 --> 00:14:14,740

282
00:14:14,740 --> 00:14:15,740
Εμείς φαίνεται να το έχουν κάνει.

283
00:14:15,740 --> 00:14:19,980
Είναι λίγο περίεργο, γιατί
αυτός είναι το περπάτημα ανάποδα.

284
00:14:19,980 --> 00:14:21,250
Ας το ονομάσουμε ότι ένα bug.

285
00:14:21,250 --> 00:14:22,120
Αυτό είναι ένα λάθος.

286
00:14:22,120 --> 00:14:27,320
Ένα bug είναι ένα λάθος σε ένα πρόγραμμα, ένα
λογικό λάθος που εγώ, ο άνθρωπος, έκανε.

287
00:14:27,320 --> 00:14:28,985
Γιατί είναι αυτός που θα ανάποδα;

288
00:14:28,985 --> 00:14:33,560

289
00:14:33,560 --> 00:14:35,250
Μήπως MIT βίδα πάνω ή προς τα έκανα;

290
00:14:35,250 --> 00:14:38,840

291
00:14:38,840 --> 00:14:42,550
>> Ναι, θέλω να πω, δεν είναι του MIT
σφάλμα. Μου έδωσαν ένα κομμάτι του παζλ

292
00:14:42,550 --> 00:14:44,970
που λέει μετατρέψει κάποιο αριθμό των βαθμών.

293
00:14:44,970 --> 00:14:47,672
Και μετά από πρόταση της Βικτώριας,
Είμαι στροφή 180 μοιρών,

294
00:14:47,672 --> 00:14:48,880
η οποία είναι η σωστή διαίσθηση.

295
00:14:48,880 --> 00:14:53,700
Αλλά η στροφή 180 μοιρών στην κυριολεξία
σημαίνει στροφή 180 μοιρών,

296
00:14:53,700 --> 00:14:55,860
και αυτό δεν είναι πραγματικά
ό, τι θέλω, προφανώς.

297
00:14:55,860 --> 00:14:58,026
Επειδή τουλάχιστον αυτός είναι σε
Αυτό δισδιάστατο κόσμο,

298
00:14:58,026 --> 00:15:00,740
έτσι καμπής πραγματικά συμβαίνει
να τον αναστρέψετε ανάποδα.

299
00:15:00,740 --> 00:15:04,030
>> Μάλλον θέλετε να χρησιμοποιήσετε ό, τι μπλοκ
Αντ 'αυτού, με βάση αυτά που βλέπετε εδώ;

300
00:15:04,030 --> 00:15:11,890

301
00:15:11,890 --> 00:15:14,790
Πώς μπορούμε να το διορθώσω αυτό;

302
00:15:14,790 --> 00:15:18,380
Ναι, έτσι θα μπορούσαμε να επισημάνω
προς την αντίθετη κατεύθυνση.

303
00:15:18,380 --> 00:15:22,300
Και στην πραγματικότητα, ακόμη και αυτό είναι
δεν πρόκειται να είναι αρκετή,

304
00:15:22,300 --> 00:15:26,410
γιατί μπορούμε μόνο σκληρή κώδικα
να δείχνει προς τα αριστερά ή προς τα δεξιά.

305
00:15:26,410 --> 00:15:27,920
>> Ξέρεις τι θα μπορούσαμε να κάνουμε;

306
00:15:27,920 --> 00:15:30,160
Φαίνεται σαν να έχουμε ένα
μπλοκ ευκολία εδώ.

307
00:15:30,160 --> 00:15:32,987
Αν μου μεγέθυνση, δείτε
κάτι που μας αρέσει εδώ;

308
00:15:32,987 --> 00:15:36,120

309
00:15:36,120 --> 00:15:40,020
Ώστε να μοιάζει με το MIT έχει μια
αφαίρεση χτίστηκε εδώ.

310
00:15:40,020 --> 00:15:45,440
Αυτό το μπλοκ φαίνεται να είναι ισοδύναμες
στην οποία άλλα μπλοκ, πληθυντικό;

311
00:15:45,440 --> 00:15:49,510
>> Αυτό και μόνο το μπλοκ φαίνεται να είναι ισοδύναμες
σε όλο αυτό το τρίο των μπλοκ

312
00:15:49,510 --> 00:15:50,880
ότι έχουμε εδώ.

313
00:15:50,880 --> 00:15:54,670
Έτσι αποδεικνύεται μπορώ να απλοποιήσει μου
πρόγραμμα με το να απαλλαγούμε από όλα αυτά

314
00:15:54,670 --> 00:15:58,270
και απλά βάλτε αυτό εδώ.

315
00:15:58,270 --> 00:16:01,620
Και τώρα είναι ακόμα λίγο
λάθη, και αυτό είναι μια χαρά για τώρα.

316
00:16:01,620 --> 00:16:03,370
Θα το αφήσουμε να είναι.

317
00:16:03,370 --> 00:16:06,000
Αλλά το πρόγραμμά μου είναι ακόμα
απλούστερη, και αυτό, επίσης,

318
00:16:06,000 --> 00:16:09,060
θα είναι αντιπροσωπευτικό
από ένα γκολ σε programming--

319
00:16:09,060 --> 00:16:13,430
είναι να κάνει ιδανικά κωδικό σας
απλή, συμπαγής όσο είναι δυνατόν,

320
00:16:13,430 --> 00:16:15,650
ενώ εξακολουθούν να είναι όσο
αναγνώσιμη δυνατό.

321
00:16:15,650 --> 00:16:20,310
Δεν θέλετε να το κάνετε τόσο συνοπτική
ότι είναι δύσκολο να κατανοηθεί.

322
00:16:20,310 --> 00:16:22,826
>> Αλλά παρατηρήσετε έχω αντικαθίστανται
τρία τετράγωνα με ένα,

323
00:16:22,826 --> 00:16:24,200
και αυτό είναι αναμφισβήτητα ένα καλό πράγμα.

324
00:16:24,200 --> 00:16:27,280
Έχω αντλείται μακριά την έννοια
να ελέγχεται εάν είστε

325
00:16:27,280 --> 00:16:29,120
στην άκρη με μόλις ένα τετράγωνο.

326
00:16:29,120 --> 00:16:31,520
Τώρα μπορούμε να διασκεδάσουν με αυτό, στην πραγματικότητα.

327
00:16:31,520 --> 00:16:35,790
Αυτό δεν προσθέτουν τόσο πολύ
πνευματική αξία, αλλά παιχνιδιάρικο αξία.

328
00:16:35,790 --> 00:16:39,730
Πάω να πάει μπροστά
και πιάσε αυτόν τον ήχο εδώ.

329
00:16:39,730 --> 00:16:42,900

330
00:16:42,900 --> 00:16:46,420
Έτσι, επιτρέψτε μου να πάει μπροστά, και επιτρέψτε μου να
να σταματήσει το πρόγραμμα για μια στιγμή.

331
00:16:46,420 --> 00:16:52,070
Πάω να καταγράψει τα ακόλουθα,
επιτρέποντας την πρόσβαση στο μικρόφωνό μου.

332
00:16:52,070 --> 00:16:53,181
>> Ορίστε.

333
00:16:53,181 --> 00:16:53,680
Ωχ.

334
00:16:53,680 --> 00:16:58,710

335
00:16:58,710 --> 00:17:01,140
Ας δοκιμάσουμε αυτό και πάλι.

336
00:17:01,140 --> 00:17:02,279
Ορίστε.

337
00:17:02,279 --> 00:17:03,570
Εντάξει, καταγράφεται το λάθος πράγμα.

338
00:17:03,570 --> 00:17:04,580
Ορίστε.

339
00:17:04,580 --> 00:17:05,080
Ωχ.

340
00:17:05,080 --> 00:17:07,910

341
00:17:07,910 --> 00:17:08,800
Ωχ.

342
00:17:08,800 --> 00:17:09,300
Εντάξει.

343
00:17:09,300 --> 00:17:10,791
Τώρα πρέπει να απαλλαγούμε από αυτό.

344
00:17:10,791 --> 00:17:11,290
Εντάξει.

345
00:17:11,290 --> 00:17:13,950
>> Έτσι, τώρα έχω ένα
καταγραφή απλά "ωχ".

346
00:17:13,950 --> 00:17:18,040
Έτσι τώρα είμαι πρόκειται να πάει
μπροστά και να καλέσει αυτό το «ωχ».

347
00:17:18,040 --> 00:17:20,270
Πάω να πάει πίσω
σε σενάρια μου, και τώρα

348
00:17:20,270 --> 00:17:25,460
προειδοποίηση υπάρχει αυτό το μπλοκ που ονομάζεται
αναπαραγωγή ήχου "νιαούρισμα" ή αναπαραγωγή ήχου "ωχ".

349
00:17:25,460 --> 00:17:28,920
Πάω να σύρετε αυτό, και όπου
πρέπει να βάλω αυτό για κωμικό αποτέλεσμα;

350
00:17:28,920 --> 00:17:31,740

351
00:17:31,740 --> 00:17:37,860
Ναι, έτσι τώρα είναι το είδος της
λάθη, γιατί τώρα αυτό block--

352
00:17:37,860 --> 00:17:42,050
παρατηρήστε πώς αυτό το «αν στην άκρη,
αναπήδηση "είναι το είδος της αυτόνομα.

353
00:17:42,050 --> 00:17:43,704
Γι 'αυτό και πρέπει να το διορθώσω αυτό.

354
00:17:43,704 --> 00:17:44,870
Επιτρέψτε μου να προχωρήσει και να το κάνουμε αυτό.

355
00:17:44,870 --> 00:17:48,630
Επιτρέψτε μου να απαλλαγούμε από αυτό και να πάει πίσω
στο αρχικό μας, πιο σκόπιμη

356
00:17:48,630 --> 00:17:49,870
λειτουργικότητα.

357
00:17:49,870 --> 00:18:01,080
Έτσι, "αν αγγίξετε άκρη, τότε« Θέλω
να μετατρέψει, όπως προτείνεται Victoria,

358
00:18:01,080 --> 00:18:02,480
180 μοίρες.

359
00:18:02,480 --> 00:18:05,497
Και θέλω να παίξετε
ο ήχος "ωχ" εκεί;

360
00:18:05,497 --> 00:18:11,800

361
00:18:11,800 --> 00:18:15,580
>> Ναι, παρατηρήσετε ότι είναι έξω
ότι κίτρινο μπλοκ.

362
00:18:15,580 --> 00:18:17,680
Έτσι, αυτό, επίσης, θα είναι ένα
bug, αλλά το έχω παρατηρήσει.

363
00:18:17,680 --> 00:18:21,290
Έτσι, Πάω να το σύρετε μέχρι εδώ,
και προειδοποίηση τώρα είναι μέσα στο «αν».

364
00:18:21,290 --> 00:18:24,250
Έτσι, το "αν" είναι αυτό το είδος
σαν βραχίονας μοιάζει κηλίδα

365
00:18:24,250 --> 00:18:26,260
ότι πρόκειται μόνο για
κάνει ό, τι είναι μέσα από αυτό.

366
00:18:26,260 --> 00:18:30,216
Έτσι τώρα, αν έχω σμίκρυνση σε
ο κίνδυνος annoying--

367
00:18:30,216 --> 00:18:32,860

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Ωχ, ωχ, ωχ.

369
00:18:36,470 --> 00:18:39,910
>> DAVID Malan: Και
θα πήγαινε για πάντα.

370
00:18:39,910 --> 00:18:44,160
Τώρα απλά να επιταχύνει τα πράγματα
Εδώ, επιτρέψτε μου να πάει μπροστά και να ανοίξει,

371
00:18:44,160 --> 00:18:50,460
ας say-- επιτρέψτε μου να πάω σε κάποια
της δικής μου πράγματα από την τάξη.

372
00:18:50,460 --> 00:18:53,000

373
00:18:53,000 --> 00:19:00,220
Και επιτρέψτε μου να ανοίξει, ας πούμε, αυτό το
ένα που γίνεται από έναν από τη διδασκαλία τους συνανθρώπους μας

374
00:19:00,220 --> 00:19:01,500
λίγα χρόνια πριν.

375
00:19:01,500 --> 00:19:04,732
Έτσι, κάποιοι από εσάς μπορεί να υπενθυμίσει
αυτό το παιχνίδι από το χτες,

376
00:19:04,732 --> 00:19:05,940
και είναι πραγματικά αξιοσημείωτη.

377
00:19:05,940 --> 00:19:08,190
Ακόμα κι αν έχουμε κάνει το
απλούστερη των προγραμμάτων τώρα,

378
00:19:08,190 --> 00:19:09,980
ας εξετάσουμε τι αυτό
πραγματικά μοιάζει.

379
00:19:09,980 --> 00:19:10,650
Επιτρέψτε μου να χτυπήσει το παιχνίδι.

380
00:19:10,650 --> 00:19:14,210

381
00:19:14,210 --> 00:19:18,980
>> Έτσι, σε αυτό το παιχνίδι, έχουμε ένα
βάτραχος, και χρησιμοποιώντας το βέλος keys--

382
00:19:18,980 --> 00:19:23,340
παίρνει μεγαλύτερα βήματα από ό, τι remember--
Έχω τον έλεγχο αυτού του βατράχου.

383
00:19:23,340 --> 00:19:29,630
Και ο στόχος είναι να μεταδώσουμε την πολυάσχολη
δρόμο χωρίς να τρέχει στα αυτοκίνητα.

384
00:19:29,630 --> 00:19:34,735
Και ας see-- αν πάω μέχρι εδώ,
πρέπει να περιμένετε για ένα ημερολόγιο για να μετακινηθείτε από.

385
00:19:34,735 --> 00:19:38,130

386
00:19:38,130 --> 00:19:39,274
Αυτό αισθάνεται σαν ένα bug.

387
00:19:39,274 --> 00:19:42,240

388
00:19:42,240 --> 00:19:43,495
Αυτό είναι το είδος του σφάλματος.

389
00:19:43,495 --> 00:19:45,980

390
00:19:45,980 --> 00:19:46,480
Εντάξει.

391
00:19:46,480 --> 00:19:51,550
Είμαι σε αυτό εδώ,
εκεί, και στη συνέχεια να σας κρατήσει

392
00:19:51,550 --> 00:19:54,100
πρόκειται μέχρι να πάρετε όλα
οι βάτραχοι στα μαξιλάρια κρίνων.

393
00:19:54,100 --> 00:19:55,920
Τώρα αυτό μπορεί να μοιάζει
όλο και πιο πολύπλοκες,

394
00:19:55,920 --> 00:19:57,840
αλλά ας προσπαθήσουμε να σπάσει
αυτό κάτω διανοητικά

395
00:19:57,840 --> 00:20:00,040
και προφορικά σε όγκους που το απαρτίζουν.

396
00:20:00,040 --> 00:20:03,910
Έτσι, υπάρχει πιθανώς ένα παζλ
κομμάτι που δεν έχουμε δει ακόμα

397
00:20:03,910 --> 00:20:07,440
αλλά αυτό είναι απάντηση σε πληκτρολογήσεις,
για πράγματα που χτύπησε στο πληκτρολόγιο.

398
00:20:07,440 --> 00:20:11,660
>> Έτσι, υπάρχει πιθανώς κάποιο είδος
μπλοκ που λέει, όταν οι βασικές ισούται επάνω,

399
00:20:11,660 --> 00:20:15,965
στη συνέχεια να κάνουμε κάτι με Scratch--
ίσως κινηθεί 10 βήματα με αυτόν τον τρόπο.

400
00:20:15,965 --> 00:20:20,240
Αν κάτω πλήκτρο, μετακινήστε 10 βήματα
Με αυτό τον τρόπο, ή αριστερό πλήκτρο, μετακινήστε 10 βήματα

401
00:20:20,240 --> 00:20:21,710
Με αυτό τον τρόπο, 10 βήματα που.

402
00:20:21,710 --> 00:20:23,644
Έχω μετατραπεί σαφώς τη γάτα σε ένα βάτραχο.

403
00:20:23,644 --> 00:20:26,060
Έτσι, αυτό είναι ακριβώς όπου η
φορεσιά, όπως κλήσεις Scratch it-- μας

404
00:20:26,060 --> 00:20:28,440
μόλις εισαχθεί μια εικόνα του βατράχου.

405
00:20:28,440 --> 00:20:29,570
>> Αλλά τι άλλο συμβαίνει;

406
00:20:29,570 --> 00:20:32,794
Ποιες άλλες γραμμές κώδικα,
τι άλλα κομμάτια του παζλ

407
00:20:32,794 --> 00:20:35,460
έκανε Blake, τη διδασκαλία τους συναδέλφους μας,
χρησιμοποιήσει σε αυτό το πρόγραμμα, προφανώς;

408
00:20:35,460 --> 00:20:38,320

409
00:20:38,320 --> 00:20:42,730
Τι κάνει τα πάντα move--
τι προγραμματισμού κατασκευάσει;

410
00:20:42,730 --> 00:20:44,950
>> Κίνηση, σίγουρος, έτσι ώστε η
μετακινήσετε μπλοκ, αυτό είναι σίγουρο.

411
00:20:44,950 --> 00:20:49,330
Και τι είναι αυτό μπλοκ κίνηση
εσωτερικό του, πιθανότατα;

412
00:20:49,330 --> 00:20:52,850
Ναι, ένα είδος βρόχου, ίσως ένα
πάντα μπλοκ, ίσως μια επανάληψη block--

413
00:20:52,850 --> 00:20:54,070
επαναλάβετε μέχρι μπλοκ.

414
00:20:54,070 --> 00:20:57,330
Και αυτό είναι που κάνει τα αρχεία καταγραφής και
τα μαξιλάρια κρίνων και όλα τα άλλα κίνηση

415
00:20:57,330 --> 00:20:57,990
εμπρός και πίσω.

416
00:20:57,990 --> 00:21:00,270
Είναι ακριβώς συμβαίνει ασταμάτητα.

417
00:21:00,270 --> 00:21:03,180
>> Γιατί είναι μερικά από τα αυτοκίνητα
κινείται γρηγορότερα από τους άλλους;

418
00:21:03,180 --> 00:21:06,607
Τι είναι διαφορετικό για αυτά τα προγράμματα;

419
00:21:06,607 --> 00:21:09,690
Ναι, ίσως κάποιοι από αυτούς λαμβάνουν
περισσότερα βήματα ταυτόχρονα και κάποια από αυτά

420
00:21:09,690 --> 00:21:10,690
λιγότερα βήματα με τη μία.

421
00:21:10,690 --> 00:21:14,670
Και το οπτικό αποτέλεσμα
είναι γρήγορη σε σχέση με αργή.

422
00:21:14,670 --> 00:21:16,030
>> Τι νομίζεις ότι συνέβη;

423
00:21:16,030 --> 00:21:19,700
Όταν πήρα το βάτραχο μου σε όλη τη διαδρομή
απέναντι από το δρόμο και το ποτάμι

424
00:21:19,700 --> 00:21:23,560
πάνω στο μαξιλάρι κρίνων, κάτι
αξιοσημείωτο συνέβη.

425
00:21:23,560 --> 00:21:26,540
Τι συνέβη μόλις το έκανα αυτό;

426
00:21:26,540 --> 00:21:27,210
Σταμάτησε.

427
00:21:27,210 --> 00:21:29,680
Αυτό βάτραχος σταμάτησε, και
Πήρα μια δεύτερη βάτραχο.

428
00:21:29,680 --> 00:21:33,155
Λοιπόν, τι κατασκευή θα πρέπει να είναι
που χρησιμοποιούνται εκεί, ποια η λειτουργία;

429
00:21:33,155 --> 00:21:36,020

430
00:21:36,020 --> 00:21:38,660
>> Ναι, έτσι υπάρχει κάποιο είδος
"Αν" ρυθμίσει εκεί, πάρα πολύ.

431
00:21:38,660 --> 00:21:41,909
Και αποδεικνύεται out-- δεν είδαμε this--
αλλά υπάρχουν και άλλα τμήματα εκεί που

432
00:21:41,909 --> 00:21:45,300
μπορώ να πω, αν είστε συγκινητικό
Ένα άλλο πράγμα που εμφανίζονται στην οθόνη,

433
00:21:45,300 --> 00:21:47,720
αν είστε σε επαφή με το μαξιλάρι κρίνων, "τότε".

434
00:21:47,720 --> 00:21:50,810
Και, στη συνέχεια, ότι όταν εμείς
να εμφανιστεί η δεύτερη βάτραχος.

435
00:21:50,810 --> 00:21:54,969
Έτσι, ακόμη κι αν αυτό το παιχνίδι είναι σίγουρα
πολύ με ημερομηνία, παρόλο που με την πρώτη ματιά

436
00:21:54,969 --> 00:21:58,010
υπάρχει τόσο πολύ να πάει on-- και Μπλέικ
δεν μαστίγιο αυτό επάνω σε δύο λεπτά,

437
00:21:58,010 --> 00:22:00,390
κατά πάσα πιθανότητα πήρε τον αρκετών
ώρες για να δημιουργηθεί αυτό το παιχνίδι

438
00:22:00,390 --> 00:22:03,850
βασίζονται σε μνήμη ή βίντεο του
της έκδοσης χτες για αυτό.

439
00:22:03,850 --> 00:22:07,940
Αλλά όλα αυτά τα μικρά πράγματα
συμβαίνει στην οθόνη σε απομόνωση

440
00:22:07,940 --> 00:22:11,550
συνοψίζεται σε αυτές τις πολύ απλές
constructs-- κινήσεις ή δηλώσεις

441
00:22:11,550 --> 00:22:15,519
όπως έχουμε συζητήσει, βρόχους και
συνθήκες, και ότι είναι γι 'αυτό.

442
00:22:15,519 --> 00:22:17,060
Υπάρχουν μερικά άλλα φανταχτερά χαρακτηριστικά.

443
00:22:17,060 --> 00:22:19,130
Μερικά από αυτά είναι καθαρά
αισθητική ή ακουστική,

444
00:22:19,130 --> 00:22:20,964
όπως τους ήχους που μόλις έπαιξε με.

445
00:22:20,964 --> 00:22:23,380
Αλλά για το μεγαλύτερο μέρος, θα
έχουν σε αυτή τη γλώσσα, Ξυστό,

446
00:22:23,380 --> 00:22:25,350
το σύνολο της θεμελιώδους
δομικά στοιχεία που θα

447
00:22:25,350 --> 00:22:29,280
έχουν σε C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
και οποιοδήποτε αριθμό άλλων γλωσσών.

449
00:22:32,960 --> 00:22:36,720
Οποιεσδήποτε ερωτήσεις σχετικά με το μηδέν;

450
00:22:36,720 --> 00:22:37,220
Εντάξει.

451
00:22:37,220 --> 00:22:40,303
Γι 'αυτό και δεν θα βουτήξει σε βαθύτερα στο Scratch,
αν είστε ευπρόσδεκτοι αυτό το Σαββατοκύριακο,

452
00:22:40,303 --> 00:22:42,860
ειδικά αν έχετε παιδιά ή
ανίψια και τέτοια,

453
00:22:42,860 --> 00:22:44,220
για την εισαγωγή τους στο Scratch.

454
00:22:44,220 --> 00:22:47,960
Είναι πραγματικά μια θαυμάσια παιχνιδιάρικο
περιβάλλον με, ως συντάκτες του λένε,

455
00:22:47,960 --> 00:22:49,120
πολύ ψηλά ταβάνια.

456
00:22:49,120 --> 00:22:51,670
Ακόμα κι αν ξεκινήσαμε με
πολύ χαμηλού επιπέδου λεπτομέρειες,

457
00:22:51,670 --> 00:22:54,890
μπορείτε να το κάνετε πραγματικά αρκετά ένα κομμάτι
με αυτό, και αυτό είναι ίσως

458
00:22:54,890 --> 00:22:57,360
μια επίδειξη ακριβώς αυτό.

459
00:22:57,360 --> 00:23:02,920
>> Αλλά ας τώρα τη μετάβαση σε κάποιο πιο
εξελιγμένα προβλήματα, αν θέλετε,

460
00:23:02,920 --> 00:23:05,870
γνωστή ως "αναζήτηση" και
«Διαλογή» γενικότερα.

461
00:23:05,870 --> 00:23:09,500
Είχαμε αυτό το τηλέφωνο βιβλίο earlier-- εδώ
ένα άλλο μόνο για discussion--

462
00:23:09,500 --> 00:23:13,460
ότι ήμασταν σε θέση να αναζητήσετε
πιο αποτελεσματικά, διότι

463
00:23:13,460 --> 00:23:15,270
ενός σημαντικού υπόθεση.

464
00:23:15,270 --> 00:23:17,655
Και ακριβώς για να είναι σαφές, τι
παραδοχή ήμουν καθιστώντας

465
00:23:17,655 --> 00:23:19,280
κατά την αναζήτηση μέσω αυτού του τηλεφώνου βιβλίο;

466
00:23:19,280 --> 00:23:23,342

467
00:23:23,342 --> 00:23:25,300
Ότι ο Mike Smith ήταν σε
ο τηλεφωνικός κατάλογος, αν και

468
00:23:25,300 --> 00:23:27,410
θα είναι σε θέση να χειριστεί
το σενάριο χωρίς αυτόν

469
00:23:27,410 --> 00:23:30,720
εκεί εάν σταμάτησα ακριβώς πρόωρα.

470
00:23:30,720 --> 00:23:31,806
Το βιβλίο είναι αλφαβητική.

471
00:23:31,806 --> 00:23:33,930
Και αυτό είναι ένα πολύ γενναιόδωρο
υπόθεση, γιατί αυτό

472
00:23:33,930 --> 00:23:36,580
σημαίνει someone-- είμαι το είδος
κοπής σε μια γωνία,

473
00:23:36,580 --> 00:23:40,580
σαν να είμαι πιο γρήγορα, επειδή κάποιος
άλλος έκανε πολλή και σκληρή δουλειά για μένα.

474
00:23:40,580 --> 00:23:43,120
>> Τι γίνεται όμως όταν το τηλέφωνο
το βιβλίο ήταν άνευ διαλογής;

475
00:23:43,120 --> 00:23:47,050
Ίσως Verizon πήρε τεμπέλης, απλά έριξε
ονόματα και οι αριθμοί του καθενός εκεί

476
00:23:47,050 --> 00:23:50,120
ίσως με τη σειρά με την οποία
εγγραφεί για την τηλεφωνική υπηρεσία.

477
00:23:50,120 --> 00:23:54,570
Και πόσο χρόνο χρειάζεται για να με πάρει
να βρείτε κάποιον σαν τον Mike Smith;

478
00:23:54,570 --> 00:23:58,160
1.000 τηλέφωνό σελίδα book-- πόσα
σελίδες έχω να δούμε μέσα;

479
00:23:58,160 --> 00:23:58,905
>> Ολα τους.

480
00:23:58,905 --> 00:24:00,030
Είσαι το είδος του από την τύχη.

481
00:24:00,030 --> 00:24:03,420
Μπορείτε κυριολεκτικά πρέπει να εξετάσουμε κάθε
σελίδα, αν ο τηλεφωνικός κατάλογος είναι απλά

482
00:24:03,420 --> 00:24:04,450
τυχαία διαλογή.

483
00:24:04,450 --> 00:24:06,910
Μπορείτε να πάρετε τυχεροί και να βρείτε Mike
από την πρώτη κιόλας σελίδα, γιατί

484
00:24:06,910 --> 00:24:08,826
ήταν ο πρώτος πελάτης
να διατάξει την τηλεφωνική υπηρεσία.

485
00:24:08,826 --> 00:24:10,760
Αλλά θα μπορούσε να ήταν η τελευταία, πάρα πολύ.

486
00:24:10,760 --> 00:24:12,500
>> Έτσι τυχαία σειρά δεν είναι καλή.

487
00:24:12,500 --> 00:24:16,750
Έτσι, ας υποθέσουμε ότι έχουμε να λύσουμε το
τηλεφωνικό κατάλογο ή σε γενικά δεδομένα ταξινόμησης

488
00:24:16,750 --> 00:24:18,520
ότι έχουμε ήδη δοθεί.

489
00:24:18,520 --> 00:24:19,440
Πώς μπορούμε να το κάνουμε αυτό;

490
00:24:19,440 --> 00:24:21,360
>> Λοιπόν, επιτρέψτε μου να δοκιμάσετε
ένα απλό παράδειγμα εδώ.

491
00:24:21,360 --> 00:24:24,290
Επιτρέψτε μου να προχωρήσει και να πετάξει ένα
μερικούς αριθμούς στον πίνακα.

492
00:24:24,290 --> 00:24:35,480
Ας υποθέσουμε ότι οι αριθμοί που έχουμε είναι,
ας πούμε, τέσσερις, δύο, ένα, και τα τρία.

493
00:24:35,480 --> 00:24:38,390
Και, Ben, ταξινομήσετε αυτούς τους αριθμούς για εμάς.

494
00:24:38,390 --> 00:24:39,017
>> Εντάξει, καλά.

495
00:24:39,017 --> 00:24:39,850
Πώς το έκανες αυτό?

496
00:24:39,850 --> 00:24:42,731

497
00:24:42,731 --> 00:24:43,230
Εντάξει.

498
00:24:43,230 --> 00:24:44,710
Έτσι, ξεκινούν με το μικρότερο
αξία και η υψηλότερη,

499
00:24:44,710 --> 00:24:46,084
και αυτό είναι πραγματικά καλή διαίσθηση.

500
00:24:46,084 --> 00:24:48,080
Και να συνειδητοποιήσουμε ότι είμαστε
οι άνθρωποι είναι στην πραγματικότητα αρκετά

501
00:24:48,080 --> 00:24:49,913
καλή στην επίλυση των προβλημάτων
όπως αυτό, τουλάχιστον

502
00:24:49,913 --> 00:24:51,810
όταν τα δεδομένα είναι σχετικά μικρή.

503
00:24:51,810 --> 00:24:54,860
Από τη στιγμή που θα αρχίσετε να έχετε εκατοντάδες
των αριθμών, χιλιάδες αριθμούς,

504
00:24:54,860 --> 00:24:58,440
τα εκατομμύρια των αριθμών, Ben πιθανώς
Δεν μπορούσε να το κάνει αρκετά τόσο γρήγορα,

505
00:24:58,440 --> 00:25:00,620
υποθέτοντας ότι υπήρχαν
κενά στους αριθμούς.

506
00:25:00,620 --> 00:25:03,450
Αρκετά εύκολο να μετρούν μέχρι το ένα εκατομμύριο
Αλλιώς, απλά χρονοβόρα.

507
00:25:03,450 --> 00:25:07,150
>> Έτσι, ο αλγόριθμος ακούγεται
όπως ο Ben χρησιμοποιείται μόλις τώρα

508
00:25:07,150 --> 00:25:08,930
ήταν αναζήτηση για το μικρότερο αριθμό.

509
00:25:08,930 --> 00:25:12,900
Έτσι ακόμα κι αν εμείς οι άνθρωποι μπορούν να λάβουν
σε πολλές πληροφορίες οπτικά,

510
00:25:12,900 --> 00:25:14,830
ένας υπολογιστής είναι στην πραγματικότητα
λίγο πιο περιορισμένη.

511
00:25:14,830 --> 00:25:17,560
Ο υπολογιστής μπορεί μόνο
εξετάσουμε ένα byte σε μια στιγμή

512
00:25:17,560 --> 00:25:20,770
ή ίσως τέσσερα bytes σε time--
αυτές τις μέρες ίσως 8 bytes σε time--

513
00:25:20,770 --> 00:25:24,450
αλλά ένας πολύ μικρός αριθμός
από bytes σε μια δεδομένη στιγμή.

514
00:25:24,450 --> 00:25:28,480
>> Έτσι, δεδομένου ότι έχουμε πραγματικά
τέσσερις ξεχωριστές τιμές here--

515
00:25:28,480 --> 00:25:32,440
και μπορείτε να σκεφτείτε Ben ως έχουσα
παρωπίδες αν ήταν ένας υπολογιστής όπως

516
00:25:32,440 --> 00:25:36,450
ότι δεν μπορεί να δει τίποτα άλλο
από έναν αριθμό σε ένα time--

517
00:25:36,450 --> 00:25:39,720
έτσι γενικά θα αναλάβει, όπως και σε
Αγγλικά, θα διαβάζονται από τα δεξιά προς τα αριστερά.

518
00:25:39,720 --> 00:25:42,870
Έτσι, ο πρώτος αριθμός Ben πιθανότατα κοίταξε
σε ήταν τέσσερα και στη συνέχεια πολύ γρήγορα

519
00:25:42,870 --> 00:25:44,770
συνειδητοποίησα ότι είναι ένα αρκετά μεγάλο
number-- επιτρέψτε μου να συνεχίσετε να ψάχνετε.

520
00:25:44,770 --> 00:25:45,357
>> Υπάρχουν δύο.

521
00:25:45,357 --> 00:25:45,940
Περίμενε ένα λεπτό.

522
00:25:45,940 --> 00:25:47,070
Δύο είναι μικρότερο από τέσσερα.

523
00:25:47,070 --> 00:25:47,986
Πάω να θυμόμαστε.

524
00:25:47,986 --> 00:25:49,070
Δύο είναι τώρα το μικρότερο.

525
00:25:49,070 --> 00:25:50,417
Τώρα ένα-- που είναι ακόμα καλύτερη.

526
00:25:50,417 --> 00:25:51,250
Αυτό είναι ακόμη μικρότερο.

527
00:25:51,250 --> 00:25:54,000
Πάω να ξεχάσουμε δύο
και απλά να θυμάστε ένα τώρα.

528
00:25:54,000 --> 00:25:56,550
>> Και θα μπορούσε να σταματήσει να ψάχνει;

529
00:25:56,550 --> 00:25:58,360
Καλά, αυτός θα μπορούσε να βασίζεται
σε αυτές τις πληροφορίες,

530
00:25:58,360 --> 00:26:00,477
αλλά είχε καλύτερη αναζήτηση
το υπόλοιπο της λίστας.

531
00:26:00,477 --> 00:26:02,060
Γιατί ό, τι και αν το μηδέν ήταν στη λίστα;

532
00:26:02,060 --> 00:26:03,643
Τι θα συμβεί αν αρνητικό ήταν στη λίστα;

533
00:26:03,643 --> 00:26:07,720
Ξέρει μόνο ότι η απάντησή του
είναι σωστή, αν αυτός είναι εξαντλητικά

534
00:26:07,720 --> 00:26:08,729
ελεγχθεί όλη τη λίστα.

535
00:26:08,729 --> 00:26:10,020
Έτσι, θα εξετάσουμε το υπόλοιπο αυτού.

536
00:26:10,020 --> 00:26:11,394
Τρία-- ότι ήταν χάσιμο χρόνου.

537
00:26:11,394 --> 00:26:13,540
Πήρε άτυχος, αλλά ήμουν
ακόμα σωστό να το πράξουν.

538
00:26:13,540 --> 00:26:17,857
Και έτσι τώρα προφανώς
επιλέγεται το μικρότερο αριθμό

539
00:26:17,857 --> 00:26:20,440
και μόλις το θέσει στην αρχή
της λίστας, όπως θα το κάνω εδώ.

540
00:26:20,440 --> 00:26:23,480
Τώρα τι έκανες επόμενη, ακόμη και αν
εσείς δεν το σκέφτομαι σχεδόν

541
00:26:23,480 --> 00:26:25,962
σε αυτό το βαθμό;

542
00:26:25,962 --> 00:26:27,670
Επαναλάβετε τη διαδικασία,
έτσι κάποιο είδος βρόχου.

543
00:26:27,670 --> 00:26:28,920
Υπάρχει μια γνωστή ιδέα.

544
00:26:28,920 --> 00:26:30,860
Έτσι, εδώ είναι τέσσερις.

545
00:26:30,860 --> 00:26:32,110
Αυτό είναι σήμερα το μικρότερο.

546
00:26:32,110 --> 00:26:33,220
Αυτός είναι ένας υποψήφιος.

547
00:26:33,220 --> 00:26:33,900
Όχι πια.

548
00:26:33,900 --> 00:26:34,770
Τώρα που έχω δει δύο.

549
00:26:34,770 --> 00:26:36,630
Αυτό είναι το επόμενο μικρότερο στοιχείο.

550
00:26:36,630 --> 00:26:40,800
Τρία-- ότι δεν είναι μικρότερο, οπότε
τώρα Ben μπορεί να κόβω το δύο.

551
00:26:40,800 --> 00:26:44,510
>> Και τώρα μπορούμε να επαναλάβετε τη διαδικασία, και
Φυσικά τριών παίρνει τράβηξε έξω την επόμενη.

552
00:26:44,510 --> 00:26:45,420
Επαναλάβετε τη διαδικασία.

553
00:26:45,420 --> 00:26:46,990
Τέσσερις παίρνει τράβηξε έξω.

554
00:26:46,990 --> 00:26:50,140
Και τώρα είμαστε από τους αριθμούς,
έτσι ώστε ο κατάλογος αυτός πρέπει να ταξινομηθούν.

555
00:26:50,140 --> 00:26:51,960
>> Και πράγματι, αυτό είναι μια επίσημη αλγόριθμο.

556
00:26:51,960 --> 00:26:56,610
Ένας επιστήμονας υπολογιστών θα
καλέσετε αυτό το «είδος επιλογής,"

557
00:26:56,610 --> 00:27:00,880
Η ιδέα είναι είδος μια
λίστα iteratively-- και πάλι

558
00:27:00,880 --> 00:27:03,807
και ξανά και ξανά, επιλέγοντας
ο μικρότερος αριθμός.

559
00:27:03,807 --> 00:27:06,140
Και τι είναι ωραίο γι 'αυτό είναι
είναι ακριβώς έτσι καταριέται διαισθητική.

560
00:27:06,140 --> 00:27:07,470
Είναι τόσο απλό.

561
00:27:07,470 --> 00:27:11,100
Και μπορείτε να επαναλάβετε την ίδια
λειτουργία ξανά και ξανά.

562
00:27:11,100 --> 00:27:12,150
Είναι απλό.

563
00:27:12,150 --> 00:27:17,170
>> Σε αυτή την περίπτωση ήταν γρήγορο, αλλά
πόσο χρόνο χρειάζεται στην πραγματικότητα να λάβει;

564
00:27:17,170 --> 00:27:19,880
Ας το κάνουμε να φαίνεται και
αισθάνονται λίγο πιο κουραστικό.

565
00:27:19,880 --> 00:27:24,150
Έτσι, ένα, δύο, τρία, τέσσερα, πέντε έξι,
επτά, οκτώ, εννέα, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- αυθαίρετο αριθμό.

567
00:27:26,160 --> 00:27:28,780
Απλά ήθελα περισσότερο αυτό
χρόνο από ό, τι ακριβώς τους τέσσερις.

568
00:27:28,780 --> 00:27:30,780
Έτσι, αν έχω ένα ολόκληρο
δέσμη των αριθμών που now--

569
00:27:30,780 --> 00:27:32,420
Δεν πειράζει ακόμη και
τι are-- ας

570
00:27:32,420 --> 00:27:34,380
σκεφτείτε τι είναι αυτό
αλγόριθμος είναι πολύ παρόμοια.

571
00:27:34,380 --> 00:27:35,857
>> Ας υποθέσουμε ότι υπάρχουν αριθμοί εκεί.

572
00:27:35,857 --> 00:27:38,190
Και πάλι, δεν έχει σημασία τι
είναι, αλλά είναι τυχαία.

573
00:27:38,190 --> 00:27:39,679
Είμαι εφαρμόζοντας τον αλγόριθμο του Ben.

574
00:27:39,679 --> 00:27:41,220
Θα πρέπει να επιλέξετε το μικρότερο αριθμό.

575
00:27:41,220 --> 00:27:41,761
Τι κάνω?

576
00:27:41,761 --> 00:27:44,240
Και Πάω να σωματικά
το κάνει αυτή τη φορά για να ενεργήσει έξω.

577
00:27:44,240 --> 00:27:46,099
Ψάχνουν, ψάχνουν,
ψάχνουν, ψάχνουν, ψάχνουν.

578
00:27:46,099 --> 00:27:48,140
Μόνο από τη στιγμή που έχω να
το τέλος της λίστας μπορεί να

579
00:27:48,140 --> 00:27:51,230
Αντιλαμβάνομαι το μικρότερο
αριθμός ήταν δυο αυτή τη φορά.

580
00:27:51,230 --> 00:27:52,720
Κάποιος δεν είναι στη λίστα.

581
00:27:52,720 --> 00:27:54,400
Έτσι έβαλα κάτω δύο.

582
00:27:54,400 --> 00:27:55,590
>> Τι μπορώ να κάνω το επόμενο βήμα;

583
00:27:55,590 --> 00:27:58,600
Ψάχνουν, ψάχνουν, ψάχνουν, ψάχνουν.

584
00:27:58,600 --> 00:28:02,250
Τώρα βρήκα τον αριθμό επτά, επειδή
υπάρχει κενά σε αυτές τις numbers--

585
00:28:02,250 --> 00:28:03,300
αλλά απλώς αυθαίρετη.

586
00:28:03,300 --> 00:28:03,800
Εντάξει.

587
00:28:03,800 --> 00:28:06,030
Έτσι τώρα μπορώ να βάλω κάτω επτά.

588
00:28:06,030 --> 00:28:08,860
Κοιτάζοντας ψάχνουν, ψάχνουν.

589
00:28:08,860 --> 00:28:11,030
>> Τώρα υποθέτω, της
Φυσικά, ότι ο Ben δεν

590
00:28:11,030 --> 00:28:14,780
έχουν επιπλέον μνήμη RAM, επιπλέον
μνήμη, επειδή, φυσικά,

591
00:28:14,780 --> 00:28:16,080
Ψάχνω στον ίδιο αριθμό.

592
00:28:16,080 --> 00:28:18,246
Σίγουρα θα μπορούσα να είχα θυμήθηκε
όλων αυτών των αριθμών,

593
00:28:18,246 --> 00:28:19,930
και αυτό είναι απολύτως αληθές.

594
00:28:19,930 --> 00:28:22,610
Αλλά αν ο Μπεν θυμάται όλα
των αριθμών έχει δει,

595
00:28:22,610 --> 00:28:24,430
δεν έχει κάνει πραγματικά
θεμελιώδη πρόοδο

596
00:28:24,430 --> 00:28:26,170
επειδή έχει ήδη
η δυνατότητα να αναζητήσετε

597
00:28:26,170 --> 00:28:27,540
μέσα από τους αριθμούς στον πίνακα.

598
00:28:27,540 --> 00:28:29,373
Ενθυμούμενος όλα τα
αριθμοί δεν βοηθά,

599
00:28:29,373 --> 00:28:32,490
γιατί μπορεί ακόμα και έναν υπολογιστή
μόνο να δούμε, έχουμε πει, έναν αριθμό

600
00:28:32,490 --> 00:28:33,080
σε μια στιγμή.

601
00:28:33,080 --> 00:28:35,760
Έτσι, δεν υπάρχει είδος cheat
εκεί που μπορείτε να αξιοποιήσετε.

602
00:28:35,760 --> 00:28:39,170
>> Έτσι, στην πραγματικότητα, όπως εγώ
να συνεχιστεί η αναζήτηση του καταλόγου,

603
00:28:39,170 --> 00:28:44,200
Έχω κυριολεκτικά πρέπει να συνεχίζουν να εργάζονται
εμπρός και πίσω μέσα από αυτό, το μάδημα έξω

604
00:28:44,200 --> 00:28:45,710
το επόμενο μικρότερο αριθμό.

605
00:28:45,710 --> 00:28:48,810
Και όπως μπορείτε είδος μπορεί να συμπεράνει
από ανόητες κινήσεις μου,

606
00:28:48,810 --> 00:28:50,860
αυτό παίρνει απλά πολύ
κουραστική πολύ γρήγορα,

607
00:28:50,860 --> 00:28:54,850
και μου φαίνεται να πηγαίνει πίσω και
εμπρός, εμπρός και πίσω αρκετά.

608
00:28:54,850 --> 00:29:03,220
Τώρα για να είμαστε δίκαιοι, δεν έχω να πάω
τόσο, καλά, ας see-- για να είμαστε δίκαιοι,

609
00:29:03,220 --> 00:29:06,310
Δεν έχω να περπατήσει αρκετά
όπως πολλά βήματα κάθε φορά.

610
00:29:06,310 --> 00:29:09,200
Διότι, φυσικά, όπως
επιλέξετε αριθμούς από τη λίστα,

611
00:29:09,200 --> 00:29:11,860
το υπόλοιπο κατάλογος γίνεται όλο και μικρότερη.

612
00:29:11,860 --> 00:29:14,240
>> Και έτσι ας σκεφτούμε
πόσα βήματα Είμαι πραγματικά

613
00:29:14,240 --> 00:29:16,010
traipsing μέσα από κάθε φορά.

614
00:29:16,010 --> 00:29:18,950
Στην πρώτη κατάσταση
είχαμε 16 αριθμούς,

615
00:29:18,950 --> 00:29:22,210
και έτσι maximally-- ας μόνο
κάνετε αυτό για μια discussion--

616
00:29:22,210 --> 00:29:25,640
Έπρεπε να δούμε μέσα από 16
αριθμούς για να βρει το μικρότερο.

617
00:29:25,640 --> 00:29:28,420
Αλλά από τη στιγμή που ξεριζώθηκαν
ο μικρότερος αριθμός, πώς

618
00:29:28,420 --> 00:29:30,590
μακρύ ήταν το υπόλοιπο λίστα, φυσικά;

619
00:29:30,590 --> 00:29:31,420
Μόλις 15.

620
00:29:31,420 --> 00:29:34,670
Έτσι, πόσοι αριθμοί έκαναν Ben ή έχω
να κοιτάξετε μέσα από την δεύτερη φορά γύρω;

621
00:29:34,670 --> 00:29:36,832
15, ακριβώς για να πάει και να βρει το μικρότερο.

622
00:29:36,832 --> 00:29:39,540
Αλλά τώρα, φυσικά, ο κατάλογος είναι,
πάρα πολύ, μικρότερα από ό, τι ήταν πριν.

623
00:29:39,540 --> 00:29:42,540
Έτσι, πόσα βήματα έκανα
πρέπει να λάβει την επόμενη φορά;

624
00:29:42,540 --> 00:29:49,970
14 και στη συνέχεια 13 και στη συνέχεια 12, συν τελεία,
τελεία, τελεία, μέχρι να είμαι αριστερά με ένα μόνο.

625
00:29:49,970 --> 00:29:53,146
Έτσι τώρα ένας επιστήμονας υπολογιστών θα
ρωτήσω, καλά, τι κάνει ότι όλοι ίσοι;

626
00:29:53,146 --> 00:29:55,770
Ισούται πραγματικά κάποια συγκεκριμένη
αριθμός που θα μπορούσαμε σίγουρα

627
00:29:55,770 --> 00:30:00,490
κάνουν αριθμητικά, αλλά θέλουμε να μιλήσουμε
σχετικά με την αποτελεσματικότητα των αλγορίθμων

628
00:30:00,490 --> 00:30:04,940
λίγο πιο formulaically,
ανεξάρτητα από το πόσο καιρό η λίστα είναι.

629
00:30:04,940 --> 00:30:06,240
>> Και έτσι ξέρετε τι;

630
00:30:06,240 --> 00:30:09,860
Αυτό είναι 16, αλλά όπως είπα και πριν,
ας καλέσει το μέγεθος του προβλήματος

631
00:30:09,860 --> 00:30:10,970
n, όπου το η είναι κάποιος αριθμός.

632
00:30:10,970 --> 00:30:13,220
Ίσως είναι 16, ίσως είναι
τρία, ίσως είναι ένα εκατομμύριο.

633
00:30:13,220 --> 00:30:13,761
Δεν γνωρίζω.

634
00:30:13,761 --> 00:30:14,390
Δεν με νοιάζει.

635
00:30:14,390 --> 00:30:16,520
Αυτό που θέλω πραγματικά είναι
ένας τύπος που μπορώ

636
00:30:16,520 --> 00:30:19,420
χρησιμοποιήσετε για να συγκρίνετε αυτόν τον αλγόριθμο
έναντι άλλων αλγορίθμων

637
00:30:19,420 --> 00:30:22,350
ότι κάποιος μπορεί να ισχυριστεί
είναι καλύτερα ή χειρότερα.

638
00:30:22,350 --> 00:30:25,430
>> Έτσι αποδεικνύεται, και μόνο εγώ
το γνωρίζουν αυτό από το σχολείο βαθμού,

639
00:30:25,430 --> 00:30:34,790
ότι αυτό λειτουργεί πραγματικά έξω στο ίδιο
πράγμα όπως n πάνω από n συν ένα πάνω από δύο.

640
00:30:34,790 --> 00:30:40,020
Και αυτό συμβαίνει να είναι ίση, της
Φυσικά, n στο τετράγωνο συν ν πάνω από δύο.

641
00:30:40,020 --> 00:30:43,250
Έτσι, αν ήθελα μια φόρμουλα
για πόσα βήματα

642
00:30:43,250 --> 00:30:46,330
συμμετείχαν στην εξέταση όλων
αυτών των αριθμών ξανά και ξανά

643
00:30:46,330 --> 00:30:52,681
και ξανά και ξανά, θα έλεγα
αυτό είναι n στο τετράγωνο συν ν πάνω από δύο.

644
00:30:52,681 --> 00:30:53,430
Αλλά ξέρετε τι;

645
00:30:53,430 --> 00:30:54,500
Αυτό ακριβώς φαίνεται βρώμικο.

646
00:30:54,500 --> 00:30:56,470
Απλά θέλω πραγματικά ένα
γενική αίσθηση των πραγμάτων.

647
00:30:56,470 --> 00:30:58,810
Και ίσως να θυμάστε από
γυμνάσιο ότι υπάρχει

648
00:30:58,810 --> 00:31:00,660
είναι η έννοια της υψηλότερης όρος τάξης.

649
00:31:00,660 --> 00:31:05,300
Ποια από αυτούς τους όρους, η n
τετράγωνο, το Ν, ή το μισό,

650
00:31:05,300 --> 00:31:07,550
έχει το μεγαλύτερο αντίκτυπο την πάροδο του χρόνου;

651
00:31:07,550 --> 00:31:11,920
Το μεγαλύτερο n παίρνει, η οποία
αυτών των θεμάτων το πιο;

652
00:31:11,920 --> 00:31:15,560
>> Με άλλα λόγια, αν συνδέω
σε ένα εκατομμύριο, n τετράγωνο

653
00:31:15,560 --> 00:31:17,900
πρόκειται να είναι πιο πιθανό
ο κυρίαρχος παράγοντας,

654
00:31:17,900 --> 00:31:21,670
ένα εκατομμύριο γιατί οι καιροί
από μόνη της είναι πολύ μεγαλύτερο

655
00:31:21,670 --> 00:31:23,682
από συν ένα επιπλέον εκατομμύριο.

656
00:31:23,682 --> 00:31:24,390
Έτσι, ξέρετε τι;

657
00:31:24,390 --> 00:31:27,305
Αυτό είναι μια τέτοια καταριέται μεγάλο
αριθμός αν τακτοποιήσει έναν αριθμό.

658
00:31:27,305 --> 00:31:28,430
Αυτό δεν πειράζει πραγματικά.

659
00:31:28,430 --> 00:31:30,596
Εμείς απλά θα σταυρό που
έξω και να ξεχάσουμε αυτό.

660
00:31:30,596 --> 00:31:34,250
Και έτσι ένας επιστήμονας υπολογιστών θα έλεγα
ότι η αποτελεσματικότητα αυτού του αλγορίθμου

661
00:31:34,250 --> 00:31:37,850
είναι της τάξης του n squared--
Εννοώ πραγματικά μια προσέγγιση.

662
00:31:37,850 --> 00:31:40,810
Είναι το είδος των περίπου n στο τετράγωνο.

663
00:31:40,810 --> 00:31:44,130
Την πάροδο του χρόνου, το μεγαλύτερο
και μεγαλύτερα n παίρνει, αυτό

664
00:31:44,130 --> 00:31:47,610
είναι μια καλή εκτίμηση για το ποια είναι η
απόδοση ή έλλειψη αποτελεσματικότητας

665
00:31:47,610 --> 00:31:49,400
αυτού του αλγορίθμου είναι στην πραγματικότητα.

666
00:31:49,400 --> 00:31:52,040
Και εγώ αντλούν αυτό, φυσικά,
από πραγματικά να κάνει τα μαθηματικά.

667
00:31:52,040 --> 00:31:54,040
Αλλά τώρα είμαι απλά κουνώντας
τα χέρια μου, γιατί απλά

668
00:31:54,040 --> 00:31:55,790
θέλουν μια γενική αίσθηση αυτού του αλγορίθμου.

669
00:31:55,790 --> 00:31:58,850
>> Έτσι, χρησιμοποιώντας την ίδια λογική, εν τω μεταξύ,
Ας εξετάσουμε ένα άλλο αλγόριθμο

670
00:31:58,850 --> 00:32:01,162
έχουμε ήδη εξετάσει at-- γραμμική αναζήτηση.

671
00:32:01,162 --> 00:32:02,870
Όταν έψαχνα
για το τηλέφωνο book--

672
00:32:02,870 --> 00:32:05,980
Δεν είναι η διαλογή, αναζήτηση
μέσω του τηλεφώνου book--

673
00:32:05,980 --> 00:32:09,197
θα έλεγε ότι ήταν
1000 βήματα, ή 500 βήματα.

674
00:32:09,197 --> 00:32:10,280
Αλλά ας γενικεύσουμε αυτό.

675
00:32:10,280 --> 00:32:12,860
Αν υπάρχει n σελίδες
ο τηλεφωνικός κατάλογος, τι είναι

676
00:32:12,860 --> 00:32:17,250
ο χρόνος εκτέλεσης ή της
αποτελεσματικότητα της γραμμικής αναζήτησης;

677
00:32:17,250 --> 00:32:19,750
Είναι της τάξης των
πόσα βήματα για να βρείτε

678
00:32:19,750 --> 00:32:24,210
Mike Smith με τη βοήθεια γραμμικής αναζήτησης, η
πρώτο αλγόριθμο, ή ακόμη και η δεύτερη;

679
00:32:24,210 --> 00:32:27,240

680
00:32:27,240 --> 00:32:31,710
>> Στη χειρότερη περίπτωση, ο Mike
βρίσκεται στο τέλος του βιβλίου.

681
00:32:31,710 --> 00:32:35,590
Έτσι, αν το βιβλίο τηλέφωνο έχει 1.000 σελίδες,
είπαμε την τελευταία φορά, στη χειρότερη περίπτωση,

682
00:32:35,590 --> 00:32:38,380
μπορεί να πάρει περίπου πόσο
πολλές σελίδες για να βρείτε Mike;

683
00:32:38,380 --> 00:32:38,990
Όπως και 1.000.

684
00:32:38,990 --> 00:32:39,830
Είναι ένα άνω φράγμα.

685
00:32:39,830 --> 00:32:41,790
Είναι μια χειρότερη δυνατή κατάσταση.

686
00:32:41,790 --> 00:32:44,410
Αλλά και πάλι, είμαστε κινείται μακριά
από αριθμούς όπως 1.000 τώρα.

687
00:32:44,410 --> 00:32:45,730
Είναι ακριβώς n.

688
00:32:45,730 --> 00:32:47,470
>> Έτσι, αυτό είναι το λογικό συμπέρασμα;

689
00:32:47,470 --> 00:32:50,210
Η εύρεση Mike σε ένα τηλέφωνο
βιβλίο που έχει n σελίδες

690
00:32:50,210 --> 00:32:55,280
θα μπορούσε να λάβει, σε πολύ χειρότερη περίπτωση,
πόσα βήματα της τάξης του n;

691
00:32:55,280 --> 00:32:58,110
Και πράγματι ένας υπολογιστής
επιστήμονας θα έλεγε

692
00:32:58,110 --> 00:33:02,340
ότι ο χρόνος τρέχει, ή η
απόδοση ή την αποτελεσματικότητα

693
00:33:02,340 --> 00:33:07,470
ή αναποτελεσματικότητα, ενός αλγορίθμου όπως
μια γραμμική έρευνα είναι της τάξης του n.

694
00:33:07,470 --> 00:33:10,010
Και μπορούμε να εφαρμόσουμε την ίδια
λογική διέλευση κάτι

695
00:33:10,010 --> 00:33:13,170
όπως έκανα ακριβώς στο δεύτερο
αλγόριθμο που είχαμε με τον τηλεφωνικό κατάλογο,

696
00:33:13,170 --> 00:33:16,040
όπου πήγαμε δύο σελίδες σε έναν χρόνο.

697
00:33:16,040 --> 00:33:20,120
>> Έτσι 1,000 σελίδα τηλεφωνικός κατάλογος θα μπορούσε
να μας πάρει 500 στροφές σελίδα, συν ένα

698
00:33:20,120 --> 00:33:21,910
αν έχουμε διπλασιάσει πίσω λίγο.

699
00:33:21,910 --> 00:33:26,590
Έτσι, αν ένας τηλεφωνικός κατάλογος έχει n σελίδες, αλλά
κάνουμε δύο σελίδες σε έναν χρόνο,

700
00:33:26,590 --> 00:33:28,900
αυτό είναι σχεδόν ό, τι;

701
00:33:28,900 --> 00:33:33,190
Ν πάνω από δύο, έτσι ώστε να είναι σαν ν πάνω από δύο.

702
00:33:33,190 --> 00:33:38,490
Αλλά έκανα το αίτημα ενός
πριν από λίγο ότι n πάνω two--

703
00:33:38,490 --> 00:33:41,060
αυτό είναι το είδος της το ίδιο ακριβώς n.

704
00:33:41,060 --> 00:33:44,050
Είναι απλά ένα σταθερό συντελεστή,
επιστήμονες υπολογιστών θα έλεγα.

705
00:33:44,050 --> 00:33:45,970
Ας επικεντρωθεί μόνο σε
οι μεταβλητές, really--

706
00:33:45,970 --> 00:33:47,780
οι μεγαλύτερες μεταβλητές στην εξίσωση.

707
00:33:47,780 --> 00:33:52,530
>> Έτσι γραμμική αναζήτηση, αν γίνει ένα
σελίδα τη φορά ή δύο σελίδες σε έναν χρόνο,

708
00:33:52,530 --> 00:33:54,810
είναι είδος ουσιαστικά το ίδιο.

709
00:33:54,810 --> 00:33:56,880
Είναι ακόμα της τάξεως των n.

710
00:33:56,880 --> 00:34:01,930
Αλλά εγώ ισχυρίστηκε με την εικόνα μου νωρίτερα
ότι η τρίτη αλγόριθμος δεν ήταν

711
00:34:01,930 --> 00:34:02,480
γραμμικός.

712
00:34:02,480 --> 00:34:03,605
Δεν ήταν μια ευθεία γραμμή.

713
00:34:03,605 --> 00:34:08,659
Ήταν ότι καμπύλη γραμμή, και ο
τύπο αλγεβρικό εκεί ήταν αυτό;

714
00:34:08,659 --> 00:34:11,812
Σύνδεση του n-- έτσι log βάση δύο από n.

715
00:34:11,812 --> 00:34:14,520
Και δεν έχουμε να πάει σε πάρα
πολλές λεπτομέρειες σχετικά με λογαρίθμους σήμερα,

716
00:34:14,520 --> 00:34:17,394
αλλά οι περισσότεροι επιστήμονες της πληροφορικής δεν θα
ακόμη και να σας πω ποια είναι η βάση είναι.

717
00:34:17,394 --> 00:34:20,639
Επειδή είναι όλα απλά
σταθερούς παράγοντες, να το πω έτσι,

718
00:34:20,639 --> 00:34:22,659
μόνο μικρές αριθμητικές διαφορές.

719
00:34:22,659 --> 00:34:31,179
Και έτσι αυτό θα είναι ένα πολύ κοινό
τρόπος για ιδιαίτερα επίσημη υπολογιστή

720
00:34:31,179 --> 00:34:33,949
επιστήμονες σε έναν πίνακα ή
προγραμματιστές σε ένα λευκό του σκάφους

721
00:34:33,949 --> 00:34:36,889
στην πραγματικότητα το επιχείρημα το οποίο
αλγόριθμος που θα χρησιμοποιήσετε

722
00:34:36,889 --> 00:34:39,500
ή ποια είναι η απόδοση
του αλγορίθμου τους είναι.

723
00:34:39,500 --> 00:34:42,960
>> Και αυτό δεν είναι κατ 'ανάγκη κάτι
θα συζητήσουμε σε κάθε μεγάλη λεπτομέρεια,

724
00:34:42,960 --> 00:34:47,889
αλλά ένας καλός προγραμματιστής είναι κάποιος
ο οποίος έχει μια σταθερή, επίσημη φόντο.

725
00:34:47,889 --> 00:34:50,120
Είναι σε θέση να μιλήσει με
σας σε αυτό το είδος του τρόπου

726
00:34:50,120 --> 00:34:53,350
και πραγματικά να κάνει
ποιοτικά επιχειρήματα

727
00:34:53,350 --> 00:34:56,870
γιατί ένα αλγόριθμο ή
ένα κομμάτι του λογισμικού

728
00:34:56,870 --> 00:35:00,165
είναι ανώτερη κατά κάποιο τρόπο σε μια άλλη.

729
00:35:00,165 --> 00:35:02,540
Επειδή θα μπορούσατε σίγουρα
απλά τρέξτε το πρόγραμμα ενός ατόμου

730
00:35:02,540 --> 00:35:04,980
και μετρήστε τον αριθμό των δευτερολέπτων
που χρειάζεται για να ταξινομήσετε κάποιους αριθμούς,

731
00:35:04,980 --> 00:35:06,710
και μπορείτε να εκτελέσετε κάποια
πρόγραμμα άλλου ατόμου

732
00:35:06,710 --> 00:35:08,418
και μετρήστε τον αριθμό
των δευτερολέπτων που χρειάζεται.

733
00:35:08,418 --> 00:35:12,840
Αλλά αυτό είναι ένα γενικότερο τρόπο ότι
μπορείτε να χρησιμοποιήσετε για να αναλύσει αλγορίθμων,

734
00:35:12,840 --> 00:35:15,520
αν θέλετε, μόνο για
χαρτί ή απλά προφορικά.

735
00:35:15,520 --> 00:35:18,430
Χωρίς καν να τρέχει, χωρίς να
ακόμη προσπαθούν εισόδους του δείγματος,

736
00:35:18,430 --> 00:35:20,180
μπορείτε απλά να λόγο μέσα από αυτό.

737
00:35:20,180 --> 00:35:24,670
Και έτσι με την πρόσληψη ενός προγραμματιστή ή αν
που έχει το άτομό του είδους υποστηρίζουν για να σας

738
00:35:24,670 --> 00:35:28,460
γιατί αλγόριθμο τους, το μυστικό τους
σάλτσα για την αναζήτηση δισεκατομμύρια

739
00:35:28,460 --> 00:35:30,580
των ιστοσελίδων για σας
Η εταιρεία είναι καλύτερη, αυτά

740
00:35:30,580 --> 00:35:33,302
είναι τα είδη των επιχειρημάτων που
θα πρέπει ιδανικά να είναι σε θέση να κάνει.

741
00:35:33,302 --> 00:35:35,010
Ή τουλάχιστον αυτά είναι
τα είδη των πραγμάτων

742
00:35:35,010 --> 00:35:40,211
ότι θα καταλήξει στη συζήτηση, σε
τουλάχιστον σε μια πολύ τυπική συζήτηση.

743
00:35:40,211 --> 00:35:40,710
Εντάξει.

744
00:35:40,710 --> 00:35:44,400
Έτσι Μπεν πρότεινε κάτι
ονομάζεται το είδος επιλογής.

745
00:35:44,400 --> 00:35:48,200
Αλλά Πάω να προτείνω ότι υπάρχει
άλλους τρόπους για να γίνει αυτό, πάρα πολύ.

746
00:35:48,200 --> 00:35:50,400
Αυτό που δεν μου άρεσε πραγματικά
σχετικά με τον αλγόριθμο του Ben

747
00:35:50,400 --> 00:35:54,400
είναι ότι διατηρούνται τα πόδια, ή
αφού με τα πόδια, και πίσω

748
00:35:54,400 --> 00:35:56,930
και μπροστά και πίσω και εμπρός και πίσω.

749
00:35:56,930 --> 00:36:04,130
Τι θα συμβεί αν αντί γι 'αυτό ήταν να κάνω
κάτι σαν αυτούς τους αριθμούς εδώ

750
00:36:04,130 --> 00:36:08,200
και εγώ έπρεπε να ασχολείται μόνο με το καθένα
αριθμό με τη σειρά του, όπως είμαι δώσει;

751
00:36:08,200 --> 00:36:10,780
>> Με άλλα λόγια, είναι εδώ
λίστα μου αριθμών.

752
00:36:10,780 --> 00:36:12,944
Τέσσερις, ένα, τρία, δύο.

753
00:36:12,944 --> 00:36:14,360
Και Πάω να κάνω το εξής.

754
00:36:14,360 --> 00:36:17,230
Πάω να εισάγετε τους αριθμούς
όπου ανήκουν μάλλον

755
00:36:17,230 --> 00:36:18,980
από την επιλογή τους, ένα κάθε φορά.

756
00:36:18,980 --> 00:36:20,820
Με άλλα λόγια, εδώ είναι το νούμερο τέσσερα.

757
00:36:20,820 --> 00:36:22,430
>> Εδώ είναι αρχική λίστα μου.

758
00:36:22,430 --> 00:36:25,290
Και Πάω να διατηρήσουν
ουσιαστικά μια νέα λίστα εδώ.

759
00:36:25,290 --> 00:36:26,710
Έτσι, αυτό είναι το παλιό λίστα.

760
00:36:26,710 --> 00:36:28,560
Αυτή είναι η νέα λίστα.

761
00:36:28,560 --> 00:36:30,220
Βλέπω τον αριθμό τέσσερα πρώτα.

762
00:36:30,220 --> 00:36:34,500
νέα λίστα μου είναι αρχικά κενή,
έτσι είναι κοινότοπα συμβαίνει

763
00:36:34,500 --> 00:36:36,410
ότι τέσσερις είναι τώρα ανάμικτες λίστα.

764
00:36:36,410 --> 00:36:39,560
Είμαι απλά παίρνετε τον αριθμό Είμαι δοθεί,
και είμαι το θέτει σε νέα λίστα μου.

765
00:36:39,560 --> 00:36:41,460
>> Ταξινομείται αυτή η νέα λίστα;

766
00:36:41,460 --> 00:36:41,990
Ναι.

767
00:36:41,990 --> 00:36:45,090
Είναι ηλίθιο επειδή υπάρχει μόνο ένα
στοιχείο, αλλά είναι απολύτως ταξινομημένο.

768
00:36:45,090 --> 00:36:46,390
Δεν υπάρχει τίποτα εκτός τόπου.

769
00:36:46,390 --> 00:36:49,290
Είναι πιο ενδιαφέρον, ο αλγόριθμος αυτός,
όταν προχωρήσουμε στο επόμενο βήμα.

770
00:36:49,290 --> 00:36:50,550
>> Τώρα έχω ένα.

771
00:36:50,550 --> 00:36:55,430
Έτσι ένα, φυσικά, ανήκει κατά τη
αρχή ή στο τέλος αυτής της νέας λίστας;

772
00:36:55,430 --> 00:36:56,360
Η αρχη.

773
00:36:56,360 --> 00:36:58,530
Έτσι έχω να κάνω κάποια δουλειά τώρα.

774
00:36:58,530 --> 00:37:01,410
Έχω ήδη λάβει κάποια
ελευθερίες με δείκτη μου

775
00:37:01,410 --> 00:37:03,120
από απλά αντλώντας τα πράγματα
όπου εγώ τους θέλω,

776
00:37:03,120 --> 00:37:05,320
αλλά αυτό δεν είναι πραγματικά
ακριβής σε έναν υπολογιστή.

777
00:37:05,320 --> 00:37:08,530
Ένας υπολογιστής, όπως γνωρίζουμε, έχει
RAM, ή μνήμη τυχαίας προσπέλασης,

778
00:37:08,530 --> 00:37:12,411
και αυτό είναι ένα byte και
ένα άλλο byte και ένα άλλο byte.

779
00:37:12,411 --> 00:37:14,910
Και αν έχετε ένα gigabyte του
RAM, έχετε ένα δισεκατομμύριο bytes,

780
00:37:14,910 --> 00:37:16,680
αλλά είναι φυσικά σε μία θέση.

781
00:37:16,680 --> 00:37:19,540
Μπορείτε όχι μόνο να κινηθούν τα πράγματα γύρω από
τραβώντας το στην πλακέτα

782
00:37:19,540 --> 00:37:20,750
όπου θέλεις.

783
00:37:20,750 --> 00:37:24,090
Έτσι, εάν η νέα λίστα μου έχει
τέσσερις θέσεις στη μνήμη,

784
00:37:24,090 --> 00:37:27,480
Δυστυχώς, οι τέσσερις είναι
ήδη σε λάθος μέρος.

785
00:37:27,480 --> 00:37:30,410
>> Έτσι για να εισάγετε τον αριθμό ένα
Δεν μπορώ απλά να επιστήσω εδώ.

786
00:37:30,410 --> 00:37:31,901
Αυτή η θέση μνήμης δεν υπάρχει.

787
00:37:31,901 --> 00:37:35,150
Αυτό θα ήταν εξαπάτηση, και έχω
εξαπάτηση με εικόνες για λίγα λεπτά

788
00:37:35,150 --> 00:37:35,800
εδώ.

789
00:37:35,800 --> 00:37:40,950
Έτσι, πραγματικά, αν θέλετε να βάλετε ένα εδώ,
Έχω να αντιγράψετε προσωρινά τα τέσσερα

790
00:37:40,950 --> 00:37:43,030
και στη συνέχεια, τοποθετήστε το ένα εκεί.

791
00:37:43,030 --> 00:37:45,500
>> Αυτό είναι εντάξει, αυτό είναι σωστό,
αυτό είναι τεχνικώς εφικτό,

792
00:37:45,500 --> 00:37:48,410
αλλά συνειδητοποιούν ότι η επιπλέον εργασία.

793
00:37:48,410 --> 00:37:50,460
Δεν είχα απλά βάλτε τον αριθμό στη θέση του.

794
00:37:50,460 --> 00:37:53,026
Θα έπρεπε πρώτα να μετακινήσετε ένα
αριθμός, τότε θα τεθεί σε εφαρμογή,

795
00:37:53,026 --> 00:37:54,650
γι 'αυτό το είδος της διπλασιάστηκε το ποσό της εργασίας μου.

796
00:37:54,650 --> 00:37:55,660
Έτσι, να το έχουμε κατά νου.

797
00:37:55,660 --> 00:37:57,120
>> Αλλά είμαι τώρα γίνει με αυτό το στοιχείο.

798
00:37:57,120 --> 00:37:59,056
Τώρα θέλω να αρπάξει τον αριθμό τρία.

799
00:37:59,056 --> 00:38:00,430
Όταν, βέβαια, δεν ανήκει;

800
00:38:00,430 --> 00:38:01,480
Ανάμεσα.

801
00:38:01,480 --> 00:38:03,650
Δεν μπορώ να εξαπατήσει πια
και απλά να βάλει εκεί,

802
00:38:03,650 --> 00:38:06,770
επειδή, και πάλι, αυτή τη μνήμη
Είναι σε φυσικές τοποθεσίες.

803
00:38:06,770 --> 00:38:10,900
Γι 'αυτό και πρέπει να αντιγράψετε τα τέσσερα
και να θέσει τα τρία εδώ.

804
00:38:10,900 --> 00:38:11,550
Δεν είναι μεγάλη υπόθεση.

805
00:38:11,550 --> 00:38:14,610
Είναι απλά ένα επιπλέον βήμα
again-- αισθάνεται πολύ φθηνή.

806
00:38:14,610 --> 00:38:16,445
>> Αλλά τώρα μπορώ να προχωρήσουμε στο δύο.

807
00:38:16,445 --> 00:38:17,820
Οι δύο, φυσικά, ανήκει εδώ.

808
00:38:17,820 --> 00:38:20,990
Τώρα θα αρχίσετε να βλέπετε πώς
η εργασία μπορεί να συσσωρεύονται.

809
00:38:20,990 --> 00:38:23,520
Τώρα τι πρέπει να κάνω;

810
00:38:23,520 --> 00:38:28,570
Ναι, έχω να μετακινήσετε το τέσσερα,
Θα πρέπει στη συνέχεια να αντιγράψετε το τρία,

811
00:38:28,570 --> 00:38:31,200
και τώρα μπορώ να τοποθετήσετε τα δύο.

812
00:38:31,200 --> 00:38:34,460
Και τα αλιεύματα με αυτό
αλγόριθμο, αρκετά ενδιαφέρον,

813
00:38:34,460 --> 00:38:41,050
είναι ότι ας υποθέσουμε ότι έχουμε μια πιο ακραία
περίπτωση που είναι ας πούμε οκτώ, επτά,

814
00:38:41,050 --> 00:38:45,150
έξι, πέντε, τέσσερα, τρία, δύο, ένα.

815
00:38:45,150 --> 00:38:49,450
Αυτό είναι, σε πολλές περιπτώσεις,
το χειρότερο σενάριο,

816
00:38:49,450 --> 00:38:51,570
γιατί το καταριέται το πράγμα
είναι κυριολεκτικά προς τα πίσω.

817
00:38:51,570 --> 00:38:53,670
>> Δεν έχει πραγματικά
επηρεάσει τον αλγόριθμο του Ben,

818
00:38:53,670 --> 00:38:55,940
γιατί στην επιλογή του Ben
είδος που πρόκειται να κρατήσει

819
00:38:55,940 --> 00:38:58,359
πηγαινοέρχονται μέσα στη λίστα.

820
00:38:58,359 --> 00:39:01,150
Και επειδή ήταν πάντα ψάχνει
όλη τη απομένει λίστα,

821
00:39:01,150 --> 00:39:02,858
δεν έχει σημασία
όπου τα στοιχεία είναι.

822
00:39:02,858 --> 00:39:05,630
Αλλά σε αυτή την περίπτωση εισαγωγής μου
approach-- ας προσπαθήσουμε αυτό.

823
00:39:05,630 --> 00:39:08,616
>> Έτσι, ένα, δύο, τρία, τέσσερα,
πέντε, έξι, επτά, οκτώ.

824
00:39:08,616 --> 00:39:11,630
Ένα δύο τρία τέσσερα,
πέντε, έξι, επτά, οκτώ.

825
00:39:11,630 --> 00:39:14,320
Πάω να πάρει το οκτώ,
και πού μπορώ να το πω;

826
00:39:14,320 --> 00:39:17,260
Λοιπόν, στην αρχή της λίστας μου,
επειδή αυτή η νέα λίστα είναι ταξινομημένο.

827
00:39:17,260 --> 00:39:18,760
Και εγώ το σταυρό έξω.

828
00:39:18,760 --> 00:39:20,551
>> Πού μπορώ να θέσει το επτά;

829
00:39:20,551 --> 00:39:21,050
Να παρει η ευχη.

830
00:39:21,050 --> 00:39:23,174
Πρέπει να πάμε εκεί, έτσι
Έχω να κάνω κάποια αντιγραφή.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Και τώρα τα επτά πηγαίνει εδώ.

833
00:39:28,480 --> 00:39:29,860
Τώρα μπορώ να προχωρήσουμε στο έξι.

834
00:39:29,860 --> 00:39:30,980
Τώρα είναι ακόμη περισσότερη δουλειά.

835
00:39:30,980 --> 00:39:32,570
>> Οκτώ πρέπει να πάτε εδώ.

836
00:39:32,570 --> 00:39:33,920
Επτά πρέπει να πάτε εδώ.

837
00:39:33,920 --> 00:39:35,450
Τώρα τα έξι μπορεί να πάει εδώ.

838
00:39:35,450 --> 00:39:37,950
Τώρα πιάσε το πέντε.

839
00:39:37,950 --> 00:39:40,560
Τώρα το οκτώ έχει να πάει
Εδώ, επτά πρέπει να πάτε εδώ,

840
00:39:40,560 --> 00:39:43,650
έξι πρέπει να πάει εδώ, και
τώρα το πέντε και επαναλάβετε.

841
00:39:43,650 --> 00:39:46,610
Και είμαι λίγο πολύ
μετακινώντας το συνεχώς.

842
00:39:46,610 --> 00:39:52,950
>> Έτσι, στο τέλος, αυτό algorithm-- εμείς θα
αποκαλούν εισαγωγή sort-- πραγματικότητα

843
00:39:52,950 --> 00:39:55,020
έχει πολλή δουλειά, πάρα πολύ.

844
00:39:55,020 --> 00:39:56,970
Είναι απλά διαφορετικό
το είδος της εργασίας από ό, τι του Ben.

845
00:39:56,970 --> 00:40:00,090
το έργο του Ben μου είχε πηγαίνει
εμπρός και πίσω όλη την ώρα,

846
00:40:00,090 --> 00:40:03,510
επιλέγοντας το αμέσως μικρότερο
στοιχείο ξανά και ξανά.

847
00:40:03,510 --> 00:40:06,660
Έτσι, ήταν αυτό το πολύ οπτική είδος της εργασίας.

848
00:40:06,660 --> 00:40:10,600
>> Αυτό το άλλο αλγόριθμο, η οποία εξακολουθεί να είναι
correct-- θα πάρει τη δουλειά done--

849
00:40:10,600 --> 00:40:12,800
αλλάζει μόνο το ποσό της εργασίας.

850
00:40:12,800 --> 00:40:15,420
Μοιάζει αρχικά είστε
εξοικονόμησης ενέργειας, επειδή είστε ακριβώς

851
00:40:15,420 --> 00:40:19,190
ασχολούνται με κάθε στοιχείο
μπροστά, χωρίς να σηκωθούν όλα

852
00:40:19,190 --> 00:40:20,930
ο τρόπος μέσα από τον κατάλογο, όπως ο Ben ήταν.

853
00:40:20,930 --> 00:40:25,300
Αλλά το πρόβλημα είναι, ειδικά σε αυτούς τους
τρελό περιπτώσεις όπου είναι όλα προς τα πίσω,

854
00:40:25,300 --> 00:40:27,830
είστε ακριβώς το είδος της
αναβάλλοντας τη σκληρή δουλειά

855
00:40:27,830 --> 00:40:30,360
μέχρι να έχετε για να διορθώσετε τα λάθη σας.

856
00:40:30,360 --> 00:40:33,919
>> Και έτσι, αν μπορείτε να φανταστείτε αυτό
οκτώ και επτά και έξι και πέντε

857
00:40:33,919 --> 00:40:36,710
και αργότερα τεσσάρων και τριών και δύο
κινείται το δρόμο τους μέσα από τη λίστα,

858
00:40:36,710 --> 00:40:39,060
έχουμε μόλις αλλάξει η
το είδος της εργασίας που κάνουμε.

859
00:40:39,060 --> 00:40:42,340
Αντί να γίνει αυτό κατά τη
αρχίζοντας της επανάληψης μου,

860
00:40:42,340 --> 00:40:45,250
Είμαι απλά το κάνουν κατά τη
τέλος κάθε επανάληψης.

861
00:40:45,250 --> 00:40:50,550
Έτσι αποδεικνύεται ότι αυτόν τον αλγόριθμο,
πάρα πολύ, γενικά ονομάζεται εισαγωγή είδους,

862
00:40:50,550 --> 00:40:52,190
Είναι επίσης της τάξης των n στο τετράγωνο.

863
00:40:52,190 --> 00:40:56,480
Είναι πραγματικά δεν είναι καλύτερη,
δεν είναι καλύτερη σε όλα.

864
00:40:56,480 --> 00:41:00,810
>> Ωστόσο, υπάρχει μια τρίτη προσέγγιση
Θα ήθελα να μας ενθαρρύνουν να εξετάσει,

865
00:41:00,810 --> 00:41:02,970
το οποίο είναι αυτό.

866
00:41:02,970 --> 00:41:07,850
Έτσι, ας υποθέσουμε λίστα μου, για την απλότητα
πάλι, είναι τέσσερα, ένα, τρία,

867
00:41:07,850 --> 00:41:11,080
two-- μόλις τέσσερις αριθμούς.

868
00:41:11,080 --> 00:41:13,300
Ben είχε καλή διαίσθηση,
καλή ανθρώπινη διαίσθηση

869
00:41:13,300 --> 00:41:16,340
πριν, με την οποία θα καθοριστεί το σύνολο
λίστα eventually-- είδος εισαγωγής.

870
00:41:16,340 --> 00:41:18,020
Θα μας έπεισε μαζί.

871
00:41:18,020 --> 00:41:22,530
Αλλά ας εξετάσουμε το
απλούστερος τρόπος για να διορθώσετε αυτή τη λίστα.

872
00:41:22,530 --> 00:41:24,110
>> Αυτή η λίστα δεν είναι ταξινομημένο.

873
00:41:24,110 --> 00:41:26,130
Γιατί;

874
00:41:26,130 --> 00:41:31,920
Στην αγγλική γλώσσα, να εξηγήσει γιατί
δεν είναι πραγματικά διευθετηθεί.

875
00:41:31,920 --> 00:41:33,400
Τι δεν σημαίνει να διευθετηθεί;

876
00:41:33,400 --> 00:41:34,220
>> Φοιτητής: Δεν είναι διαδοχική.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Malan: Δεν διαδοχική.

878
00:41:34,990 --> 00:41:35,822
Δώσε μου ένα παράδειγμα.

879
00:41:35,822 --> 00:41:37,180
>> Φοιτητής: Βάλτε τους σε σειρά.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Malan: OK.

881
00:41:37,440 --> 00:41:38,790
Δώστε μου ένα πιο συγκεκριμένο παράδειγμα.

882
00:41:38,790 --> 00:41:39,832
>> Φοιτητής: αύξουσα σειρά.

883
00:41:39,832 --> 00:41:41,206
DAVID Malan: Δεν αύξουσα σειρά.

884
00:41:41,206 --> 00:41:42,100
Να είναι πιο ακριβείς.

885
00:41:42,100 --> 00:41:45,190
Δεν ξέρω τι εννοείτε με αύξουσα σειρά.

886
00:41:45,190 --> 00:41:47,150
Τι τρέχει?

887
00:41:47,150 --> 00:41:49,930
>> ΜΑΘΗΤΗ: Το μικρότερο από το
αριθμών δεν είναι στην πρώτη θέση.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Malan: Μικρότερο αριθμό του
όχι στον πρώτο χώρο.

889
00:41:51,140 --> 00:41:52,120
Γίνε πιο συγκεκριμένος.

890
00:41:52,120 --> 00:41:55,000
Αρχίζω να πιάσει.

891
00:41:55,000 --> 00:41:59,470
Μετράμε, αλλά
τι είναι εκτός λειτουργίας εδώ;

892
00:41:59,470 --> 00:42:00,707
>> Φοιτητής: αριθμητική ακολουθία.

893
00:42:00,707 --> 00:42:02,040
DAVID Malan: αριθμητική ακολουθία.

894
00:42:02,040 --> 00:42:04,248
το είδος του καθενός της τήρησης
το here-- πολύ υψηλό επίπεδο.

895
00:42:04,248 --> 00:42:07,450
Απλά κυριολεκτικά να μου πει τι είναι
λάθος σαν ένα πέντε-year-old δύναμη.

896
00:42:07,450 --> 00:42:08,310
>> Φοιτητής: συν ένα.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Malan: Τι είναι αυτό;

898
00:42:08,750 --> 00:42:09,610
>> Φοιτητής: συν ένα.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Malan: Τι εννοείς συν ένα;

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Δώσε μου ένα διαφορετικό πέντε ετών.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Τι είναι λάθος, μαμά;

904
00:42:18,330 --> 00:42:19,940
Τι κάνει λάθος, ο μπαμπάς;

905
00:42:19,940 --> 00:42:22,808
Τι εννοείς αυτό δεν είναι ταξινομημένο;

906
00:42:22,808 --> 00:42:24,370
>> Φοιτητής: Δεν είναι το σωστό μέρος.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Malan: Τι είναι
όχι στο σωστό μέρος;

908
00:42:25,580 --> 00:42:26,174
>> ΦΟΙΤΗΤΗ: Four.

909
00:42:26,174 --> 00:42:27,090
DAVID Malan: Εντάξει, καλά.

910
00:42:27,090 --> 00:42:29,110
Έτσι, τέσσερις δεν είναι εκεί που πρέπει να είναι.

911
00:42:29,110 --> 00:42:30,590
Ειδικότερα, είναι αυτό το δικαίωμα;

912
00:42:30,590 --> 00:42:33,000
Τέσσερις και ένα, το πρώτο
δύο αριθμούς βλέπω.

913
00:42:33,000 --> 00:42:34,930
Είναι αυτό σωστό?

914
00:42:34,930 --> 00:42:36,427
Όχι, είναι εκτός λειτουργίας, έτσι δεν είναι;

915
00:42:36,427 --> 00:42:38,135
Στην πραγματικότητα, σκεφτείτε τώρα
για έναν υπολογιστή, πάρα πολύ.

916
00:42:38,135 --> 00:42:40,824
Μπορεί μόνο να δούμε ίσως ένα,
ίσως δύο πράγματα once--

917
00:42:40,824 --> 00:42:43,240
και στην πραγματικότητα μόνο ένα πράγμα
σε μια στιγμή, αλλά μπορεί τουλάχιστον

918
00:42:43,240 --> 00:42:45,790
δούμε ένα πράγμα, στη συνέχεια, το
επόμενο πράγμα ακριβώς δίπλα σε αυτό.

919
00:42:45,790 --> 00:42:47,380
>> Έτσι είναι αυτά για;

920
00:42:47,380 --> 00:42:48,032
Φυσικά και όχι.

921
00:42:48,032 --> 00:42:48,740
Έτσι, ξέρετε τι;

922
00:42:48,740 --> 00:42:51,020
Γιατί δεν παίρνουμε το μωρό
βήματα για τον καθορισμό αυτού του προβλήματος

923
00:42:51,020 --> 00:42:53,410
αντί να κάνει αυτά τα φανταχτερά
αλγόριθμοι όπως ο Ben, όπου

924
00:42:53,410 --> 00:42:56,440
αυτός είναι το είδος αυτό για τον καθορισμό από την
looping μέσα στη λίστα

925
00:42:56,440 --> 00:42:59,670
αντί να κάνει ό, τι έκανα, όπου
Θέλω μόνο είδος που ορίζεται ως πάμε;

926
00:42:59,670 --> 00:43:03,650
Ας κυριολεκτικά καταρρεύσει η
έννοια της order-- αριθμητική σειρά,

927
00:43:03,650 --> 00:43:06,990
ονομάσουμε ό, τι want--
σε αυτές τις κατά ζεύγη συγκρίσεις.

928
00:43:06,990 --> 00:43:07,590
>> Τέσσερις και ένα.

929
00:43:07,590 --> 00:43:09,970
Είναι αυτό η σωστή σειρά;

930
00:43:09,970 --> 00:43:11,310
Ας το διορθώσουμε.

931
00:43:11,310 --> 00:43:14,700
Ένα και τέσσερα, και στη συνέχεια
θα αντιγράψει ακριβώς αυτό.

932
00:43:14,700 --> 00:43:15,560
Εντάξει, καλά.

933
00:43:15,560 --> 00:43:17,022
Έχω σταθερό από ένα έως τέσσερα.

934
00:43:17,022 --> 00:43:18,320
Τρία και δύο;

935
00:43:18,320 --> 00:43:18,820
Όχι.

936
00:43:18,820 --> 00:43:21,690
Ας τα λόγια μου ταιριάζουν τα δάχτυλά μου.

937
00:43:21,690 --> 00:43:23,695
Τέσσερις και τρεις;

938
00:43:23,695 --> 00:43:27,930
>> Δεν είναι σε σειρά, έτσι Πάω
να κάνει ένα, τρία, τέσσερα, δύο.

939
00:43:27,930 --> 00:43:28,680
Εντάξει, καλά.

940
00:43:28,680 --> 00:43:32,310
Τώρα τεσσάρων και δύο;

941
00:43:32,310 --> 00:43:33,370
Πρέπει να το διορθώσετε αυτό, πάρα πολύ.

942
00:43:33,370 --> 00:43:36,700
Έτσι ένα, τρία, δύο, τέσσερα.

943
00:43:36,700 --> 00:43:39,820
Έτσι είναι ταξινομημένο;

944
00:43:39,820 --> 00:43:43,170
Όχι, αλλά είναι πιο κοντά να διευθετηθεί;

945
00:43:43,170 --> 00:43:48,930
>> Είναι, γιατί αυτή καθορίζεται
λάθος, είμαστε σταθερά αυτό το λάθος,

946
00:43:48,930 --> 00:43:50,370
και σταθερό αυτό το λάθος.

947
00:43:50,370 --> 00:43:52,420
Γι 'αυτό και σταθερό τρία λάθη αναμφισβήτητα.

948
00:43:52,420 --> 00:43:58,100
Ακόμα πραγματικά δεν φαίνονται ταξινομημένα αλλά
είναι αντικειμενικά πιο κοντά να διευθετηθεί

949
00:43:58,100 --> 00:44:00,080
γιατί έχουμε σταθερό ορισμένα από αυτά τα λάθη.

950
00:44:00,080 --> 00:44:02,047
>> Τώρα τι πρέπει να κάνω το επόμενο βήμα;

951
00:44:02,047 --> 00:44:03,630
Ι το είδος φτάσει στο τέλος της λίστας.

952
00:44:03,630 --> 00:44:05,680
Μου φάνηκε να έχουν σταθερές
όλα τα λάθη, αλλά όχι.

953
00:44:05,680 --> 00:44:08,510
Επειδή σε αυτή την περίπτωση, ορισμένοι αριθμοί
θα μπορούσε να διοχετεύεται μέχρι πιο κοντά

954
00:44:08,510 --> 00:44:10,410
σε άλλες αριθμών που
εξακολουθούν να είναι εκτός λειτουργίας.

955
00:44:10,410 --> 00:44:12,951
Έτσι, ας το κάνουμε και πάλι, και εγώ θα
απλά να το κάνει στη θέση του αυτή τη φορά.

956
00:44:12,951 --> 00:44:14,170
Ενός και τριών;

957
00:44:14,170 --> 00:44:14,720
Είναι εντάξει.

958
00:44:14,720 --> 00:44:16,070
Τρία και δύο;

959
00:44:16,070 --> 00:44:17,560
Φυσικά όχι, οπότε ας το αλλάξουμε αυτό.

960
00:44:17,560 --> 00:44:19,160
Έτσι δύο, τρία.

961
00:44:19,160 --> 00:44:21,340
Τρία και τέσσερα;

962
00:44:21,340 --> 00:44:24,370
Και τώρα ας είναι
ιδιαίτερα σχολαστικός εδώ.

963
00:44:24,370 --> 00:44:26,350
Είναι ταξινομημένο;

964
00:44:26,350 --> 00:44:29,280
Εσείς οι άνθρωποι ξέρουν ότι είναι ταξινομημένο.

965
00:44:29,280 --> 00:44:30,400
>> Θα πρέπει να προσπαθήσετε ξανά.

966
00:44:30,400 --> 00:44:31,900
Έτσι Ολίβια προτείνει προσπαθώ ξανά.

967
00:44:31,900 --> 00:44:32,530
Γιατί;

968
00:44:32,530 --> 00:44:35,810
Επειδή ένας υπολογιστής δεν έχει
η πολυτέλεια των ανθρώπινων ματιών μας

969
00:44:35,810 --> 00:44:38,080
μόλις ανακλώμενη back-- Εντάξει, είμαι γίνει.

970
00:44:38,080 --> 00:44:41,610
Πώς καθορίσει ο υπολογιστής
ότι ο κατάλογος είναι τώρα ταξινομημένο;

971
00:44:41,610 --> 00:44:44,590
Μηχανικά.

972
00:44:44,590 --> 00:44:47,650
>> Θα πρέπει να περάσουν από
για μια ακόμη φορά, και μόνο αν

973
00:44:47,650 --> 00:44:51,190
δεν κάνουν / να βρούμε τα λάθη μπορώ
στη συνέχεια να συνάψει με τον υπολογιστή, yep,

974
00:44:51,190 --> 00:44:51,980
είμαστε καλοί να πάτε.

975
00:44:51,980 --> 00:44:54,850
Έτσι, ένα και δύο, δύο και
τρία, τρία και τέσσερα.

976
00:44:54,850 --> 00:44:58,030
Τώρα μπορώ να πω οριστικά αυτό είναι
διαλογή, επειδή έκανα καμία αλλαγή.

977
00:44:58,030 --> 00:45:01,940
Τώρα θα ήταν ένα σφάλμα και μόνο
ανόητο αν, ο υπολογιστής,

978
00:45:01,940 --> 00:45:05,640
ζήτησε από τις ίδιες ερωτήσεις ξανά
περιμένουμε διαφορετικές απαντήσεις.

979
00:45:05,640 --> 00:45:07,110
δεν πρέπει να συμβεί.

980
00:45:07,110 --> 00:45:08,600
>> Και έτσι τώρα η λίστα είναι ταξινομημένο.

981
00:45:08,600 --> 00:45:12,630
Δυστυχώς, χρόνος λειτουργίας της
Ο αλγόριθμος αυτός είναι επίσης Ν τετράγωνο.

982
00:45:12,630 --> 00:45:13,130
Γιατί;

983
00:45:13,130 --> 00:45:19,520
Επειδή έχετε n αριθμούς, και το
χειρότερη περίπτωση θα πρέπει να κινηθούν οι αριθμοί n

984
00:45:19,520 --> 00:45:23,637
n φορές γιατί πρέπει να συνεχίσουμε
πίσω για να ελέγξει και ενδεχομένως να καθορίσει

985
00:45:23,637 --> 00:45:24,220
αυτοί οι αριθμοί.

986
00:45:24,220 --> 00:45:26,280
Και μπορούμε να κάνουμε μια πιο
τυπική ανάλυση, πάρα πολύ.

987
00:45:26,280 --> 00:45:29,530
>> Έτσι, όλα αυτά είναι για να πούμε ότι έχουμε λάβει
τρεις διαφορετικές προσεγγίσεις, μία

988
00:45:29,530 --> 00:45:32,210
από αυτούς αμέσως διαισθητική
από το ρόπαλο από τον Ben

989
00:45:32,210 --> 00:45:35,170
με προτεινόμενη εισαγωγή μου
Ταξινόμηση σε αυτό

990
00:45:35,170 --> 00:45:38,540
όπου μπορείτε είδους παραβλέπουμε
το δάσος για τα δέντρα αρχικά.

991
00:45:38,540 --> 00:45:41,760
Στη συνέχεια, όμως, αν κάνουμε ένα βήμα πίσω,
voila, έχουμε σταθερή την έννοια διαλογής.

992
00:45:41,760 --> 00:45:43,824
Έτσι, αυτό είναι, τολμώ να πω,
ένα χαμηλότερο επίπεδο ίσως

993
00:45:43,824 --> 00:45:45,740
από ό, τι μερικά από τα άλλα
αλγορίθμους, αλλά ας

994
00:45:45,740 --> 00:45:48,550
να δούμε αν δεν μπορούμε να απεικονίσει
αυτά μέσω αυτού.

995
00:45:48,550 --> 00:45:51,450
>> Έτσι, αυτό είναι μερικά ωραία
λογισμικό ότι κάποιος

996
00:45:51,450 --> 00:45:56,110
έγραψε χρησιμοποιώντας πολύχρωμα μπαρ που είναι
πρόκειται να κάνετε τα εξής για εμάς.

997
00:45:56,110 --> 00:45:57,736
Κάθε μία από αυτές τις ράβδους αντιπροσωπεύει έναν αριθμό.

998
00:45:57,736 --> 00:46:00,026
Ψηλότερος το μπαρ, το μεγαλύτερο
ο αριθμός, τόσο μικρότερη είναι η ράβδος,

999
00:46:00,026 --> 00:46:00,990
όσο μικρότερος είναι ο αριθμός.

1000
00:46:00,990 --> 00:46:05,880
Έτσι, στην ιδανική περίπτωση που θέλετε ένα ωραίο πυραμίδα
όπου ξεκινά μικρό και παίρνει μεγάλες,

1001
00:46:05,880 --> 00:46:08,330
και ότι θα σήμαινε ότι
αυτές οι μπάρες ταξινομημένο.

1002
00:46:08,330 --> 00:46:11,200
Έτσι, Πάω να πάει μπροστά και να επιλέξετε,
για παράδειγμα, ο αλγόριθμος του Ben

1003
00:46:11,200 --> 00:46:13,990
first-- είδος επιλογής.

1004
00:46:13,990 --> 00:46:16,220
>> Και παρατηρήστε τι κάνει.

1005
00:46:16,220 --> 00:46:18,670
Ο τρόπος με τον οποίο έχετε επιλέξει να
απεικονίσει αυτόν τον αλγόριθμο

1006
00:46:18,670 --> 00:46:22,090
είναι ότι, ακριβώς όπως ήμουν
περπατώντας μέσα από λίστα μου,

1007
00:46:22,090 --> 00:46:24,710
Αυτό το πρόγραμμα είναι το περπάτημα
μέσω λίστα των αριθμών,

1008
00:46:24,710 --> 00:46:28,160
τονίζοντας σε ροζ χρώμα κάθε
αριθμός που είναι κοιτάζοντας.

1009
00:46:28,160 --> 00:46:32,360
Και τι πρόκειται να συμβεί τώρα;

1010
00:46:32,360 --> 00:46:35,154
>> Ο μικρότερος αριθμός ότι
Ι ή Ben βρεθεί ξαφνικά

1011
00:46:35,154 --> 00:46:36,820
παίρνει κινήθηκε προς την αρχή της λίστας.

1012
00:46:36,820 --> 00:46:40,037
Και παρατηρήστε έκαναν έξωση
ο αριθμός που ήταν εκεί,

1013
00:46:40,037 --> 00:46:41,120
και ότι είναι απολύτως εντάξει.

1014
00:46:41,120 --> 00:46:42,600
Δεν είχα μπει σε αυτό το επίπεδο λεπτομέρειας.

1015
00:46:42,600 --> 00:46:44,308
Αλλά πρέπει να τεθεί
ότι ο αριθμός κάπου,

1016
00:46:44,308 --> 00:46:47,775
γι 'αυτό ακριβώς κινήθηκε προς το
ανοικτό σημείο που δημιουργήθηκε.

1017
00:46:47,775 --> 00:46:49,900
Έτσι, Πάω να επιταχυνθεί αυτή η
up, γιατί διαφορετικά

1018
00:46:49,900 --> 00:46:51,871
γίνεται πολύ κουραστικό γρήγορα.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animation speed-- εκεί πάμε.

1021
00:46:58,600 --> 00:47:01,850
Έτσι τώρα ίδια αρχή
Ήμουν εφαρμογή, αλλά θα

1022
00:47:01,850 --> 00:47:06,540
μπορεί να αρχίσει να αισθάνονται τον αλγόριθμο, που αν
θα είναι, ή να δείτε λίγο πιο ξεκάθαρα.

1023
00:47:06,540 --> 00:47:13,190
Και αυτός ο αλγόριθμος έχει ως αποτέλεσμα την
επιλέγοντας το επόμενο μικρότερο στοιχείο,

1024
00:47:13,190 --> 00:47:16,422
έτσι θα πάμε να αρχίσουν να
δείτε ράμπα μέχρι στα αριστερά.

1025
00:47:16,422 --> 00:47:19,130
Και σε κάθε επανάληψη, όπως
πρότεινε, το κάνει λίγο λιγότερη εργασία.

1026
00:47:19,130 --> 00:47:21,921
Δεν πρέπει να πάει σε όλη τη διαδρομή
πίσω στο αριστερό άκρο της λίστας,

1027
00:47:21,921 --> 00:47:23,900
γιατί ήδη
ξέρει αυτά είναι ταξινομημένο.

1028
00:47:23,900 --> 00:47:28,129
Γι 'αυτό το είδος του αισθάνεται σαν να είναι
επιτάχυνση, αν και κάθε βήμα είναι

1029
00:47:28,129 --> 00:47:29,420
λαμβάνοντας το ίδιο χρονικό διάστημα.

1030
00:47:29,420 --> 00:47:31,600
Υπάρχει μόνο λιγότερα βήματα που απομένουν.

1031
00:47:31,600 --> 00:47:35,240
Και τώρα μπορείτε είδος μπορεί να αισθάνεται ο
αλγόριθμο καθαρισμό στο τέλος της,

1032
00:47:35,240 --> 00:47:37,040
και μάλιστα τώρα είναι ταξινομημένο.

1033
00:47:37,040 --> 00:47:41,620
>> Έτσι, το είδος εισαγωγής είναι όλα γίνονται.

1034
00:47:41,620 --> 00:47:43,600
Θα πρέπει να επαν-τυχαίο τον πίνακα.

1035
00:47:43,600 --> 00:47:45,940
Και παρατηρήσετε μπορώ μόνο
κρατήσει την τυχαία αυτό,

1036
00:47:45,940 --> 00:47:50,630
και θα πάρετε μια προσέγγιση της
η ίδια προσέγγιση, το είδος εισαγωγής.

1037
00:47:50,630 --> 00:47:55,050
Επιτρέψτε μου να επιβραδύνει εδώ.

1038
00:47:55,050 --> 00:47:56,915
Ας ξεκινήσουμε ότι πάνω.

1039
00:47:56,915 --> 00:47:57,414
Στάση.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Ας παραλείψτε τέσσερις.

1042
00:48:02,410 --> 00:48:03,200
Εκεί πάμε.

1043
00:48:03,200 --> 00:48:04,190
Τυχαίο σειρά τους.

1044
00:48:04,190 --> 00:48:05,555
Και εδώ έχουμε go-- είδος εισαγωγής.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Παιχνίδι.

1047
00:48:12,800 --> 00:48:17,280
Παρατηρήστε ότι αυτό είναι που ασχολούνται με κάθε
στοιχείο συναντά αμέσως,

1048
00:48:17,280 --> 00:48:20,282
αλλά αν ανήκει σε
η λανθασμένη ανακοίνωση χώρα

1049
00:48:20,282 --> 00:48:21,740
όλες τις εργασίες που έχει να συμβεί.

1050
00:48:21,740 --> 00:48:24,700
Πρέπει να συνεχίσουμε τη μετατόπιση περισσότερα
και περισσότερα στοιχεία για να κάνει χώρο

1051
00:48:24,700 --> 00:48:27,340
για τη μία θέλουμε να τεθεί σε εφαρμογή.

1052
00:48:27,340 --> 00:48:30,740
>> Έτσι, είμαστε εστιάζοντας στην
αριστερό άκρο του μόνο τη λίστα.

1053
00:48:30,740 --> 00:48:34,460
Ανακοίνωση δεν έχουμε καν κοίταξε at-- μας
Δεν έχουν αναδείξει σε ροζ τίποτα

1054
00:48:34,460 --> 00:48:35,610
δεξιά.

1055
00:48:35,610 --> 00:48:38,180
Είμαστε ακριβώς που ασχολούνται με
τα προβλήματα όπως πάμε,

1056
00:48:38,180 --> 00:48:40,430
αλλά είμαστε δημιουργώντας πολλά
εργάζονται για τον εαυτό μας ακόμα.

1057
00:48:40,430 --> 00:48:44,410
Και έτσι αν θέλουμε να επιταχύνει τη διαδικασία
τώρα να πάνε στην ολοκλήρωση,

1058
00:48:44,410 --> 00:48:46,210
έχει μια διαφορετική αίσθηση σε αυτό όντως.

1059
00:48:46,210 --> 00:48:50,150
Είναι απλά με επίκεντρο το αριστερό άκρο, αλλά
κάνει λίγο περισσότερη δουλειά ως needed--

1060
00:48:50,150 --> 00:48:53,230
είδους εξομάλυνση πράγματα
πάνω, για τον καθορισμό πράγματα,

1061
00:48:53,230 --> 00:48:58,350
αλλά ασχολούνται τελικά με
κάθε στοιχείο, ένα κάθε φορά

1062
00:48:58,350 --> 00:49:07,740
μέχρι να φτάσουμε στο το-- καλά,
Όλοι γνωρίζουμε πώς αυτό πρόκειται να τελειώσει,

1063
00:49:07,740 --> 00:49:09,700
γι 'αυτό είναι λίγο απογοητευτικό ίσως.

1064
00:49:09,700 --> 00:49:12,830
>> Αλλά ο κατάλογος στον end--
spoiler-- πρόκειται να διευθετηθεί.

1065
00:49:12,830 --> 00:49:15,300
Έτσι, ας ρίξουμε μια ματιά σε ένα τελευταίο.

1066
00:49:15,300 --> 00:49:16,840
Δεν μπορούμε απλά να παραλείψετε τώρα.

1067
00:49:16,840 --> 00:49:18,000
Είμαστε σχεδόν εκεί.

1068
00:49:18,000 --> 00:49:19,980
Δύο για να πάει, το ένα για να πάει.

1069
00:49:19,980 --> 00:49:22,680
Και voila.

1070
00:49:22,680 --> 00:49:23,450
Έξοχος.

1071
00:49:23,450 --> 00:49:27,220
>> Έτσι τώρα ας κάνουμε μια τελευταία,
εκ νέου την τυχαία κατανομή με ταξινόμηση φυσαλίδας.

1072
00:49:27,220 --> 00:49:31,690
Και παρατηρήσετε εδώ, ειδικά αν μπορώ να επιβραδύνει
προς τα κάτω, αυτό τηρεί ορμώντας μέσα.

1073
00:49:31,690 --> 00:49:36,830
Αλλά παρατηρήσετε ότι κάνει ακριβώς ζεύγη
comparisons-- είδος τοπικές λύσεις.

1074
00:49:36,830 --> 00:49:39,050
Αλλά μόλις φτάσουμε
το τέλος του καταλόγου σε ροζ χρώμα,

1075
00:49:39,050 --> 00:49:40,690
τι θα πρέπει να συμβεί ξανά;

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ναι, πρόκειται να πρέπει να
ξεκινήσετε από την αρχή, γιατί μόνο

1078
00:49:46,830 --> 00:49:49,870
σταθερό ζεύγη λάθη.

1079
00:49:49,870 --> 00:49:53,120
Και αυτό θα μπορούσε να αποκαλύψει ακόμα άλλους.

1080
00:49:53,120 --> 00:49:58,950
Και έτσι αν έχετε να επιταχύνει τη διαδικασία, θα
δείτε ότι, όσο υποδηλώνει το όνομα,

1081
00:49:58,950 --> 00:50:01,870
το μικρότερο elements-- ή μάλλον,
τα μεγαλύτερα elements-- ξεκινώντας

1082
00:50:01,870 --> 00:50:03,740
να φούσκα μέχρι την κορυφή, αν θέλετε.

1083
00:50:03,740 --> 00:50:07,380
Και τα μικρότερα στοιχεία είναι
αρχίζουν να φούσκα κάτω προς τα αριστερά.

1084
00:50:07,380 --> 00:50:10,780
Και πράγματι, αυτό είναι το είδος της
το οπτικό αποτέλεσμα, καθώς και.

1085
00:50:10,780 --> 00:50:17,150
Και έτσι αυτό θα καταλήξει φινίρισμα
σε ένα πολύ παρόμοιο τρόπο, πάρα πολύ.

1086
00:50:17,150 --> 00:50:19,160
>> Δεν έχουμε να σταθώ
σε αυτό το συγκεκριμένο.

1087
00:50:19,160 --> 00:50:21,010
Επιτρέψτε μου να ανοίξει αυτό τώρα, πάρα πολύ.

1088
00:50:21,010 --> 00:50:24,040
Υπάρχουν μερικά άλλα αλγορίθμων ταξινόμησης
στον κόσμο, μερικά εκ των οποίων

1089
00:50:24,040 --> 00:50:25,580
Εδώ συλλαμβάνονται.

1090
00:50:25,580 --> 00:50:29,960
Και ειδικά για τους μαθητές που δεν είναι
απαραίτητα οπτική ή μαθηματικών,

1091
00:50:29,960 --> 00:50:31,930
όπως κάναμε πριν, μπορούμε
Επίσης, το κάνετε αυτό audially

1092
00:50:31,930 --> 00:50:34,210
αν έχουμε συνδέσει έναν ήχο με αυτό.

1093
00:50:34,210 --> 00:50:36,990
Και μόνο για διασκέδαση, εδώ είναι μια
Λίγα διαφορετικών αλγορίθμων,

1094
00:50:36,990 --> 00:50:40,950
και ένας από αυτούς, ιδίως είστε
Θα παρατηρήσετε ονομάζεται «συγχώνευση του είδους."

1095
00:50:40,950 --> 00:50:43,250
>> Είναι πραγματικά μια ριζικά
καλύτερο αλγόριθμο,

1096
00:50:43,250 --> 00:50:45,860
τέτοια ώστε ταξινόμηση με συγχώνευση, ένας από τους
αυτά που είστε έτοιμος να δείτε,

1097
00:50:45,860 --> 00:50:49,170
Δεν είναι σειρά των n τετράγωνο.

1098
00:50:49,170 --> 00:50:57,280
Είναι της τάξης του n φορές log της
n, η οποία είναι στην πραγματικότητα μικρότερο και έτσι

1099
00:50:57,280 --> 00:50:58,940
ταχύτερα από ό, τι τα άλλα τρία.

1100
00:50:58,940 --> 00:51:00,670
Και υπάρχει ένα ζευγάρι άλλα
ανόητα αυτά που θα δούμε.

1101
00:51:00,670 --> 00:51:01,933
>> Έτσι, εδώ πηγαίνουμε με κάποιο ήχο.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Αυτό είναι το είδος της εισαγωγής, οπότε και πάλι
είναι ακριβώς ασχολούνται με τα στοιχεία

1104
00:51:10,490 --> 00:51:13,420
όπως έρχονται.

1105
00:51:13,420 --> 00:51:17,180
Αυτό είναι το είδος φούσκα, έτσι είναι
θεωρώντας τα ζευγάρια σε έναν χρόνο.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Και πάλι, τα μεγαλύτερα στοιχεία
Οι εμφύσηση μέχρι την κορυφή.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Έπειτα επάνω είδος επιλογής.

1110
00:51:41,710 --> 00:51:45,420
Αυτό είναι ο αλγόριθμος του Ben, όπου
και πάλι αυτός είναι επιλογή επαναληπτικά

1111
00:51:45,420 --> 00:51:46,843
το επόμενο μικρότερο στοιχείο.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Και πάλι, τώρα μπορείτε πραγματικά να ακούω ότι
αυτό είναι την επιτάχυνση, αλλά μόνο στο βαθμό

1114
00:51:53,900 --> 00:51:58,230
όπως κάνει και λιγότερο
εργάζονται σε κάθε επανάληψη.

1115
00:51:58,230 --> 00:52:04,170
Αυτή είναι η πιο γρήγορη μία, ταξινόμηση με συγχώνευση,
η οποία είναι η διαλογή συστάδες των αριθμών

1116
00:52:04,170 --> 00:52:05,971
μαζί και στη συνέχεια ο συνδυασμός τους.

1117
00:52:05,971 --> 00:52:07,720
Έτσι look-- το αριστερό
μισό έχει ήδη διευθετηθεί.

1118
00:52:07,720 --> 00:52:14,165
>> Τώρα είναι η διαλογή το δεξί μισό, και
Τώρα πρόκειται να τα συνδυάσετε σε ένα.

1119
00:52:14,165 --> 00:52:19,160
Αυτό είναι κάτι που ονομάζεται "Gnome είδος."

1120
00:52:19,160 --> 00:52:23,460
Και μπορείτε να το είδος δούμε ότι
πρόκειται εμπρός και πίσω,

1121
00:52:23,460 --> 00:52:27,950
καθορισμό έργο λίγο εδώ και
εκεί πριν προχωρήσει σε νέα εργασία.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Και αυτό είναι όλο.

1124
00:52:33,692 --> 00:52:36,400
Υπάρχει ένα άλλο είδος, το οποίο είναι
πραγματικά μόνο για ακαδημαϊκούς σκοπούς,

1125
00:52:36,400 --> 00:52:40,980
που ονομάζεται «ηλίθιο είδος," η οποία λαμβάνει
τα δεδομένα σας, ταξινομεί τυχαία,

1126
00:52:40,980 --> 00:52:43,350
και στη συνέχεια ελέγχει αν είναι ταξινομημένο.

1127
00:52:43,350 --> 00:52:47,880
Και αν δεν είναι, εκ νέου ταξινομεί το
τυχαία, ελέγχει αν είναι ταξινομημένο,

1128
00:52:47,880 --> 00:52:49,440
και αν δεν επαναλαμβάνεται.

1129
00:52:49,440 --> 00:52:52,660
Και στη θεωρία, πιθανολογικά
αυτό θα ολοκληρωθεί,

1130
00:52:52,660 --> 00:52:54,140
αλλά μετά από αρκετά ένα κομμάτι του χρόνου.

1131
00:52:54,140 --> 00:52:56,930
Δεν είναι το πιο
αποδοτικών αλγορίθμων.

1132
00:52:56,930 --> 00:53:02,550
Έτσι, οποιεσδήποτε ερωτήσεις σχετικά με εκείνους
Ειδικότερα οι αλγόριθμοι ή τίποτα

1133
00:53:02,550 --> 00:53:04,720
που σχετίζονται εκεί, πάρα πολύ;

1134
00:53:04,720 --> 00:53:09,430
>> Λοιπόν, ας τώρα πειράζουν πέρα ​​ό, τι όλα
αυτές οι γραμμές είναι ότι έχω την κατάρτιση

1135
00:53:09,430 --> 00:53:15,090
και τι είμαι υποθέτοντας τον υπολογιστή
μπορεί να κάνει κάτω από την κουκούλα.

1136
00:53:15,090 --> 00:53:18,650
Θα έλεγα ότι όλα αυτά τα νούμερα
Κρατάω drawing-- που χρειάζονται για να

1137
00:53:18,650 --> 00:53:21,330
αποθηκευμένα κάπου στη μνήμη.

1138
00:53:21,330 --> 00:53:24,130
Θα απαλλαγούμε από αυτόν τον τύπο σήμερα, πάρα πολύ.

1139
00:53:24,130 --> 00:53:30,110
>> Έτσι, ένα κομμάτι της μνήμης σε ένα
computer-- έτσι RAM DIMM είναι

1140
00:53:30,110 --> 00:53:35,480
αυτό που έψαχναν για χθες, διπλή
inline μνήμη module-- μοιάζει με αυτό.

1141
00:53:35,480 --> 00:53:39,370
Και κάθε ένα από αυτά τα μικρά μαύρα τσιπ
είναι κάποια αριθμός των bytes, τυπικά.

1142
00:53:39,370 --> 00:53:44,380
Και τότε οι χρυσές καρφίτσες είναι σαν το
καλώδια που συνδέουν τον υπολογιστή,

1143
00:53:44,380 --> 00:53:47,521
και το πράσινο πλακέτα πυριτίου είναι μόνο
αυτό που κρατά τα πάντα μαζί.

1144
00:53:47,521 --> 00:53:48,770
Λοιπόν, τι σημαίνει αυτό πραγματικά;

1145
00:53:48,770 --> 00:53:53,180
Αν ήμουν είδος επιστήσει την ίδια εικόνα,
ας υποθέσουμε για απλότητα

1146
00:53:53,180 --> 00:53:55,280
ότι αυτή η DIMM, διπλή
inline μονάδα μνήμης,

1147
00:53:55,280 --> 00:54:00,530
είναι ένα gigabyte μνήμης RAM, ένα gigabyte
μνήμη, η οποία είναι πόσα bytes;

1148
00:54:00,530 --> 00:54:02,100
Ένα gigabyte είναι πόσα bytes;

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Περισσότερο από αυτό.

1151
00:54:06,030 --> 00:54:09,960
1124 είναι κιλό, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega είναι εκατομμύρια.

1153
00:54:11,730 --> 00:54:14,570
Giga είναι ένα δισεκατομμύριο.

1154
00:54:14,570 --> 00:54:15,070
>> Είμαι ξαπλωμένη;

1155
00:54:15,070 --> 00:54:16,670
Μπορούμε να διαβάσει ακόμα την ετικέτα;

1156
00:54:16,670 --> 00:54:19,920
Αυτό είναι στην πραγματικότητα 128
gigabytes, οπότε είναι περισσότερο.

1157
00:54:19,920 --> 00:54:22,130
Αλλά θα προσποιηθώ αυτό
Είναι απλά ένα gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Έτσι, αυτό σημαίνει ότι υπάρχει ένα δισεκατομμύριο
bytes της μνήμης στη διάθεσή μου

1159
00:54:25,640 --> 00:54:29,770
ή 8 δισεκατομμύρια bits, αλλά θα πάμε
να μιλήσει από την άποψη των bytes τώρα,

1160
00:54:29,770 --> 00:54:30,750
προχωρώντας μπροστά.

1161
00:54:30,750 --> 00:54:36,330
>> Έτσι τι αυτό σημαίνει ότι είναι αυτό είναι
ένα byte, αυτό είναι ένα άλλο byte,

1162
00:54:36,330 --> 00:54:38,680
αυτό είναι ένα άλλο byte,
και αν πραγματικά ήθελε

1163
00:54:38,680 --> 00:54:43,280
να είναι συγκεκριμένες θα έπρεπε να
συντάξει ένα δισεκατομμύριο μικρές πλατείες.

1164
00:54:43,280 --> 00:54:44,320
Αλλά τι σημαίνει αυτό;

1165
00:54:44,320 --> 00:54:46,420
Λοιπόν, επιτρέψτε μου να μεγεθύνετε
σε αυτή την εικόνα.

1166
00:54:46,420 --> 00:54:50,900
Αν έχω κάτι που φαίνεται
όπως αυτό τώρα, αυτό είναι τέσσερα bytes.

1167
00:54:50,900 --> 00:54:53,710
>> Και έτσι θα μπορούσα να βάλω τέσσερις αριθμούς εδώ.

1168
00:54:53,710 --> 00:54:54,990
Ένα δύο τρία τέσσερα.

1169
00:54:54,990 --> 00:55:00,170
Ή θα μπορούσα να βάλω τέσσερα γράμματα ή σύμβολα.

1170
00:55:00,170 --> 00:55:02,620
"Γεια σου!" θα μπορούσε να πάει εκεί,
επειδή καθένα από τα γράμματα,

1171
00:55:02,620 --> 00:55:04,370
συζητήσαμε νωρίτερα,
θα μπορούσαν να εκπροσωπούνται

1172
00:55:04,370 --> 00:55:06,650
με οκτώ bits ή ASCII ή ένα byte.

1173
00:55:06,650 --> 00:55:09,370
Έτσι με άλλα λόγια, μπορείς
βάλει 8000000000 πράγματα στο εσωτερικό

1174
00:55:09,370 --> 00:55:11,137
αυτού ένα ραβδί της μνήμης.

1175
00:55:11,137 --> 00:55:14,345
Τώρα τι σημαίνει αυτό για να βάλει τα πράγματα πίσω
στην πλάτη με πλάτη στη μνήμη σαν αυτό;

1176
00:55:14,345 --> 00:55:17,330
Αυτό είναι ό, τι έναν προγραμματιστή
θα αποκαλούσα μια «σειρά».

1177
00:55:17,330 --> 00:55:21,250
Σε ένα πρόγραμμα υπολογιστή, που δεν νομίζω
σχετικά με το υποκείμενο υλικό, per se.

1178
00:55:21,250 --> 00:55:24,427
Απλά σκεφτείτε τον εαυτό σας ως έχουν
πρόσβαση σε ένα σύνολο δισεκατομμύριο bytes,

1179
00:55:24,427 --> 00:55:26,010
και μπορείτε να ό, τι θέλετε με αυτό.

1180
00:55:26,010 --> 00:55:27,880
Αλλά για λόγους ευκολίας
είναι γενικά χρήσιμη

1181
00:55:27,880 --> 00:55:31,202
για να κρατήσει σωστά τη μνήμη σας
δίπλα στο άλλο όπως αυτό.

1182
00:55:31,202 --> 00:55:33,660
Έτσι, αν κάνετε ζουμ σε this--
επειδή είμαστε σίγουρα δεν πρόκειται

1183
00:55:33,660 --> 00:55:39,310
να συντάξει ένα δισεκατομμύριο λίγο τετράγωνα--
ας υποθέσουμε ότι αυτή η πλακέτα αντιπροσωπεύει

1184
00:55:39,310 --> 00:55:40,610
ότι το ραβδί μνήμης τώρα.

1185
00:55:40,610 --> 00:55:43,800
Και εγώ θα επιστήσω ακριβώς όσο μου
δείκτης καταλήγει δίνοντας μου εδώ.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Έτσι τώρα έχουμε ένα ραβδί
της μνήμης στην πλακέτα

1188
00:55:52,300 --> 00:55:56,400
ότι έχεις ένα, δύο, τρία, τέσσερα, πέντε,
έξι, ένα, δύο, τρία, τέσσερα, πέντε, έξι,

1189
00:55:56,400 --> 00:56:01,130
seven-- έτσι 42 bytes της
μνήμη επί του συνολικού οθόνη.

1190
00:56:01,130 --> 00:56:01,630
Ευχαριστώ.

1191
00:56:01,630 --> 00:56:02,838
Ναι, έκανε την αριθμητική μου σωστά.

1192
00:56:02,838 --> 00:56:05,120
Έτσι 42 bytes της μνήμης εδώ.

1193
00:56:05,120 --> 00:56:06,660
Λοιπόν, τι σημαίνει αυτό πραγματικά σημαίνει;

1194
00:56:06,660 --> 00:56:09,830
Λοιπόν, ένας προγραμματιστής ηλεκτρονικών υπολογιστών
θα ήταν στην πραγματικότητα σε γενικές γραμμές

1195
00:56:09,830 --> 00:56:12,450
σκέφτομαι αυτή τη μνήμη ως addressable.

1196
00:56:12,450 --> 00:56:16,630
Με άλλα λόγια, κάθε μία από αυτές
θέσεις στη μνήμη, στο υλικό,

1197
00:56:16,630 --> 00:56:18,030
έχει μια μοναδική διεύθυνση.

1198
00:56:18,030 --> 00:56:22,020
>> Δεν είναι τόσο περίπλοκο όπως ένα Brattle
Πλατεία, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Αντ 'αυτού, είναι απλά ένας αριθμός.

1200
00:56:23,830 --> 00:56:27,930
Αυτός είναι ο αριθμός byte μηδέν, αυτό είναι
ένα, αυτό είναι δύο, αυτό είναι τρεις,

1201
00:56:27,930 --> 00:56:30,327
και αυτό είναι 41.

1202
00:56:30,327 --> 00:56:30,910
Περίμενε ένα λεπτό.

1203
00:56:30,910 --> 00:56:32,510
Νόμιζα ότι είπα 42 πριν από λίγο.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Άρχισα καταμέτρηση στο μηδέν,
έτσι ώστε να είναι πραγματικά σωστή.

1206
00:56:37,772 --> 00:56:40,980
Τώρα δεν έχουμε να επιστήσει την πραγματικότητα
ως πλέγμα, και αν το σχεδιάσετε ως πλέγμα

1207
00:56:40,980 --> 00:56:43,520
Νομίζω ότι τα πράγματα στην πραγματικότητα
να πάρει λίγο παραπλανητικό.

1208
00:56:43,520 --> 00:56:46,650
Τι προγραμματιστής θα ήταν,
στο δικό του μυαλό,

1209
00:56:46,650 --> 00:56:50,310
γενικά σκεφτείτε αυτό
μνήμη είναι ακριβώς όπως μια ταινία,

1210
00:56:50,310 --> 00:56:53,340
σαν ένα κομμάτι κολλητική ταινία
που πηγαίνει ακριβώς και για πάντα

1211
00:56:53,340 --> 00:56:54,980
ή μέχρι να εξαντληθεί η μνήμη.

1212
00:56:54,980 --> 00:56:59,200
Έτσι, μια πιο συνηθισμένος τρόπος για να αντλήσει
και απλά σκεφτείτε τη μνήμη

1213
00:56:59,200 --> 00:57:03,710
θα ήταν ότι αυτό είναι το byte μηδέν, ένα,
δύο, τρία, και στη συνέχεια, τελεία, τελεία, τελεία.

1214
00:57:03,710 --> 00:57:07,650
Και έχετε 42 όπως bytes Συνολικά, ακόμη και
αν φυσικά αυτό μπορεί στην πραγματικότητα

1215
00:57:07,650 --> 00:57:09,480
είναι κάτι περισσότερο σαν αυτό.

1216
00:57:09,480 --> 00:57:12,850
>> Έτσι, αν τώρα σκεφτείτε σας
μνήμη όπως αυτό, ακριβώς όπως μια ταινία,

1217
00:57:12,850 --> 00:57:17,640
Αυτό είναι ό, τι ένας προγραμματιστής και πάλι
θα έθετε μια σειρά από μνήμης.

1218
00:57:17,640 --> 00:57:20,660
Και όταν θέλετε να αποθηκεύσετε πραγματικά
κάτι στη μνήμη ενός υπολογιστή,

1219
00:57:20,660 --> 00:57:23,290
μπορείτε γενικά να κάνουμε τα πράγματα κατάστημα
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Έτσι έχουμε μιλήσει σχετικά με τους αριθμούς.

1221
00:57:25,010 --> 00:57:30,880
Και όταν θέλησα να λύσει τα προβλήματα
όπως τέσσερα, ένα, τρία, δύο,

1222
00:57:30,880 --> 00:57:33,820
ακόμα κι αν ήμουν μόλις κατάρτιση
Μόνον οι αριθμοί τέσσερα, ένα, τρία,

1223
00:57:33,820 --> 00:57:39,490
δύο στο διοικητικό συμβούλιο, ο υπολογιστής θα
πραγματικά αυτή τη ρύθμιση στη μνήμη.

1224
00:57:39,490 --> 00:57:43,347
>> Και τι θα ήταν δίπλα στο
δύο στη μνήμη του υπολογιστή;

1225
00:57:43,347 --> 00:57:44,680
Λοιπόν, δεν υπάρχει καμία απάντηση σε αυτό.

1226
00:57:44,680 --> 00:57:45,770
Εμείς πραγματικά δεν ξέρω.

1227
00:57:45,770 --> 00:57:48,200
Και εφόσον η
υπολογιστή δεν το χρειάζεται,

1228
00:57:48,200 --> 00:57:51,440
δεν πρέπει να με νοιάζει τι είναι το επόμενο
με τους αριθμούς που κάνει τη φροντίδα για.

1229
00:57:51,440 --> 00:57:55,130
Και όταν είπα νωρίτερα ότι έναν υπολογιστή
να δείτε μόνο σε μια διεύθυνση σε μια στιγμή,

1230
00:57:55,130 --> 00:57:56,170
αυτό είναι το είδος της γιατί.

1231
00:57:56,170 --> 00:57:59,490
>> Δεν σε αντίθεση με ρεκόρ
player και μια κεφαλή ανάγνωσης

1232
00:57:59,490 --> 00:58:03,030
μόνο να είναι σε θέση να δούμε ένα ορισμένο
αυλάκι σε μια φυσική παλιό σχολείο-ρεκόρ

1233
00:58:03,030 --> 00:58:06,500
σε μια στιγμή, ομοίως
Μπορεί ένας υπολογιστής χάρη

1234
00:58:06,500 --> 00:58:09,810
σε CPU και της
Intel σύνολο εντολών,

1235
00:58:09,810 --> 00:58:12,480
μεταξύ των οποίων η διδασκαλία
διαβάζεται από τη μνήμη

1236
00:58:12,480 --> 00:58:15,590
ή να το αποθηκεύσετε σε memory-- ένα
υπολογιστής μπορεί να κοιτάμε μόνο

1237
00:58:15,590 --> 00:58:19,210
σε μια τοποθεσία με ένα time--
μερικές φορές ένα συνδυασμό αυτών,

1238
00:58:19,210 --> 00:58:21,770
αλλά πραγματικά μόνο ένα χώρο κάθε φορά.

1239
00:58:21,770 --> 00:58:24,770
Έτσι, όταν κάναμε
αυτές οι διάφορες αλγόριθμοι,

1240
00:58:24,770 --> 00:58:28,110
Δεν είμαι απλά γράφοντας σε ένα
vacuum-- τέσσερα, ένα, τρία, δύο.

1241
00:58:28,110 --> 00:58:30,849
Αυτοί οι αριθμοί στην πραγματικότητα ανήκουν
κάπου φυσική μνήμη.

1242
00:58:30,849 --> 00:58:32,890
Έτσι, υπάρχουν μικροσκοπικά
τρανζίστορ ή κάποιο είδος

1243
00:58:32,890 --> 00:58:35,840
των ηλεκτρονικών ειδών κάτω από το
κουκούλα αποθήκευση αυτών των αξιών.

1244
00:58:35,840 --> 00:58:40,460
>> Και συνολικά, πόσα bits είναι
που συμμετέχουν αυτή τη στιγμή, ακριβώς για να είναι σαφές;

1245
00:58:40,460 --> 00:58:45,580
Έτσι, αυτό είναι τέσσερα bytes, ή
τώρα είναι η συνολική 32 bits.

1246
00:58:45,580 --> 00:58:49,280
Έτσι, στην πραγματικότητα υπάρχουν 32 μηδενικά και
αυτά που συνθέτουν αυτά τα τέσσερα πράγματα.

1247
00:58:49,280 --> 00:58:52,070
Υπάρχει ακόμη περισσότερο εδώ, αλλά
και πάλι δεν με νοιάζει γι 'αυτό.

1248
00:58:52,070 --> 00:58:55,120
>> Έτσι τώρα, ας ζητήσει από άλλο
ερώτηση χρησιμοποιώντας τη μνήμη,

1249
00:58:55,120 --> 00:58:57,519
επειδή ότι στο τέλος
της ημέρας είναι στο διακύμανσης.

1250
00:58:57,519 --> 00:59:00,310
Δεν έχει σημασία τι θα μπορούσαμε να κάνουμε με
ο υπολογιστής, στο τέλος της ημέρας

1251
00:59:00,310 --> 00:59:02,560
το υλικό εξακολουθεί να είναι η
ίδιο κάτω από την κουκούλα.

1252
00:59:02,560 --> 00:59:04,670
Πώς θα αποθηκεύσετε μια λέξη εδώ;

1253
00:59:04,670 --> 00:59:09,710
Λοιπόν, μια λέξη σε έναν υπολογιστή, όπως
"Γεια σου!" θα αποθηκεύονται ακριβώς όπως αυτό.

1254
00:59:09,710 --> 00:59:12,300
Και αν θέλετε ένα μεγαλύτερο
λέξη, μπορείτε απλά

1255
00:59:12,300 --> 00:59:19,120
αντικαταστήσετε ότι και να πω κάτι
όπως "γεια" και το κατάστημα που εδώ.

1256
00:59:19,120 --> 00:59:23,930
>> Και έτσι εδώ, πάρα πολύ, αυτό contiguousness
είναι στην πραγματικότητα ένα πλεονέκτημα,

1257
00:59:23,930 --> 00:59:26,530
γιατί ένας υπολογιστής μπορεί απλά
διαβάζεται από δεξιά προς τα αριστερά.

1258
00:59:26,530 --> 00:59:28,680
Αλλά εδώ είναι μια ερώτηση.

1259
00:59:28,680 --> 00:59:33,480
Στο πλαίσιο αυτής της λέξης,
h-e-l-L-o, θαυμαστικό,

1260
00:59:33,480 --> 00:59:38,740
πώς θα μπορούσε ο υπολογιστής ξέρει όπου ο
λέξη αρχίζει και πού τελειώνει η λέξη;

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Στο πλαίσιο των αριθμών,
πώς ο υπολογιστής

1263
00:59:43,800 --> 00:59:48,396
ξέρω πόσο καιρό η ακολουθία του
αριθμοί είναι ή όπου αρχίζει;

1264
00:59:48,396 --> 00:59:50,270
Λοιπόν, αποδεικνύεται out--
και εμείς δεν θα πάει πάρα πολύ

1265
00:59:50,270 --> 00:59:54,970
σε αυτό το επίπεδο detail--
υπολογιστές κινηθούν τα πράγματα γύρω στη μνήμη

1266
00:59:54,970 --> 00:59:57,800
κυριολεκτικά μέσω των διευθύνσεων αυτών.

1267
00:59:57,800 --> 01:00:02,080
Έτσι, σε έναν υπολογιστή, αν είστε
γράφοντας κώδικα για να αποθηκεύσετε τα πράγματα

1268
01:00:02,080 --> 01:00:05,800
όπως λέξεις, τι είστε
πραγματικά κάνουν είναι να πληκτρολογείτε

1269
01:00:05,800 --> 01:00:11,320
εκφράσεις που θυμάμαι όταν σε
μνήμη του υπολογιστή αυτά τα λόγια είναι.

1270
01:00:11,320 --> 01:00:14,370
Έτσι, επιτρέψτε μου να κάνω μια πολύ,
πολύ απλό παράδειγμα.

1271
01:00:14,370 --> 01:00:18,260
>> Πάω να πάει μπροστά και να
ανοίξει ένα απλό πρόγραμμα κειμένου,

1272
01:00:18,260 --> 01:00:20,330
και Πάω να δημιουργήσουν
ένα αρχείο που ονομάζεται hello.c.

1273
01:00:20,330 --> 01:00:22,849
Οι περισσότερες από αυτές τις πληροφορίες που
Δεν θα μπω σε με μεγάλη λεπτομέρεια,

1274
01:00:22,849 --> 01:00:25,140
αλλά Πάω να γράψω ένα
προγράμματος σε εκείνη την ίδια γλώσσα,

1275
01:00:25,140 --> 01:00:31,140
C. Αυτό είναι πολύ πιο εκφοβιστικό,
Θα έλεγα, από το μηδέν,

1276
01:00:31,140 --> 01:00:32,490
αλλά είναι πολύ παρόμοιο με το πνεύμα.

1277
01:00:32,490 --> 01:00:34,364
Στην πραγματικότητα, αυτά τα σγουρά
braces-- μπορείτε να το είδος της

1278
01:00:34,364 --> 01:00:37,820
σκεφτείτε τι έκανα ακριβώς όπως αυτό.

1279
01:00:37,820 --> 01:00:39,240
>> Ας κάνουμε αυτό, στην πραγματικότητα.

1280
01:00:39,240 --> 01:00:45,100
Όταν κάνετε κλικ πράσινη σημαία,
κάνετε τα εξής.

1281
01:00:45,100 --> 01:00:50,210
Θέλω να εκτυπώσετε "γεια".

1282
01:00:50,210 --> 01:00:51,500
Έτσι, αυτό είναι τώρα ψευδοκώδικα.

1283
01:00:51,500 --> 01:00:53,000
Είμαι το είδος της θολώνοντας τις γραμμές.

1284
01:00:53,000 --> 01:00:56,750
Στην C, αυτή η γλώσσα που μιλώ
περίπου, αυτή η γραμμή εκτύπωσης γεια

1285
01:00:56,750 --> 01:01:01,940
στην πραγματικότητα γίνεται "printf» με
μερικές παρενθέσεις και μία άνω τελεία.

1286
01:01:01,940 --> 01:01:03,480
>> Αλλά είναι η ίδια ακριβώς ιδέα.

1287
01:01:03,480 --> 01:01:06,730
Και αυτό είναι πολύ φιλικό προς το χρήστη
"Όταν πατηθεί πράσινη σημαία" γίνεται

1288
01:01:06,730 --> 01:01:10,182
η πιο απόκρυφες "int main άκυρη."

1289
01:01:10,182 --> 01:01:12,890
Και αυτό πραγματικά δεν έχει καμία χαρτογράφηση,
έτσι είμαι απλώς πρόκειται να αγνοήσει αυτό.

1290
01:01:12,890 --> 01:01:17,210
Αλλά τα άγκιστρα είναι σαν το
καμπύλα κομμάτια του παζλ σαν αυτό.

1291
01:01:17,210 --> 01:01:18,700
>> Έτσι, μπορείτε να το είδος υποθέτω.

1292
01:01:18,700 --> 01:01:22,357
Ακόμα κι αν δεν έχετε προγραμματιστεί πριν,
τι κάνει αυτό το πρόγραμμα ίσως να κάνω;

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Πιθανώς εκτυπώνει γεια
με ένα θαυμαστικό.

1295
01:01:28,000 --> 01:01:29,150
>> Έτσι, ας προσπαθήσουμε αυτό.

1296
01:01:29,150 --> 01:01:30,800
Πάω να το αποθηκεύσετε.

1297
01:01:30,800 --> 01:01:34,000
Και αυτό είναι, και πάλι, ένα πολύ
παλιό σχολικό περιβάλλον.

1298
01:01:34,000 --> 01:01:35,420
Δεν μπορώ να πατήσω, δεν μπορώ να σύρετε.

1299
01:01:35,420 --> 01:01:36,910
Έχω να πληκτρολογήσετε εντολές.

1300
01:01:36,910 --> 01:01:41,320
Γι 'αυτό θέλω να τρέξει το πρόγραμμά μου, έτσι
Θα ήθελα να το κάνετε αυτό, όπως hello.c.

1301
01:01:41,320 --> 01:01:42,292
Αυτό είναι το αρχείο έτρεξα.

1302
01:01:42,292 --> 01:01:43,500
Αλλά περιμένετε, είμαι λείπει ένα βήμα.

1303
01:01:43,500 --> 01:01:46,470
Τι έκανε λέμε είναι απαραίτητη
βήμα για μια γλώσσα όπως η C;

1304
01:01:46,470 --> 01:01:49,470
Έχω μόνο γραπτή πηγή
κώδικα, αλλά τι πρέπει να κάνω;

1305
01:01:49,470 --> 01:01:50,670
Ναι, χρειάζομαι ένα compiler.

1306
01:01:50,670 --> 01:01:57,670
Έτσι, στο Mac μου εδώ, έχω ένα
πρόγραμμα που ονομάζεται GCC, GNU C compiler,

1307
01:01:57,670 --> 01:02:03,990
η οποία μου επιτρέπει να κάνω this-- στροφή
πηγαίο κώδικα μου σε, θα το ονομάσουμε,

1308
01:02:03,990 --> 01:02:04,930
κώδικα μηχανής.

1309
01:02:04,930 --> 01:02:10,180
>> Και μπορώ να δω ότι,
πάλι, ως εξής, αυτοί

1310
01:02:10,180 --> 01:02:14,090
είναι τα μηδενικά και μονάδες που μόλις
δημιουργήθηκε από τον πηγαίο κώδικα μου,

1311
01:02:14,090 --> 01:02:15,730
όλα τα μηδενικά και μονάδες.

1312
01:02:15,730 --> 01:02:17,770
Και αν θέλω να τρέξει
μου program-- συμβαίνει

1313
01:02:17,770 --> 01:02:23,010
να ονομάζεται a.out για
ιστορικές reasons-- "γεια".

1314
01:02:23,010 --> 01:02:24,070
Μπορώ να το εκτελέσετε ξανά.

1315
01:02:24,070 --> 01:02:25,690
Γεια γεια γεια.

1316
01:02:25,690 --> 01:02:27,430
Και φαίνεται να λειτουργεί.

1317
01:02:27,430 --> 01:02:31,000
>> Αλλά αυτό σημαίνει ότι κάπου στο μου
μνήμη του υπολογιστή είναι οι λέξεις

1318
01:02:31,000 --> 01:02:35,279
h-e-l-L-o, θαυμαστικό.

1319
01:02:35,279 --> 01:02:38,070
Και αποδεικνύεται, ακριβώς όπως ένα μέρος,
ό, τι ένας υπολογιστής θα συνήθως

1320
01:02:38,070 --> 01:02:40,550
το κάνουμε έτσι ώστε να ξέρει πού
τα πράγματα αρχίζουν και end-- είναι

1321
01:02:40,550 --> 01:02:42,460
πρόκειται να θέσει ένα ειδικό σύμβολο εδώ.

1322
01:02:42,460 --> 01:02:46,064
Και η σύμβαση είναι να τεθεί η
αριθμός μηδέν στο τέλος μιας λέξης

1323
01:02:46,064 --> 01:02:48,230
έτσι ώστε να γνωρίζετε πού
στην πραγματικότητα τελειώνει, έτσι ώστε να

1324
01:02:48,230 --> 01:02:52,750
δεν τηρούν την εκτύπωση όλο και περισσότερα
χαρακτήρες από ό, τι πραγματικά σκοπεύετε.

1325
01:02:52,750 --> 01:02:55,400
>> Αλλά το πακέτο εδώ, ακόμα και
αν και αυτό είναι αρκετά απόκρυφα,

1326
01:02:55,400 --> 01:02:58,140
είναι ότι είναι, τελικά,
σχετικά απλή.

1327
01:02:58,140 --> 01:03:04,550
Μπορείτε δόθηκε ένα είδος ταινίας, ένα κενό
χώρο στον οποίο μπορείτε να γράψετε γράμματα.

1328
01:03:04,550 --> 01:03:07,150
Εσείς απλά πρέπει να έχουν
ειδικό σύμβολο, όπως αυθαίρετα

1329
01:03:07,150 --> 01:03:10,316
ο αριθμός μηδέν, να θέσει στο τέλος του
τα λόγια σας, έτσι ώστε ο υπολογιστής ξέρει,

1330
01:03:10,316 --> 01:03:13,410
OH, εγώ πρέπει να σταματήσει την εκτύπωση μετά
Βλέπω το θαυμαστικό.

1331
01:03:13,410 --> 01:03:16,090
Επειδή το επόμενο πράγμα εκεί
είναι μια τιμή ASCII του μηδενός,

1332
01:03:16,090 --> 01:03:19,125
ή η μηδενική χαρακτήρα, όπως
κάποιος θα το ονομάσουμε.

1333
01:03:19,125 --> 01:03:21,500
Αλλά υπάρχει το είδος του προβλήματος
εδώ, και ας επανέλθει

1334
01:03:21,500 --> 01:03:23,320
σε αριθμούς για μια στιγμή.

1335
01:03:23,320 --> 01:03:28,720
Ας υποθέσουμε ότι κάνω, στην πραγματικότητα,
έχουν μια σειρά από αριθμούς,

1336
01:03:28,720 --> 01:03:30,730
και ας υποθέσουμε ότι το
πρόγραμμα γράφω είναι

1337
01:03:30,730 --> 01:03:34,680
όπως ένα βιβλίο βαθμό για έναν δάσκαλο
και μια τάξη δασκάλους.

1338
01:03:34,680 --> 01:03:38,720
Και αυτό το πρόγραμμα το άτομό του επιτρέπει
για να πληκτρολογήσετε στις βαθμολογίες των μαθητών τους

1339
01:03:38,720 --> 01:03:39,960
στο κουίζ.

1340
01:03:39,960 --> 01:03:43,750
Και ας υποθέσουμε ότι ο μαθητής παίρνει
100 στην πρώτη κουίζ τους, ίσως

1341
01:03:43,750 --> 01:03:49,920
σαν 80 στην επόμενη, τότε ένα
75, τότε 90 στον τέταρτο κουίζ.

1342
01:03:49,920 --> 01:03:54,150
>> Έτσι, σε αυτό το σημείο στην ιστορία,
η συστοιχία είναι του μεγέθους τέσσερα.

1343
01:03:54,150 --> 01:03:58,470
Δεν υπάρχει απολύτως περισσότερη μνήμη στο
υπολογιστή, αλλά η συστοιχία, να το πω έτσι,

1344
01:03:58,470 --> 01:04:00,350
έχει μέγεθος τέσσερα.

1345
01:04:00,350 --> 01:04:06,060
Ας υποθέσουμε τώρα ότι ο δάσκαλος θέλει
να ορίσετε ένα πέμπτο κουίζ στην τάξη.

1346
01:04:06,060 --> 01:04:08,510
Λοιπόν, ένα από τα πράγματα που
ή αυτή που θα πρέπει να κάνετε

1347
01:04:08,510 --> 01:04:10,650
είναι τώρα αποθηκεύουν πρόσθετη αξία εδώ.

1348
01:04:10,650 --> 01:04:15,490
Αλλά αν η σειρά έχει ο δάσκαλος
δημιουργήθηκε σε αυτό το πρόγραμμα είναι μεγέθους για,

1349
01:04:15,490 --> 01:04:22,440
ένα από το πρόβλημα με μία συστοιχία είναι ότι
μπορείτε όχι μόνο να συνεχίσουμε να προσθέτουμε στη μνήμη.

1350
01:04:22,440 --> 01:04:26,470
Γιατί ό, τι και αν ένα άλλο μέρος του
το πρόγραμμα έχει τη λέξη "Γεια σου" εκεί;

1351
01:04:26,470 --> 01:04:29,650
>> Με άλλα λόγια, η μνήμη μου μπορεί να είναι
χρησιμοποιηθεί για οτιδήποτε σε ένα πρόγραμμα.

1352
01:04:29,650 --> 01:04:33,250
Και αν εκ των προτέρων έχω πληκτρολογήσει, hey,
Θέλω να εισόδου τέσσερις βαθμολογίες κουίζ,

1353
01:04:33,250 --> 01:04:34,784
θα μπορούσε να πάει εδώ και εδώ.

1354
01:04:34,784 --> 01:04:37,700
Και αν ξαφνικά αλλάξει το μυαλό σας
αργότερα και να πω θέλω ένα πέμπτο κουίζ

1355
01:04:37,700 --> 01:04:40,872
σκορ, μπορείτε όχι μόνο να
βάζουμε οπουδήποτε θέλετε,

1356
01:04:40,872 --> 01:04:42,580
γιατί ό, τι και αν αυτό
μνήμη που χρησιμοποιείται

1357
01:04:42,580 --> 01:04:45,990
για κάτι else-- κάποιο άλλο πρόγραμμα
ή κάποιο άλλο χαρακτηριστικό του προγράμματος

1358
01:04:45,990 --> 01:04:46,910
ότι τρέχετε;

1359
01:04:46,910 --> 01:04:50,650
Έτσι θα πρέπει να σκεφτείτε εκ των προτέρων
πώς θέλετε να αποθηκεύσετε τα δεδομένα σας,

1360
01:04:50,650 --> 01:04:54,480
γιατί τώρα έχετε βαμμένα
τον εαυτό σας σε ένα ψηφιακό γωνία.

1361
01:04:54,480 --> 01:04:57,280
>> Έτσι, ένας δάσκαλος θα μπορούσε, αντί
λένε όταν γράφετε ένα πρόγραμμα

1362
01:04:57,280 --> 01:04:59,360
για την αποθήκευση του ή της
βαθμούς, ξέρετε τι;

1363
01:04:59,360 --> 01:05:04,180
Πάω να ζητήσει,
όταν γράφετε το πρόγραμμά μου,

1364
01:05:04,180 --> 01:05:12,070
ότι θέλω μηδέν, ένα, δύο, τρία,
τέσσερα, πέντε, έξι, οκτώ βαθμούς συνολικά.

1365
01:05:12,070 --> 01:05:15,320
Έτσι, ένα, δύο, τρία, τέσσερα,
πέντε, έξι, επτά, οκτώ.

1366
01:05:15,320 --> 01:05:18,612
Ο δάσκαλος μπορεί μόλις πάνω από διαθέσει
μνήμη κατά τη σύνταξη του προγράμματος του ή της

1367
01:05:18,612 --> 01:05:19,570
και να πω, ξέρετε τι;

1368
01:05:19,570 --> 01:05:22,236
Είμαι ποτέ δεν πρόκειται να εκχωρήσει περισσότερα
από οκτώ κουίζ σε ένα εξάμηνο.

1369
01:05:22,236 --> 01:05:23,130
Αυτό είναι απλά τρελό.

1370
01:05:23,130 --> 01:05:24,470
Ποτέ δεν θα διαθέσει αυτό.

1371
01:05:24,470 --> 01:05:28,270
Έτσι ώστε με αυτόν τον τρόπο αυτός ή αυτή έχει το
ευελιξία να σκοράρει κατάστημα σπουδαστών,

1372
01:05:28,270 --> 01:05:33,010
όπως 75, 90, και ίσως ένα επιπλέον όπου
ο μαθητής πήρε επιπλέον πίστωσης, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Αλλά αν ο δάσκαλος δεν
χρησιμοποιεί αυτές τις τρεις θέσεις,

1374
01:05:36,130 --> 01:05:38,860
υπάρχει ένα έξυπνο πακέτο εδώ.

1375
01:05:38,860 --> 01:05:41,410
Αυτός ή αυτή είναι απλώς σπατάλη χώρου.

1376
01:05:41,410 --> 01:05:44,790
Έτσι με άλλα λόγια, υπάρχει αυτό το
κοινή δίλημμα στον προγραμματισμό

1377
01:05:44,790 --> 01:05:48,241
όπου μπορείτε είτε να διαθέσουν
ακριβώς όπως το μέγεθος της μνήμης, όπως θέλετε,

1378
01:05:48,241 --> 01:05:51,490
η άνω πλευρά του οποίου είναι ότι είστε σούπερ
efficient-- δεν είσαι σπάταλη

1379
01:05:51,490 --> 01:05:54,640
σε all-- αλλά το μειονέκτημα της οποίας
είναι ό, τι εάν αλλάξετε το μυαλό σας, όταν

1380
01:05:54,640 --> 01:05:58,780
χρησιμοποιώντας το πρόγραμμα που θέλετε να αποθηκεύσετε
περισσότερα δεδομένα από ό, τι προβλεπόταν αρχικά.

1381
01:05:58,780 --> 01:06:03,030
>> Έτσι ίσως η λύση είναι, τότε,
γράψει τα προγράμματα σας με τέτοιο τρόπο

1382
01:06:03,030 --> 01:06:05,605
ότι χρησιμοποιούν περισσότερη μνήμη
ό, τι πραγματικά χρειάζονται.

1383
01:06:05,605 --> 01:06:07,730
Αυτός ο τρόπος εσείς δεν πρόκειται
για να τρέξει σε αυτό το πρόβλημα,

1384
01:06:07,730 --> 01:06:09,730
αλλά είστε είναι σπάταλη.

1385
01:06:09,730 --> 01:06:12,960
Και η περισσότερη μνήμη πρόγραμμά σας χρησιμοποιεί,
όπως συζητήσαμε χθες, το λιγότερο

1386
01:06:12,960 --> 01:06:15,410
μνήμη που είναι διαθέσιμη
για άλλα προγράμματα,

1387
01:06:15,410 --> 01:06:18,790
τόσο πιο γρήγορα ο υπολογιστής σας μπορεί να επιβραδύνει
προς τα κάτω, λόγω της εικονικής μνήμης.

1388
01:06:18,790 --> 01:06:22,670
Και έτσι η ιδανική λύση θα μπορούσε να είναι αυτό;

1389
01:06:22,670 --> 01:06:24,610
>> Υπό-κατανομή φαίνεται κακό.

1390
01:06:24,610 --> 01:06:27,030
Πάνω-την κατανομή φαίνεται κακό.

1391
01:06:27,030 --> 01:06:31,120
Λοιπόν, τι θα μπορούσε να είναι η καλύτερη λύση;

1392
01:06:31,120 --> 01:06:32,390
Ανακατανομής.

1393
01:06:32,390 --> 01:06:33,590
Να είναι πιο δυναμική.

1394
01:06:33,590 --> 01:06:37,520
Μην πιέζετε τον εαυτό σας να επιλέξετε ένα
εκ των προτέρων, στην αρχή, ό, τι θέλετε.

1395
01:06:37,520 --> 01:06:41,370
Και σίγουρα δεν υπερ-κατανομή,
μήπως είναι σπάταλη.

1396
01:06:41,370 --> 01:06:45,770
>> Και έτσι για να επιτευχθεί ο στόχος αυτός, εμείς
πρέπει να ρίξει αυτή τη δομή δεδομένων,

1397
01:06:45,770 --> 01:06:48,100
να το πω έτσι, μακριά.

1398
01:06:48,100 --> 01:06:51,080
Και έτσι ό, τι ένας προγραμματιστής
θα χρησιμοποιούν συνήθως

1399
01:06:51,080 --> 01:06:55,940
είναι κάτι που δεν είναι ένα που ονομάζεται
array αλλά μια συνδεδεμένη λίστα.

1400
01:06:55,940 --> 01:07:00,860
Με άλλα λόγια, αυτός ή αυτή θα
αρχίζουν να σκέφτονται τη μνήμη τους

1401
01:07:00,860 --> 01:07:05,280
ως είδος ενός σχήματος ώστε να
να σχεδιάσετε με τον ακόλουθο τρόπο.

1402
01:07:05,280 --> 01:07:08,520
Αν θέλω να αποθηκεύσετε έναν αριθμό στη
ένα program-- έτσι είναι Σεπτέμβριος,

1403
01:07:08,520 --> 01:07:12,600
Έχω δώσει στους μαθητές μου ένα κουίζ? θέλω
για να αποθηκεύσετε το πρώτο κουίζ των μαθητών,

1404
01:07:12,600 --> 01:07:16,220
και πήραν 100 και στο εξής it--
είμαι πρόκειται να ζητήσει από τον υπολογιστή μου,

1405
01:07:16,220 --> 01:07:19,540
μέσω του προγράμματος έχω
γραπτή, για ένα κομμάτι της μνήμης.

1406
01:07:19,540 --> 01:07:22,570
Και Πάω να αποθηκεύσετε το
αριθμό 100 σε αυτό, και αυτό είναι όλο.

1407
01:07:22,570 --> 01:07:24,820
>> Στη συνέχεια, λίγες εβδομάδες αργότερα
όταν παίρνω το δεύτερο κουίζ μου,

1408
01:07:24,820 --> 01:07:27,890
και ήρθε η ώρα για να πληκτρολογήσετε
σε αυτό το 90%, Πάω

1409
01:07:27,890 --> 01:07:32,129
να ζητήσει από τον υπολογιστή, hey, ηλεκτρονικών υπολογιστών,
μπορώ να έχω ένα άλλο κομμάτι της μνήμης;

1410
01:07:32,129 --> 01:07:34,170
Είναι πρόκειται να μου δώσει αυτό
άδειο κομμάτι της μνήμης.

1411
01:07:34,170 --> 01:07:39,370
Πάω να θέσει σε αριθμό 90,
αλλά στο πρόγραμμα μου με κάποιο τρόπο ή other--

1412
01:07:39,370 --> 01:07:42,100
και δεν θα ανησυχείτε για
η σύνταξη για this-- χρειάζομαι

1413
01:07:42,100 --> 01:07:44,430
με κάποιο τρόπο να συνδέετε αυτά τα πράγματα μαζί.

1414
01:07:44,430 --> 01:07:47,430
Και εγώ θα τους αλυσίδα μαζί με
αυτό που μοιάζει με ένα βέλος εδώ.

1415
01:07:47,430 --> 01:07:50,050
>> Το τρίτο κουίζ που έρχεται,
Πάω να πω, hey, ηλεκτρονικών υπολογιστών,

1416
01:07:50,050 --> 01:07:51,680
να μου δώσει ένα άλλο κομμάτι της μνήμης.

1417
01:07:51,680 --> 01:07:54,660
Και Πάω να βάλει κάτω
ό, τι ήταν, όπως 75,

1418
01:07:54,660 --> 01:07:56,920
και έχω να την αλυσίδα αυτή
μαζί τώρα με κάποιο τρόπο.

1419
01:07:56,920 --> 01:08:00,290
Τέταρτη κουίζ έρχεται, και ίσως
ότι είναι προς το τέλος του εξαμήνου.

1420
01:08:00,290 --> 01:08:03,140
Και από αυτό το πρόγραμμα μου σημείο
θα μπορούσε να είναι με τη χρήση της μνήμης

1421
01:08:03,140 --> 01:08:05,540
σε όλη τη χώρα, σε όλο σωματικά.

1422
01:08:05,540 --> 01:08:08,170
Και έτσι απλά για πλάκα, είμαι
πρόκειται να συντάξει αυτό το εμπρός

1423
01:08:08,170 --> 01:08:11,260
quiz-- ξεχάσω ό, τι ήταν? εγώ
ότι ίσως ένα 80 ή something--

1424
01:08:11,260 --> 01:08:12,500
τρόπο εδώ.

1425
01:08:12,500 --> 01:08:15,920
>> Αλλά αυτό είναι εντάξει, επειδή εικονογραφικά
Πάω να επιστήσει αυτή τη γραμμή.

1426
01:08:15,920 --> 01:08:19,063
Με άλλα λόγια, στην πραγματικότητα,
στο υλικό του υπολογιστή σας,

1427
01:08:19,063 --> 01:08:20,979
το πρώτο αποτέλεσμα θα μπορούσε
καταλήγουν εδώ γιατί είναι

1428
01:08:20,979 --> 01:08:22,529
ακριβώς στην αρχή του εξαμήνου.

1429
01:08:22,529 --> 01:08:25,810
Η επόμενη θα μπορούσε κανείς να καταλήγουν εδώ
επειδή ένα κομμάτι του χρόνου έχει περάσει

1430
01:08:25,810 --> 01:08:27,210
και το πρόγραμμα συνεχίζει να τρέχει.

1431
01:08:27,210 --> 01:08:30,060
Η επόμενη βαθμολογία, η οποία ήταν
ένα 75, θα μπορούσε να είναι εδώ.

1432
01:08:30,060 --> 01:08:33,420
Και η τελευταία σκορ θα μπορούσε να είναι
ένας 80, που είναι εδώ.

1433
01:08:33,420 --> 01:08:38,729
>> Έτσι, στην πραγματικότητα, σωματικά, αυτό θα μπορούσε να είναι
τι μνήμη του υπολογιστή σας μοιάζει.

1434
01:08:38,729 --> 01:08:41,569
Αλλά αυτό δεν είναι ένα χρήσιμο ψυχική
παράδειγμα για έναν προγραμματιστή υπολογιστών.

1435
01:08:41,569 --> 01:08:44,649
Γιατί πρέπει να σας νοιάζει, όπου η
Heck τα δεδομένα σας είναι να καταλήξουμε;

1436
01:08:44,649 --> 01:08:46,200
Απλά θέλετε να αποθηκεύσετε τα δεδομένα.

1437
01:08:46,200 --> 01:08:49,390
>> Αυτό είναι κάτι σαν τη συζήτησή μας
νωρίτερα από την κατάρτιση του κύβου.

1438
01:08:49,390 --> 01:08:52,200
Γιατί σε νοιάζει εσένα τι
η γωνία είναι του κύβου

1439
01:08:52,200 --> 01:08:53,740
και πώς θα πρέπει να στραφούν για να βγάλουμε;

1440
01:08:53,740 --> 01:08:54,950
Μπορείτε απλά θέλουν έναν κύβο.

1441
01:08:54,950 --> 01:08:57,359
Ομοίως εδώ,
απλά θέλουν να βιβλίου βαθμού.

1442
01:08:57,359 --> 01:08:59,559
Απλά θέλετε να σκεφτείτε
αυτό ως μια λίστα των αριθμών.

1443
01:08:59,559 --> 01:09:01,350
Ποιος νοιάζεται πώς είναι
υλοποιηθεί σε hardware;

1444
01:09:01,350 --> 01:09:05,180
>> Έτσι τώρα η αφαίρεση
Είναι αυτή η εικόνα εδώ.

1445
01:09:05,180 --> 01:09:07,580
Αυτή είναι μια λίστα που συνδέεται, όπως
ένας προγραμματιστής θα το ονομάσουμε,

1446
01:09:07,580 --> 01:09:10,640
εφόσον έχετε ένα
κατάλογος, προφανώς των αριθμών.

1447
01:09:10,640 --> 01:09:14,990
Αλλά αυτό είναι που συνδέονται εικονογραφικά
μέσω αυτών των βελών,

1448
01:09:14,990 --> 01:09:18,510
και όλα αυτά τα βέλη are-- κάτω από
η κουκούλα, αν είστε περίεργοι,

1449
01:09:18,510 --> 01:09:23,210
Υπενθυμίζουμε ότι το φυσικό υλικό μας έχει
διευθύνσεις μηδέν, ένα, δύο, τρία, τέσσερα.

1450
01:09:23,210 --> 01:09:28,465
Όλα αυτά τα βέλη είναι είναι σαν ένα χάρτη
ή οδηγίες, που αν 90 is-- τώρα

1451
01:09:28,465 --> 01:09:29,090
Πήρα να μετρήσει.

1452
01:09:29,090 --> 01:09:31,750
>> Μηδέν, ένα, δύο, τρία,
τέσσερα, πέντε, έξι, επτά.

1453
01:09:31,750 --> 01:09:35,640
Μοιάζει με το 90 είναι σε
Αριθμός διεύθυνση μνήμης επτά.

1454
01:09:35,640 --> 01:09:38,460
Όλα αυτά τα βέλη είναι είναι
σαν ένα μικρό κομμάτι χαρτί

1455
01:09:38,460 --> 01:09:42,439
ότι είναι να δίνει οδηγίες για το
πρόγραμμα που λέει ακολουθούν αυτόν τον χάρτη

1456
01:09:42,439 --> 01:09:43,880
για να φτάσουμε στην θέση επτά.

1457
01:09:43,880 --> 01:09:46,680
Και εκεί θα βρείτε το
δεύτερο βαθμολογία κουίζ μαθητή.

1458
01:09:46,680 --> 01:09:52,100
Εν τω μεταξύ, η 75-- αν συνεχιστεί αυτό,
αυτό είναι επτά, οκτώ, εννέα, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Αυτό το άλλο βέλος αντιπροσωπεύει μόλις το
ένας χάρτης στη θέση μνήμης 15.

1461
01:09:59,080 --> 01:10:02,550
Αλλά και πάλι, ο προγραμματιστής κάνει γενικά
Δεν νοιάζονται για αυτό το επίπεδο λεπτομέρειας.

1462
01:10:02,550 --> 01:10:05,530
Και στις περισσότερες κάθε προγραμματισμό
γλώσσας σήμερα, ο προγραμματιστής

1463
01:10:05,530 --> 01:10:10,490
Δεν θα γνωρίζουν καν από πού στη μνήμη
οι αριθμοί αυτοί στην πραγματικότητα είναι.

1464
01:10:10,490 --> 01:10:14,830
Όλα τα αυτός ή αυτή έχει να νοιάζονται για είναι
ότι είναι κατά κάποιο τρόπο συνδέονται μεταξύ τους

1465
01:10:14,830 --> 01:10:18,390
σε μια δομή δεδομένων όπως αυτό.

1466
01:10:18,390 --> 01:10:21,580
>> Αλλά τελικά δεν
να πάρει πάρα πολύ τεχνική.

1467
01:10:21,580 --> 01:10:27,430
Αλλά ακριβώς επειδή μπορούμε ίσως
την πολυτέλεια να κάνουμε αυτήν τη συζήτηση εδώ,

1468
01:10:27,430 --> 01:10:33,630
ας υποθέσουμε ότι έχουμε επανεξετάσουμε
Αυτό το θέμα εδώ μιας συστοιχίας.

1469
01:10:33,630 --> 01:10:35,780
Ας δούμε αν λυπούμαστε πρόκειται εδώ.

1470
01:10:35,780 --> 01:10:42,950
Αυτό είναι 100, 90, 75, και 80.

1471
01:10:42,950 --> 01:10:44,980
>> Επιτρέψτε μου να κάνω για λίγο αυτόν τον ισχυρισμό.

1472
01:10:44,980 --> 01:10:48,980
Αυτή είναι μια συστοιχία, και πάλι, ο
εξέχον χαρακτηριστικό μιας συστοιχίας

1473
01:10:48,980 --> 01:10:52,400
είναι ότι όλα τα δεδομένα σας είναι πίσω για να
πλάτη με πλάτη στο memory-- κυριολεκτικά

1474
01:10:52,400 --> 01:10:56,830
ένα byte ή ίσως τέσσερα bytes,
μερικά σταθερό αριθμό των bytes μακριά.

1475
01:10:56,830 --> 01:11:00,710
Σε μια συνδεδεμένη λίστα, η οποία θα μπορούσε να αντλήσει
όπως αυτό, κάτω από την κουκούλα που

1476
01:11:00,710 --> 01:11:02,000
ξέρει πού ότι τα πράγματα είναι;

1477
01:11:02,000 --> 01:11:03,630
Δεν χρειάζεται καν να ρέει σαν αυτό.

1478
01:11:03,630 --> 01:11:06,050
Μερικά από τα στοιχεία θα μπορούσαν να είναι
πίσω προς τα αριστερά μέχρι εκεί.

1479
01:11:06,050 --> 01:11:07,530
Δεν ξέρω καν.

1480
01:11:07,530 --> 01:11:15,430
>> Και έτσι με μια σειρά, έχετε ένα
χαρακτηριστικό γνωστό ως τυχαίας προσπέλασης.

1481
01:11:15,430 --> 01:11:20,570
Και τι σημαίνει τυχαίας προσπέλασης είναι
ότι ο υπολογιστής μπορεί να πηδήξει αμέσως

1482
01:11:20,570 --> 01:11:22,730
σε οποιαδήποτε θέση σε μια σειρά.

1483
01:11:22,730 --> 01:11:23,580
Γιατί;

1484
01:11:23,580 --> 01:11:26,000
Επειδή ο υπολογιστής ξέρει
ότι η πρώτη θέση είναι

1485
01:11:26,000 --> 01:11:29,540
μηδέν, ένα, δύο και τρία.

1486
01:11:29,540 --> 01:11:33,890
>> Και έτσι, αν θέλετε να πάτε από
Αυτό το στοιχείο στο επόμενο στοιχείο,

1487
01:11:33,890 --> 01:11:36,099
μπορείτε κυριολεκτικά, στο
το μυαλό του υπολογιστή, απλά προσθέστε ένα.

1488
01:11:36,099 --> 01:11:39,140
Αν θέλετε να πάτε στο τρίτο στοιχείο,
απλά προσθέστε ένα-- επόμενο στοιχείο, απλά

1489
01:11:39,140 --> 01:11:40,290
προσθέσετε μία.

1490
01:11:40,290 --> 01:11:42,980
Ωστόσο, σε αυτή την έκδοση
της ιστορίας, ας υποθέσουμε

1491
01:11:42,980 --> 01:11:46,080
ο υπολογιστής αυτή τη στιγμή ψάχνει
στο ή ασχολούνται με τον αριθμό 100.

1492
01:11:46,080 --> 01:11:49,770
Πώς μπορείτε να φτάσετε στο επόμενο
βαθμό στο βιβλίο βαθμό;

1493
01:11:49,770 --> 01:11:52,560
>> Θα πρέπει να λάβει επτά
στάδια, η οποία είναι αυθαίρετη.

1494
01:11:52,560 --> 01:11:58,120
Για να φτάσετε στο επόμενο, θα πρέπει να
να λάβει άλλα οκτώ βήματα για να φτάσετε στο 15.

1495
01:11:58,120 --> 01:12:02,250
Με άλλα λόγια, δεν είναι ένα
σταθερό διάκενο μεταξύ των αριθμών,

1496
01:12:02,250 --> 01:12:04,857
και γι 'αυτό ακριβώς χρειάζεται η
υπολογιστή περισσότερο χρόνο είναι το σημείο.

1497
01:12:04,857 --> 01:12:06,940
Ο υπολογιστής πρέπει να ψάξει
μέσω της μνήμης, προκειμένου

1498
01:12:06,940 --> 01:12:08,990
για να βρείτε αυτό που ψάχνετε.

1499
01:12:08,990 --> 01:12:14,260
>> Έτσι, ενώ μια σειρά τείνει να είναι μια
structure-- γρήγορα τα δεδομένα, γιατί

1500
01:12:14,260 --> 01:12:17,610
μπορεί κυριολεκτικά να κάνει απλή αριθμητική
και να πάρετε όπου θέλετε με την προσθήκη ενός,

1501
01:12:17,610 --> 01:12:21,300
για instance-- μια συνδεδεμένη λίστα,
θα θυσιάσει αυτό το χαρακτηριστικό.

1502
01:12:21,300 --> 01:12:24,020
Δεν μπορείς απλά να πάει από την πρώτη
για τη δεύτερη στην τρίτη στην τέταρτη θέση.

1503
01:12:24,020 --> 01:12:25,240
Θα πρέπει να ακολουθήσετε το χάρτη.

1504
01:12:25,240 --> 01:12:28,160
Θα πρέπει να λάβει περισσότερα μέτρα
για να πάρει σε αυτές τις αξίες, οι οποίες

1505
01:12:28,160 --> 01:12:30,230
φαίνεται να είναι η προσθήκη ενός κόστους.

1506
01:12:30,230 --> 01:12:35,910
Έτσι είμαστε πληρώνουν ένα τίμημα, αλλά αυτό που ήταν
το χαρακτηριστικό ότι Dan αναζητούσε εδώ;

1507
01:12:35,910 --> 01:12:38,110
Τι κάνει μια συνδεδεμένη λίστα
προφανώς θα μας επιτρέψουν να κάνουμε,

1508
01:12:38,110 --> 01:12:40,240
το οποίο ήταν η προέλευση της
Αυτή η συγκεκριμένη ιστορία;

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Ακριβώς.

1511
01:12:43,830 --> 01:12:46,220
Μια δυναμική μέγεθος σε αυτό.

1512
01:12:46,220 --> 01:12:48,040
Μπορούμε να προσθέσουμε σε αυτή τη λίστα.

1513
01:12:48,040 --> 01:12:51,430
Μπορούμε να συρρικνωθεί ακόμη τη λίστα, έτσι
ότι είμαστε μόνο χρησιμοποιώντας ως πολύ μνήμη

1514
01:12:51,430 --> 01:12:55,560
όπως έχουμε πραγματικά θέλουν και έτσι
είμαστε ποτέ υπερβολική κατανομή.

1515
01:12:55,560 --> 01:12:58,470
>> Τώρα, ακριβώς για να είναι πραγματικά nit-επιλεκτικοί,
υπάρχει ένα κρυφό κόστος.

1516
01:12:58,470 --> 01:13:01,980
Έτσι δεν θα πρέπει απλά επιτρέψτε μου να πείσω
σας ότι αυτό είναι ένα σημαντικό δίλημμα.

1517
01:13:01,980 --> 01:13:04,190
Υπάρχει ένα άλλο κρυφό κόστος εδώ.

1518
01:13:04,190 --> 01:13:06,550
Το όφελος, να είναι σαφής,
είναι ότι έχουμε δυναμισμό.

1519
01:13:06,550 --> 01:13:10,359
Αν θέλω ένα άλλο στοιχείο, μπορώ μόνο
συντάξει και να το βάλετε έναν αριθμό εκεί.

1520
01:13:10,359 --> 01:13:12,150
Και τότε μπορώ να το συνδέσετε
με μια εικόνα εδώ,

1521
01:13:12,150 --> 01:13:14,970
ενώ εδώ, και πάλι, αν έχω
ζωγράφισε τον εαυτό μου σε μια γωνία,

1522
01:13:14,970 --> 01:13:19,410
αν κάτι άλλο είναι ήδη χρησιμοποιώντας
η μνήμη εδώ, είμαι από την τύχη.

1523
01:13:19,410 --> 01:13:21,700
Έχω ζωγράφισε τον εαυτό μου στη γωνία.

1524
01:13:21,700 --> 01:13:24,390
>> Αλλά τι είναι το κρυφό
το κόστος σε αυτή την εικόνα;

1525
01:13:24,390 --> 01:13:27,690
Δεν είναι μόνο το ποσό
του χρόνου που χρειάζεται

1526
01:13:27,690 --> 01:13:29,870
για να πάει από εδώ εδώ,
η οποία είναι επτά βήματα, στη συνέχεια,

1527
01:13:29,870 --> 01:13:32,820
οκτώ βήματα, που είναι περισσότερα από ένα.

1528
01:13:32,820 --> 01:13:34,830
Τι είναι άλλο κρυφό κόστος;

1529
01:13:34,830 --> 01:13:35,440
Όχι μόνο χρόνο.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Πρόσθετες πληροφορίες
αναγκαίο για την επίτευξη αυτή την εικόνα.

1532
01:13:49,940 --> 01:13:53,210
>> Ναι, αυτό χάρτη, αυτά τα μικρά κομμάτια
χαρτί, όπως έχω κρατήσει τους περιγράφει ως.

1533
01:13:53,210 --> 01:13:55,650
Αυτά arrows-- αυτά δεν είναι δωρεάν.

1534
01:13:55,650 --> 01:13:57,660
Μια computer-- ξέρετε
ό, τι ένας υπολογιστής έχει.

1535
01:13:57,660 --> 01:13:58,790
Έχει μηδενικά και μονάδες.

1536
01:13:58,790 --> 01:14:03,170
Αν θέλετε να αντιπροσωπεύουν ένα βέλος ή ένα
χάρτης ή ένας αριθμός, θα πρέπει να έχετε κάποια μνήμη.

1537
01:14:03,170 --> 01:14:05,950
Έτσι, από την άλλη τιμή που
πληρώσουν για μια συνδεδεμένη λίστα,

1538
01:14:05,950 --> 01:14:09,070
ένα κοινό επιστήμη των υπολογιστών
των πόρων, είναι επίσης χώρο.

1539
01:14:09,070 --> 01:14:11,710
>> Και πράγματι έτσι, τόσο συχνά,
μεταξύ των tradeoffs

1540
01:14:11,710 --> 01:14:15,580
στο σχεδιασμό της μηχανικής λογισμικού
συστημάτων είναι ο χρόνος και space--

1541
01:14:15,580 --> 01:14:18,596
είναι δύο από τα συστατικά σας, δύο
από τα πιο δαπανηρά συστατικά σας.

1542
01:14:18,596 --> 01:14:21,220
Αυτό μου κοστίζει περισσότερο χρόνο
γιατί έχω να ακολουθήσουν αυτό το χάρτη,

1543
01:14:21,220 --> 01:14:25,730
αλλά είναι επίσης κοστίζει μένα περισσότερο χώρο
γιατί έχω να κρατήσει αυτό το χάρτη γύρω.

1544
01:14:25,730 --> 01:14:28,730
Έτσι, η ελπίδα, όπως έχουμε το είδος της
συζήτησαν πάνω χθες και σήμερα,

1545
01:14:28,730 --> 01:14:31,720
είναι ότι τα οφέλη
θα υπερκαλύπτουν το κόστος.

1546
01:14:31,720 --> 01:14:33,870
>> Αλλά δεν υπάρχει καμία προφανής λύση εδώ.

1547
01:14:33,870 --> 01:14:35,870
Ίσως είναι better--
a la γρήγορη και βρώμικη,

1548
01:14:35,870 --> 01:14:38,660
όπως Kareem προτεινόμενη earlier--
να ρίξει τη μνήμη στο πρόβλημα.

1549
01:14:38,660 --> 01:14:42,520
Απλά αγοράζουν περισσότερη μνήμη, σκέφτονται λιγότερο
σκληρά για την επίλυση του προβλήματος,

1550
01:14:42,520 --> 01:14:44,595
και να το λύσει με έναν ευκολότερο τρόπο.

1551
01:14:44,595 --> 01:14:46,720
Και πράγματι νωρίτερα, όταν
μιλήσαμε για ανταλλαγές,

1552
01:14:46,720 --> 01:14:49,190
δεν ήταν κόπηκε με
ο υπολογιστής και το χρόνο.

1553
01:14:49,190 --> 01:14:51,810
Ήταν η ώρα του έργου, η οποία
είναι ένα ακόμη πόρο.

1554
01:14:51,810 --> 01:14:54,829
>> Έτσι και πάλι, είναι αυτό πράξη εξισορρόπησης
προσπαθείτε να αποφασίσετε ποια από αυτά τα πράγματα

1555
01:14:54,829 --> 01:14:55,870
είστε πρόθυμοι να περάσετε;

1556
01:14:55,870 --> 01:14:57,380
Ποιο είναι το λιγότερο ακριβό;

1557
01:14:57,380 --> 01:15:01,040
Η οποία αποδίδει τα καλύτερα αποτελέσματα;

1558
01:15:01,040 --> 01:15:01,540
Ναι;

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Πράγματι.

1561
01:15:12,580 --> 01:15:15,970
Σε αυτή την περίπτωση, αν είστε
που αντιπροσωπεύουν αριθμούς στο maps--

1562
01:15:15,970 --> 01:15:18,820
αυτές ονομάζονται σε πολλές γλώσσες
«Δείκτες» ή «διευθύνσεις» -

1563
01:15:18,820 --> 01:15:20,390
είναι διπλάσιο από το χώρο.

1564
01:15:20,390 --> 01:15:24,390
Αυτό δεν χρειάζεται να είναι τόσο κακή όσο διπλά αν
τώρα είμαστε ακριβώς την αποθήκευση αριθμών.

1565
01:15:24,390 --> 01:15:27,410
Ας υποθέσουμε ότι είχαμε την αποθήκευση
φακέλους των ασθενών σε hospital--

1566
01:15:27,410 --> 01:15:30,870
έτσι ώστε ονόματα του Pierson, αριθμούς τηλεφώνου,
αριθμούς κοινωνικής ασφάλισης, ο γιατρός

1567
01:15:30,870 --> 01:15:31,540
ιστορία.

1568
01:15:31,540 --> 01:15:34,160
Αυτό το πλαίσιο θα μπορούσε να είναι πολύ,
πολύ μεγαλύτερη, οπότε

1569
01:15:34,160 --> 01:15:38,000
ένα μικροσκοπικό μικρό δείκτη, η διεύθυνση της
η επόμενη element-- δεν είναι μια μεγάλη υπόθεση.

1570
01:15:38,000 --> 01:15:40,620
Είναι ένα τέτοιο περιθώριο
το κόστος αυτό δεν έχει σημασία.

1571
01:15:40,620 --> 01:15:43,210
Αλλά σε αυτή την περίπτωση, ναι, είναι ο διπλασιασμός.

1572
01:15:43,210 --> 01:15:45,290
Καλή ερώτηση.

1573
01:15:45,290 --> 01:15:47,900
>> Ας μιλήσουμε για το χρόνο μια
λίγο πιο συγκεκριμένα.

1574
01:15:47,900 --> 01:15:50,380
Τι είναι ο χρόνος εκτέλεσης
από την αναζήτηση αυτή τη λίστα;

1575
01:15:50,380 --> 01:15:53,640
Ας υποθέσουμε Ήθελα να αναζητήσετε
μέσω όλων των τάξεων των μαθητών,

1576
01:15:53,640 --> 01:15:55,980
και υπάρχει n βαθμούς
σε αυτή τη δομή δεδομένων.

1577
01:15:55,980 --> 01:15:58,830
Εδώ, επίσης, μπορούμε να δανειστούμε
το λεξιλόγιο του νωρίτερα.

1578
01:15:58,830 --> 01:16:00,890
Αυτή είναι μια γραμμική δομή δεδομένων.

1579
01:16:00,890 --> 01:16:04,570
>> Big O Ν είναι ό, τι απαιτείται για να
στο τέλος αυτής της δομής δεδομένων,

1580
01:16:04,570 --> 01:16:08,410
whereas-- και δεν έχουμε δει
Αυτό before-- μια σειρά που δίνει

1581
01:16:08,410 --> 01:16:13,555
αυτό που ονομάζεται σταθερά χρόνου, πράγμα που σημαίνει
ένα βήμα ή δύο βήματα ή 10 steps--

1582
01:16:13,555 --> 01:16:14,180
Δεν πειράζει.

1583
01:16:14,180 --> 01:16:15,440
Είναι ένα σταθερό αριθμό.

1584
01:16:15,440 --> 01:16:17,440
Δεν έχει τίποτε να κάνει με την
το μέγεθος της συστοιχίας.

1585
01:16:17,440 --> 01:16:20,130
Και ο λόγος γι 'αυτό,
πάλι, είναι τυχαίας προσπέλασης.

1586
01:16:20,130 --> 01:16:23,180
Ο υπολογιστής μπορεί απλά αμέσως
μεταβείτε σε άλλη θέση,

1587
01:16:23,180 --> 01:16:27,770
επειδή είναι όλοι το ίδιο
απόσταση από οτιδήποτε άλλο.

1588
01:16:27,770 --> 01:16:29,112
Δεν υπάρχει καμία σκέψη που εμπλέκονται.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Εντάξει.

1591
01:16:32,400 --> 01:16:39,230
Έτσι, αν μπορώ, επιτρέψτε μου να προσπαθήσω να
ζωγραφίσει δύο τελικές εικόνες.

1592
01:16:39,230 --> 01:16:42,830
Ένα πολύ κοινό ένα γνωστό ως πίνακα κατακερματισμού.

1593
01:16:42,830 --> 01:16:51,120
Έτσι για να παρακινήσει τη συζήτηση αυτή,
επιτρέψτε μου να σκεφτεί για το πώς να το κάνουμε αυτό.

1594
01:16:51,120 --> 01:16:52,610
>> Πώς, λοιπόν, γι 'αυτό;

1595
01:16:52,610 --> 01:16:55,160
Ας υποθέσουμε ότι το πρόβλημα
θέλουμε να λύσουμε τώρα

1596
01:16:55,160 --> 01:16:58,360
εφαρμόζει σε dictionary--
έτσι, ένα σωρό των αγγλικών λέξεων

1597
01:16:58,360 --> 01:16:59,330
ή οτιδήποτε.

1598
01:16:59,330 --> 01:17:02,724
Και ο στόχος είναι να είναι σε θέση να απαντήσει
ερωτήσεις της μορφής είναι αυτή η λέξη;

1599
01:17:02,724 --> 01:17:04,640
Έτσι θέλετε να εφαρμόσουν
ένα ορθογράφο, απλά

1600
01:17:04,640 --> 01:17:07,220
σαν μια φυσική λεξικό
ότι μπορείτε να δείτε τα πράγματα μέσα.

1601
01:17:07,220 --> 01:17:10,490
Ας υποθέσουμε ότι επρόκειτο να το κάνουμε αυτό με μια σειρά.

1602
01:17:10,490 --> 01:17:12,590
Θα μπορούσα να το κάνουμε αυτό.

1603
01:17:12,590 --> 01:17:20,756
>> Και ας υποθέσουμε ότι οι λέξεις είναι μήλο
και μπανάνα και πεπόνι.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Και δεν μπορώ να σκεφτώ φρούτα
που ξεκινούν με d, έτσι είμαστε απλά

1606
01:17:26,465 --> 01:17:27,590
πρόκειται να έχει τρία φρούτα.

1607
01:17:27,590 --> 01:17:31,510
Έτσι, αυτό είναι μια σειρά, και είμαστε
αποθήκευση όλων αυτών των λέξεων

1608
01:17:31,510 --> 01:17:34,200
σε αυτό το λεξικό ως πίνακας.

1609
01:17:34,200 --> 01:17:39,350
Το ερώτημα, λοιπόν, είναι πώς αλλιώς
θα μπορούσε να αποθηκεύσει αυτές τις πληροφορίες;

1610
01:17:39,350 --> 01:17:43,160
>> Λοιπόν, είμαι το είδος της εξαπάτησης εδώ, επειδή
καθένα από αυτά τα γράμματα της λέξης

1611
01:17:43,160 --> 01:17:44,490
Είναι πραγματικά ένα άτομο byte.

1612
01:17:44,490 --> 01:17:46,740
Έτσι, αν πραγματικά ήθελε να είναι
nit-επιλεκτικοί, θα ήθελα πραγματικά

1613
01:17:46,740 --> 01:17:49,600
να διαιρώντας αυτό επάνω σε πολλά
μικρότερα κομμάτια της μνήμης,

1614
01:17:49,600 --> 01:17:51,289
και θα μπορούσαμε να κάνουμε ακριβώς αυτό.

1615
01:17:51,289 --> 01:17:53,580
Αλλά θα πάμε να τρέχει σε
το ίδιο πρόβλημα όπως και πριν.

1616
01:17:53,580 --> 01:17:56,674
Τι θα συμβεί αν, όπως Merriam Webster ή Οξφόρδης
κάνει κάθε year-- προσθέτουν λέξεις

1617
01:17:56,674 --> 01:17:59,340
στην dictionary-- δεν το κάνουμε
θέλουν απαραιτήτως να ζωγραφίσει τον εαυτό μας

1618
01:17:59,340 --> 01:18:00,780
σε μια γωνία με μια σειρά;

1619
01:18:00,780 --> 01:18:05,710
>> Έτσι, αντ 'αυτού, ίσως μια πιο έξυπνη προσέγγιση
είναι να τεθεί το μήλο στο δικό κόμβο ή το κουτί της,

1620
01:18:05,710 --> 01:18:11,190
όπως θα λέγαμε, μπανάνα, και
τότε εδώ έχουμε το πεπόνι.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Και εγχόρδων εμείς αυτά τα πράγματα μαζί.

1623
01:18:16,790 --> 01:18:19,980
Έτσι, αυτό είναι ο πίνακας, και
αυτή είναι η συνδεδεμένη λίστα.

1624
01:18:19,980 --> 01:18:23,300
Εάν δεν μπορείτε να εντελώς δείτε, απλά
λέει "σειρά", και αυτό λέει "λίστα".

1625
01:18:23,300 --> 01:18:25,780
>> Έτσι έχουμε την ίδια
ακριβής ζητήματα όπως πριν,

1626
01:18:25,780 --> 01:18:28,600
σύμφωνα με την οποία έχουμε τώρα
δυναμισμό στην συνδεδεμένη λίστα μας.

1627
01:18:28,600 --> 01:18:31,090
Αλλά έχουμε μια αρκετά αργή λεξικό.

1628
01:18:31,090 --> 01:18:32,870
Ας υποθέσουμε ότι θέλετε να αναζητήσετε μια λέξη.

1629
01:18:32,870 --> 01:18:35,430
Θα μπορούσε να μου πάρει μεγάλο O του n
βήματα, γιατί η λέξη θα μπορούσε

1630
01:18:35,430 --> 01:18:37,840
είναι σε όλη τη διαδρομή στο τέλος της
η λίστα, όπως και το πεπόνι.

1631
01:18:37,840 --> 01:18:40,600
Και αποδεικνύεται ότι
στον προγραμματισμό, το είδος

1632
01:18:40,600 --> 01:18:42,700
το Άγιο Δισκοπότηρο των δεδομένων
δομές, είναι κάτι

1633
01:18:42,700 --> 01:18:46,620
ότι δίνει σταθερή
χρόνου, όπως μια σειρά

1634
01:18:46,620 --> 01:18:50,870
αλλά ότι εξακολουθεί να σας δίνει δυναμισμό.

1635
01:18:50,870 --> 01:18:52,940
>> Έτσι, μπορούμε να έχουμε το καλύτερο και των δύο κόσμων;

1636
01:18:52,940 --> 01:18:55,570
Και πράγματι, υπάρχει κάτι
ονομάζεται ο πίνακας κατακερματισμού

1637
01:18:55,570 --> 01:18:59,320
που σας επιτρέπει να κάνετε ακριβώς
ότι, έστω και κατά προσέγγιση.

1638
01:18:59,320 --> 01:19:03,140
Ένας πίνακας hash είναι ένα φανταχτερό
δομή δεδομένων που θα

1639
01:19:03,140 --> 01:19:06,340
μπορεί να σκεφτεί ως
συνδυασμός ενός array--

1640
01:19:06,340 --> 01:19:12,390
και πάω να το συντάξει
όπως this-- και συνδεδεμένες λίστες

1641
01:19:12,390 --> 01:19:17,310
ότι εγώ θα επιστήσω σαν αυτό εδώ.

1642
01:19:17,310 --> 01:19:19,760
>> Και ο τρόπος που αυτό το πράγμα
έργα είναι η εξής.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Εάν αυτό now-- hash table--
είναι η τρίτη δομή δεδομένων μου,

1645
01:19:29,540 --> 01:19:32,590
και θέλω να αποθηκεύσετε
λέξεις σε αυτό, εγώ δεν κάνω

1646
01:19:32,590 --> 01:19:35,440
θέλετε να αποθηκεύσετε μόνο όλα τα
λέξεις πλάτη με πλάτη με πλάτη με πλάτη.

1647
01:19:35,440 --> 01:19:37,430
Θέλω να αξιοποιήσουν κάποια
κομμάτι των πληροφοριών

1648
01:19:37,430 --> 01:19:40,330
για τις λέξεις που θα σας αφήσει
Θέλω να το πάρει, όπου είναι πιο γρήγορο.

1649
01:19:40,330 --> 01:19:43,666
>> Έτσι, δίνεται το μήλο λέξεις
και μπανάνα και πεπόνι,

1650
01:19:43,666 --> 01:19:45,040
Έχω σκόπιμα επέλεξε αυτές τις λέξεις.

1651
01:19:45,040 --> 01:19:45,340
Γιατί;

1652
01:19:45,340 --> 01:19:47,631
Ποιο είναι το είδος της θεμελιωδώς
διαφορετικά για τα τρία;

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Ποιο είναι το προφανές;

1655
01:19:51,484 --> 01:19:52,900
Αρχίζουν με διαφορετικά γράμματα.

1656
01:19:52,900 --> 01:19:53,900
>> Έτσι, ξέρετε τι;

1657
01:19:53,900 --> 01:19:57,120
Αντί να βάλει όλα τα λόγια μου
το ίδιο κουβά, να το πω έτσι,

1658
01:19:57,120 --> 01:20:00,390
όπως σε μια μεγάλη λίστα, γιατί να μην το κάνουμε
Θα προσπαθήσουμε τουλάχιστον μια βελτιστοποίηση

1659
01:20:00,390 --> 01:20:04,180
και να κάνουν λίστες μου 1/26 εφ.

1660
01:20:04,180 --> 01:20:07,440
Ένα συναρπαστικό βελτιστοποίησης
θα μπορούσε να είναι γιατί δεν το κάνουν

1661
01:20:07,440 --> 01:20:10,650
I-- κατά την εισαγωγή μιας λέξης
σε αυτή τη δομή δεδομένων,

1662
01:20:10,650 --> 01:20:14,300
στη μνήμη του υπολογιστή, γιατί
Δεν μπορώ να θέσει όλες τις λέξεις «ένα» εδώ,

1663
01:20:14,300 --> 01:20:17,270
όλες οι «β» λόγια εδώ,
και όλα τα «c» λέξεις εδώ;

1664
01:20:17,270 --> 01:20:24,610
Έτσι, αυτό καταλήγει βάζοντας ένα μήλο
Εδώ, μπανάνα εδώ, πεπόνι εδώ,

1665
01:20:24,610 --> 01:20:25,730
και ούτω καθεξής.

1666
01:20:25,730 --> 01:20:31,700
>> Και εάν έχω μια πρόσθετη
λέξη like-- τι άλλο;

1667
01:20:31,700 --> 01:20:36,640
Μήλο, μπανάνα, αχλάδι.

1668
01:20:36,640 --> 01:20:39,370
Όποιος σκεφτεί ενός φρούτου
που ξεκινά με α, β, ή γ;

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- τέλεια.

1670
01:20:40,570 --> 01:20:43,990
Αυτό πρόκειται να τελειώσει εδώ.

1671
01:20:43,990 --> 01:20:47,530
Και έτσι φαίνεται να έχουμε μια
οριακά καλύτερη λύση,

1672
01:20:47,530 --> 01:20:50,820
γιατί τώρα αν θέλω
για να αναζητήσετε το μήλο, θα

1673
01:20:50,820 --> 01:20:53,200
first-- δεν το κάνω μόνο κατάδυση
στη δομή των δεδομένων μου.

1674
01:20:53,200 --> 01:20:54,850
Δεν βουτήξει στη μνήμη του υπολογιστή μου.

1675
01:20:54,850 --> 01:20:56,530
Θα εξετάσουμε πρώτα το πρώτο γράμμα.

1676
01:20:56,530 --> 01:20:58,610
>> Και αυτό είναι ό, τι έναν υπολογιστή
επιστήμονας θα έλεγε.

1677
01:20:58,610 --> 01:21:00,760
Μπορείτε hash στη δομή των δεδομένων σας.

1678
01:21:00,760 --> 01:21:04,100
Μπορείτε να πάρετε τη συμβολή σας, η οποία με τη
η υπόθεση αυτή είναι μια λέξη σαν μήλο.

1679
01:21:04,100 --> 01:21:07,150
Μπορείτε να το αναλύσουμε, κοιτάζοντας
το πρώτο γράμμα σε αυτή την περίπτωση,

1680
01:21:07,150 --> 01:21:08,340
το hashing με αυτόν τον τρόπο.

1681
01:21:08,340 --> 01:21:10,950
Κατακερματισμός είναι ένας γενικός όρος σύμφωνα με την οποία
πάρετε κάτι σαν είσοδο

1682
01:21:10,950 --> 01:21:12,116
και θα παράγει κάποια έξοδο.

1683
01:21:12,116 --> 01:21:15,090
Και η έξοδος από το ότι
περίπτωση είναι η θέση

1684
01:21:15,090 --> 01:21:18,150
που θέλετε να αναζητήσετε, το πρώτο
θέση, δεύτερη θέση, τρίτη.

1685
01:21:18,150 --> 01:21:22,160
Έτσι, η είσοδος είναι το μήλο,
η έξοδος είναι πρώτη.

1686
01:21:22,160 --> 01:21:25,054
Η είσοδος είναι μπανάνα, η
εξόδου θα πρέπει να είναι δεύτερη.

1687
01:21:25,054 --> 01:21:27,220
Η είσοδος είναι πεπόνι,
η έξοδος θα πρέπει να είναι τρίτο.

1688
01:21:27,220 --> 01:21:30,320
Η είσοδος είναι βατόμουρου, η
εξόδου θα πρέπει και πάλι να είναι δεύτερη.

1689
01:21:30,320 --> 01:21:34,010
Και αυτό είναι που σας βοηθά να πάρετε
συντομεύσεις μέσα από τη μνήμη σας

1690
01:21:34,010 --> 01:21:39,050
προκειμένου να πάρει τα λόγια
ή δεδομένα πιο αποτελεσματικά.

1691
01:21:39,050 --> 01:21:43,330
>> Τώρα αυτό μειώνει το χρόνο μας δυνητικά
από όσο ένας στους 26,

1692
01:21:43,330 --> 01:21:45,850
γιατί αν υποθέσουμε ότι έχετε
έχουν ως πολλά "Α" λέξεις όπως "z"

1693
01:21:45,850 --> 01:21:48,080
λέξεις λέξεις "q", η οποία
Δεν είναι πραγματικά realistic--

1694
01:21:48,080 --> 01:21:50,830
θα πάμε να έχουν παραποιήσει ολόκληρη
ορισμένες επιστολές του alphabet--

1695
01:21:50,830 --> 01:21:53,204
αλλά αυτό θα είναι μια σταδιακή
προσέγγιση που δεν επιτρέπει

1696
01:21:53,204 --> 01:21:55,930
μπορείτε να πάρετε τα λόγια πολύ πιο γρήγορα.

1697
01:21:55,930 --> 01:21:59,660
Και στην πραγματικότητα, ένα εξελιγμένο
προγράμματος, η Googles του κόσμου,

1698
01:21:59,660 --> 01:22:02,180
η Facebooks του world--
θα χρησιμοποιήσει έναν πίνακα κατακερματισμού

1699
01:22:02,180 --> 01:22:03,740
για πολλούς διαφορετικούς σκοπούς.

1700
01:22:03,740 --> 01:22:06,590
Αλλά δεν θα ήταν τόσο αφελής ώστε
να εξετάσουμε μόνο το πρώτο γράμμα

1701
01:22:06,590 --> 01:22:09,700
το μήλο ή μπανάνα ή
αχλάδι ή πεπόνι,

1702
01:22:09,700 --> 01:22:13,420
επειδή όπως μπορείτε να δείτε αυτά
λίστες θα μπορούσε να πάρει ακόμα καιρό.

1703
01:22:13,420 --> 01:22:17,130
>> Και έτσι αυτό μπορεί να είναι ακόμα είδος
της linear-- έτσι το είδος της αργή,

1704
01:22:17,130 --> 01:22:19,980
όπως και με το μεγάλο Ο Ν
ότι συζητήσαμε νωρίτερα.

1705
01:22:19,980 --> 01:22:25,290
Έτσι, αυτό που πραγματικά καλό πίνακα κατακερματισμού θα
do-- θα έχει μια πολύ μεγαλύτερη ποικιλία.

1706
01:22:25,290 --> 01:22:28,574
Και θα χρησιμοποιήσει ένα πολύ πιο
εξελιγμένα συνάρτηση κατακερματισμού,

1707
01:22:28,574 --> 01:22:30,240
έτσι ώστε να μην εξετάσουμε μόνο το "α."

1708
01:22:30,240 --> 01:22:35,480
Ίσως φαίνεται στο "A-π-π-λ-ε» και
κατά κάποιο τρόπο μετατρέπει αυτά τα πέντε γράμματα

1709
01:22:35,480 --> 01:22:38,400
στην τοποθεσία όπου
μήλο θα πρέπει να αποθηκεύονται.

1710
01:22:38,400 --> 01:22:42,660
Εμείς απλά αφελώς χρησιμοποιώντας το γράμμα «a»
μόνη της, γιατί είναι όμορφο και απλό.

1711
01:22:42,660 --> 01:22:44,600
>> Αλλά ένα πίνακα κατακερματισμού, σε
το τέλος, μπορείτε να σκεφτείτε

1712
01:22:44,600 --> 01:22:47,270
του ως συνδυασμός
ένας πίνακας, καθένα από τα οποία

1713
01:22:47,270 --> 01:22:51,700
έχει μια συνδεδεμένη λίστα που ιδανική
θα πρέπει να είναι όσο το δυνατόν συντομότερη.

1714
01:22:51,700 --> 01:22:54,364
Και αυτό δεν είναι μια προφανής λύση.

1715
01:22:54,364 --> 01:22:57,280
Στην πραγματικότητα, ένα μεγάλο μέρος της μικρορύθμιση
ότι συνεχίζεται κάτω από την κουκούλα, όταν

1716
01:22:57,280 --> 01:22:59,654
εφαρμογή αυτών των ειδών
εξελιγμένες δομές δεδομένων

1717
01:22:59,654 --> 01:23:01,640
είναι ό, τι είναι το σωστό
μήκος του πίνακα;

1718
01:23:01,640 --> 01:23:03,250
Ποια είναι η λειτουργία σωστό hash;

1719
01:23:03,250 --> 01:23:04,830
Πώς μπορείτε να αποθηκεύσετε τα πράγματα στη μνήμη;

1720
01:23:04,830 --> 01:23:07,249
>> Αλλά συνειδητοποιούν πόσο γρήγορα
Αυτό το είδος της συζήτησης

1721
01:23:07,249 --> 01:23:10,540
κλιμακώθηκε, είτε μέχρι τώρα ότι αυτό είναι το είδος
πάνω από το κεφάλι του σε αυτό το σημείο, το οποίο

1722
01:23:10,540 --> 01:23:11,360
είναι μια χαρά.

1723
01:23:11,360 --> 01:23:18,820
Αλλά αρχίσαμε, ανάκληση, με πραγματικά
κάτι χαμηλού επιπέδου και των ηλεκτρονικών.

1724
01:23:18,820 --> 01:23:20,819
Και έτσι αυτό πάλι είναι αυτό
το θέμα της αφαίρεσης,

1725
01:23:20,819 --> 01:23:23,610
όπου μόλις αρχίσετε να πάρει για
χορηγείται, εντάξει, έχω it-- πήρα υπάρχει

1726
01:23:23,610 --> 01:23:26,680
φυσική μνήμη, εντάξει, το πήρα, κάθε
φυσική τοποθεσία έχει μια διεύθυνση,

1727
01:23:26,680 --> 01:23:29,910
Εντάξει, το πήρα, μπορώ να εκπροσωπώ
αυτές οι διευθύνσεις ως arrows--

1728
01:23:29,910 --> 01:23:34,650
μπορείτε να ξεκινήσετε πολύ γρήγορα για να έχουν
πιο εξελιγμένα συζητήσεις που

1729
01:23:34,650 --> 01:23:38,360
στο τέλος φαίνεται να μας επιτρέπουν
για την επίλυση προβλημάτων όπως η αναζήτηση

1730
01:23:38,360 --> 01:23:41,620
και διαλογή πιο αποτελεσματικά.

1731
01:23:41,620 --> 01:23:44,190
Και να είστε βέβαιοι, too--
επειδή πιστεύω ότι αυτό

1732
01:23:44,190 --> 01:23:48,700
είναι η βαθύτερη που έχουμε πάει σε μερικά
από αυτά τα θέματα CS proper-- έχουμε

1733
01:23:48,700 --> 01:23:51,880
γίνει σε μια μέρα και ένα μισό στο αυτό
το σημείο αυτό μπορείτε να συνήθως κάνει πάνω

1734
01:23:51,880 --> 01:23:55,520
η πορεία οκτώ εβδομάδες σε ένα εξάμηνο.

1735
01:23:55,520 --> 01:23:59,670
>> Οποιεσδήποτε ερωτήσεις σχετικά με αυτά;

1736
01:23:59,670 --> 01:24:01,100
Όχι?

1737
01:24:01,100 --> 01:24:01,940
Εντάξει.

1738
01:24:01,940 --> 01:24:05,610
Λοιπόν, γιατί δεν σταματάμε εκεί,
ξεκινήσετε το γεύμα λίγα λεπτά νωρίτερα,

1739
01:24:05,610 --> 01:24:07,052
επαναλάβει σε μόλις περίπου μία ώρα;

1740
01:24:07,052 --> 01:24:08,760
Και εγώ θα σταθώ για
ένα κομμάτι με τις ερωτήσεις.

1741
01:24:08,760 --> 01:24:11,343
Στη συνέχεια, Πάω να πρέπει να πάει
να λάβει ένα ζευγάρι κλήσεις αν αυτό είναι εντάξει.

1742
01:24:11,343 --> 01:24:15,000
Θα ενεργοποιήσετε κάποια μουσική, εν τω μεταξύ,
αλλά το μεσημεριανό γεύμα θα πρέπει να είναι γύρω από τη γωνία.

1743
01:24:15,000 --> 01:24:17,862