1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Ενότητα 3 - Περισσότερα Άνετα]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Πανεπιστήμιο του Χάρβαρντ]

3
00:00:05,070 --> 00:00:07,310
>> [Αυτό είναι CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Έτσι, το πρώτο ερώτημα είναι διατυπωμένο παράξενα.

5
00:00:12,700 --> 00:00:17,480
GDB σας επιτρέπει να "διορθώσετε" ένα πρόγραμμα, αλλά, πιο συγκεκριμένα, τι χρειάζεται για να σας κάνουμε;

6
00:00:17,480 --> 00:00:22,590
Θα απαντήσω ότι μία, και δεν ξέρω τι ακριβώς αναμενόταν,

7
00:00:22,590 --> 00:00:27,910
οπότε υποθέτω ότι είναι κάτι κατά μήκος των γραμμών του σας επιτρέπει να το βήμα προς βήμα

8
00:00:27,910 --> 00:00:31,540
περπατήσετε μέσα από το πρόγραμμα, αλληλεπιδρούν με αυτό, οι μεταβλητές αλλαγή, κάνει όλα αυτά τα πράγματα -

9
00:00:31,540 --> 00:00:34,270
ουσιαστικά ελέγχουν πλήρως την εκτέλεση ενός προγράμματος

10
00:00:34,270 --> 00:00:38,410
και να επιθεωρεί κάθε δεδομένη μέρος της εκτέλεσης του προγράμματος.

11
00:00:38,410 --> 00:00:43,030
Έτσι, αυτά τα χαρακτηριστικά σας επιτρέπουν να διορθώσετε τα πράγματα.

12
00:00:43,030 --> 00:00:44,830
Εντάξει.

13
00:00:44,830 --> 00:00:50,520
Γιατί η δυαδική αναζήτηση απαιτεί μια σειρά να ταξινομηθούν;

14
00:00:50,520 --> 00:00:53,360
Ποιος θέλει να απαντήσει σε αυτό;

15
00:00:56,120 --> 00:01:00,070
[Φοιτητής] Επειδή δεν λειτουργεί αν δεν είναι ταξινομημένο. Ναι >>. [Γέλια]

16
00:01:00,070 --> 00:01:04,910
Εάν δεν είναι ταξινομημένο, τότε είναι αδύνατο να χωριστεί στη μέση

17
00:01:04,910 --> 00:01:07,850
και να ξέρετε ότι πάντα στα αριστερά είναι μικρότερη και τα πάντα προς τα δεξιά

18
00:01:07,850 --> 00:01:10,490
είναι μεγαλύτερη από την μέση τιμή.

19
00:01:10,490 --> 00:01:12,790
Γι 'αυτό πρέπει να διευθετηθεί.

20
00:01:12,790 --> 00:01:14,170
Εντάξει.

21
00:01:14,170 --> 00:01:17,570
Γιατί είναι είδος φούσκας των n O τετράγωνο;

22
00:01:17,570 --> 00:01:23,230
Μήπως κάποιος πρέπει πρώτα να δώσει μια πολύ γρήγορη επισκόπηση υψηλού επιπέδου των τι είδους είναι φούσκα;

23
00:01:25,950 --> 00:01:33,020
[Φοιτητής] Μπορείτε βασικά να περάσουν από κάθε στοιχείο και να ελέγξετε τα πρώτα στοιχεία.

24
00:01:33,020 --> 00:01:37,150
Αν είστε από όπου μπορείτε να ανταλλάξετε, τότε ελέγξτε τις επόμενες στοιχεία και ούτω καθεξής.

25
00:01:37,150 --> 00:01:40,770
Όταν φτάσετε στο τέλος, τότε ξέρετε ότι το μεγαλύτερο στοιχείο τοποθετείται στο τέλος,

26
00:01:40,770 --> 00:01:42,750
έτσι ώστε να αγνοήσουμε ότι ένας τότε θα συνεχίσουμε να προχωράμε μέσα,

27
00:01:42,750 --> 00:01:48,490
και κάθε φορά που θα πρέπει να ελέγξετε ένα λιγότερο στοιχείο μέχρι να κάνετε καμία αλλαγή. Ναι >>.

28
00:01:48,490 --> 00:01:58,470
Λέγεται είδος φούσκα γιατί αν αναστρέψετε τη σειρά από την πλευρά της, γι 'αυτό είναι πάνω-κάτω, κάθετα,

29
00:01:58,470 --> 00:02:03,100
τότε οι μεγάλες τιμές θα βυθίζονται στον πυθμένα και οι μικρές τιμές θα φούσκα μέχρι την κορυφή.

30
00:02:03,100 --> 00:02:05,210
Αυτό είναι το πώς πήρε το όνομά του.

31
00:02:05,210 --> 00:02:08,220
Και ναι, μπορείτε απλά να περάσει.

32
00:02:08,220 --> 00:02:11,190
Θα συνεχίζουμε μέσω του πίνακα, αλλάζουν τη μεγαλύτερη αξία

33
00:02:11,190 --> 00:02:14,040
για να πάρει τις μεγαλύτερες τιμές προς τα κάτω.

34
00:02:14,040 --> 00:02:17,500
>> Γιατί είναι n Ξ τετράγωνο;

35
00:02:18,690 --> 00:02:24,620
Κατ 'αρχάς, δεν θέλει κανείς να πει γιατί είναι από n O τετράγωνο;

36
00:02:24,620 --> 00:02:28,760
[Φοιτητής] Επειδή για κάθε επιχείρηση πηγαίνει n φορές.

37
00:02:28,760 --> 00:02:32,100
Μπορείτε να είστε σίγουροι ότι έχετε πάρει το μεγαλύτερο στοιχείο σε όλη τη διαδρομή προς τα κάτω,

38
00:02:32,100 --> 00:02:35,230
τότε θα πρέπει να επαναλάβω ότι για όσο πολλά στοιχεία. Ναι >>.

39
00:02:35,230 --> 00:02:41,800
Έτσι, έχετε κατά νου τι σημαίνει μεγάλη O μεγάλος και τι σημαίνει Omega.

40
00:02:41,800 --> 00:02:50,560
Η μεγάλη O είναι σαν το άνω όριο για το πώς αργή μπορεί πραγματικά να τρέξει.

41
00:02:50,560 --> 00:02:58,990
Έτσι, λέγοντας O αυτό του n στο τετράγωνο, δεν είναι από O n ή αλλιώς θα είναι σε θέση να τρέξει

42
00:02:58,990 --> 00:03:02,640
σε γραμμικό χρόνο, αλλά είναι Ο κ κύβους

43
00:03:02,640 --> 00:03:06,390
επειδή οριοθετείται από O κ κύβους.

44
00:03:06,390 --> 00:03:12,300
Αν αυτό είναι που οριοθετείται από O ν τετράγωνο, τότε είναι που οριοθετείται επίσης από n κύβους.

45
00:03:12,300 --> 00:03:20,280
Γι 'αυτό είναι ν τετράγωνο, και στην απόλυτη χειρότερη περίπτωση δεν μπορεί να κάνει καλύτερα από ό, τι n τετράγωνο,

46
00:03:20,280 --> 00:03:22,830
η οποία είναι ο λόγος για αυτό είναι n Ξ τετράγωνο.

47
00:03:22,830 --> 00:03:31,200
Έτσι για να δείτε μικρή μαθηματικά το πώς πρόκειται να είναι n τετράγωνο,

48
00:03:31,200 --> 00:03:40,530
αν έχουμε πέντε πράγματα στην λίστα μας, είναι η πρώτη φορά πόσα swaps θα μπορούσαμε ενδεχομένως να χρειαστεί να

49
00:03:40,530 --> 00:03:47,170
προκειμένου να πάρει αυτό; Ας πραγματικά μόνο -

50
00:03:47,170 --> 00:03:52,040
Πόσες swaps θα πάμε να πρέπει να κάνει το πρώτο τρέξιμο του bubble sort μέσω του πίνακα;

51
00:03:52,040 --> 00:03:53,540
[Φοιτητής] n - 1. Ναι >>.

52
00:03:53,540 --> 00:03:58,340
>> Αν υπάρχουν 5 στοιχεία, θα πάμε να χρειαστεί να κάνετε n - 1.

53
00:03:58,340 --> 00:04:01,100
Στη συνέχεια, στο δεύτερο πόσες swaps θα πάμε να πρέπει να κάνουμε;

54
00:04:01,100 --> 00:04:03,440
[Φοιτητής] n - 2. Ναι >>.

55
00:04:03,440 --> 00:04:11,640
Και η τρίτη θα είναι n - 3, και στη συνέχεια, για λόγους ευκολίας θα γράψω τα δύο τελευταία

56
00:04:11,640 --> 00:04:15,270
όπως και τότε θα πάμε να χρειαστεί να κάνει 2 swaps και 1 swap.

57
00:04:15,270 --> 00:04:19,899
Υποθέτω ότι το τελευταίο μπορεί ή δεν μπορεί πραγματικά να συμβεί.

58
00:04:19,899 --> 00:04:22,820
Είναι ένα swap; Δεν ξέρω.

59
00:04:22,820 --> 00:04:26,490
Αυτά λοιπόν είναι τα συνολικά ποσά των συμβάσεων ανταλλαγής ή τουλάχιστον συγκρίσεις που έχετε να κάνετε.

60
00:04:26,490 --> 00:04:29,910
Ακόμα κι αν δεν έχετε ανταλλάξει, θα πρέπει ακόμα να συγκρίνουν τις τιμές.

61
00:04:29,910 --> 00:04:33,910
Έτσι, υπάρχουν n - 1 συγκρίσεις σε πρώτη εκτέλεση, μέσω του πίνακα.

62
00:04:33,910 --> 00:04:42,050
Αν οργανώσετε αυτά τα πράγματα, ας το κάνει στην πραγματικότητα έξι πράγματα έτσι πήγαν τα πράγματα καλά,

63
00:04:42,050 --> 00:04:44,790
και στη συνέχεια θα κάνω 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Έτσι απλά αναδιάταξη των ποσών αυτών, θέλουμε να δούμε πόσα κάνουμε συγκρίσεις

65
00:04:49,910 --> 00:04:52,700
σε ολόκληρο το αλγόριθμο.

66
00:04:52,700 --> 00:04:56,550
Έτσι, αν φέρουμε αυτά τα παιδιά εδώ κάτω,

67
00:04:56,550 --> 00:05:07,470
τότε είμαστε ακόμα αθροίζοντας ακριβώς όμως πολλές συγκρίσεις ήταν εκεί.

68
00:05:07,470 --> 00:05:13,280
Αλλά αν θέλουμε να τα συλλέξετε και να τα συλλέξετε και να συνοψίσω αυτά,

69
00:05:13,280 --> 00:05:18,130
είναι ακόμα το ίδιο πρόβλημα. Θα συνοψίσω ακριβώς αυτές τις συγκεκριμένες ομάδες.

70
00:05:18,130 --> 00:05:22,400
>> Έτσι τώρα είμαστε αθροίζοντας 3 είναι n. Δεν είναι μόνο 3 n του.

71
00:05:22,400 --> 00:05:27,650
Είναι πάντα θα είναι n / 2 n.

72
00:05:27,650 --> 00:05:29,430
Έτσι, εδώ τυχαίνει να έχει 6.

73
00:05:29,430 --> 00:05:34,830
Αν είχαμε 10 πράγματα, τότε θα μπορούσαμε να κάνουμε αυτή την ομάδα για 5 διαφορετικά ζεύγη των πραγμάτων

74
00:05:34,830 --> 00:05:37,180
και καταλήγουν με n + n + ν + ν + ν.

75
00:05:37,180 --> 00:05:45,840
Έτσι είστε πάντα πρόκειται να πάρει n / 2 n, και έτσι αυτό θα το σημειώνω για να τετράγωνο n / 2.

76
00:05:45,840 --> 00:05:48,890
Και έτσι ακόμα κι αν είναι ο παράγοντας της μισό, η οποία συμβαίνει να έρχονται σε

77
00:05:48,890 --> 00:05:54,190
λόγω του γεγονότος ότι κάθε επανάληψη μέσα πάνω από την συστοιχία 1 συγκρίνουμε λιγότερα

78
00:05:54,190 --> 00:05:58,040
έτσι ώστε να είναι το πώς θα πάρει το πάνω από 2, αλλά εξακολουθεί να είναι n τετράγωνο.

79
00:05:58,040 --> 00:06:01,650
Δεν νοιάζονται για το σταθερό παράγοντα του μισού.

80
00:06:01,650 --> 00:06:07,760
Έτσι, πολλά από τα μεγάλα πράγματα O όπως αυτό βασίζεται σε ακριβώς το είδος του να κάνει αυτό το είδος των μαθηματικών,

81
00:06:07,760 --> 00:06:12,260
κάνει ποσά αριθμητική και γεωμετρική σειρά πράγματα,

82
00:06:12,260 --> 00:06:17,750
αλλά οι περισσότεροι από αυτούς σε αυτή την πορεία είναι αρκετά απλή.

83
00:06:17,750 --> 00:06:19,290
Εντάξει.

84
00:06:19,290 --> 00:06:24,430
Γιατί είναι είδος εισαγωγής σε ωμέγα του n; Τι σημαίνει ωμέγα;

85
00:06:24,430 --> 00:06:27,730
[Δύο μαθητές μιλώντας ταυτόχρονα - ακατάληπτο] >> Ναι.

86
00:06:27,730 --> 00:06:30,630
Omega μπορείτε να σκεφτείτε ως το κατώτερο όριο.

87
00:06:30,630 --> 00:06:36,550
>> Έτσι, δεν έχει σημασία πόσο αποτελεσματική εισαγωγή αλγόριθμος σας είναι είδος,

88
00:06:36,550 --> 00:06:41,810
ανεξάρτητα από τη λίστα που πέρασε, θα πρέπει πάντα να συγκρίνει τουλάχιστον n πράγματα

89
00:06:41,810 --> 00:06:44,620
ή πρέπει να επαναλάβει πάνω από n πράγματα.

90
00:06:44,620 --> 00:06:47,280
Γιατί συμβαίνει αυτό;

91
00:06:47,280 --> 00:06:51,190
[Φοιτητής] Διότι, αν η λίστα έχει ήδη ταξινομημένο, στη συνέχεια, μέσα από το πρώτο επανάληψη

92
00:06:51,190 --> 00:06:54,080
μπορείτε μόνο να εγγυηθεί ότι το πρώτο στοιχείο είναι το λιγότερο,

93
00:06:54,080 --> 00:06:56,490
και η δεύτερη επανάληψη μπορείτε να εγγυηθούν μόνο οι δυο πρώτες είναι

94
00:06:56,490 --> 00:07:00,010
επειδή δεν ξέρετε ότι το υπόλοιπο της λίστας είναι ταξινομημένο. Ναι >>.

95
00:07:00,010 --> 00:07:08,910
Αν περάσει σε ένα εντελώς ταξινομημένη λίστα, τουλάχιστον θα πρέπει να πάει πέρα ​​από όλα τα στοιχεία

96
00:07:08,910 --> 00:07:12,180
για να δείτε ότι τίποτα δεν πρέπει να μετακινούνται.

97
00:07:12,180 --> 00:07:14,720
Έτσι, περνώντας πάνω από τον κατάλογο και λέγοντας OH, αυτό είναι ήδη ταξινομημένο,

98
00:07:14,720 --> 00:07:18,240
είναι αδύνατο για σας να ξέρετε ότι είναι ταξινομημένο μέχρι να ελέγξετε κάθε στοιχείο

99
00:07:18,240 --> 00:07:20,660
για να δείτε ότι είναι σε ταξινομημένη σειρά.

100
00:07:20,660 --> 00:07:25,290
Έτσι, το κάτω φράγμα για το είδος είναι η εισαγωγή της Omega n.

101
00:07:25,290 --> 00:07:28,210
Ποια είναι η χειρότερη περίπτωση χρόνος λειτουργίας του είδους συγχώνευση,

102
00:07:28,210 --> 00:07:31,390
χειρότερη περίπτωση είναι O μεγάλος και πάλι;

103
00:07:31,390 --> 00:07:37,660
Έτσι, στη χειρότερη περίπτωση, πώς συγχώνευση είδος τρέχει;

104
00:07:42,170 --> 00:07:43,690
[Φοιτητής] Ν log n. Ναι >>.

105
00:07:43,690 --> 00:07:49,990
Τα ταχύτερα γενικές αλγόριθμοι ταξινόμησης είναι n log n. Δεν μπορείτε να το κάνετε καλύτερα.

106
00:07:51,930 --> 00:07:55,130
>> Υπάρχουν ειδικές περιπτώσεις, και αν έχουμε χρόνο σήμερα - αλλά πιθανώς won't -

107
00:07:55,130 --> 00:07:59,330
θα μπορούσαμε να δούμε αυτό που κάνει καλύτερα από ό, τι n log n.

108
00:07:59,330 --> 00:08:04,050
Όμως, στη γενική περίπτωση, δεν μπορείτε να κάνετε καλύτερα από ό, τι n log n.

109
00:08:04,050 --> 00:08:09,680
Και συγχώνευση είδος συμβαίνει να είναι το ένα που πρέπει να ξέρετε για αυτό το μάθημα, που είναι n log n.

110
00:08:09,680 --> 00:08:13,260
Και έτσι θα είναι στην πραγματικότητα ότι σήμερα εφαρμογή.

111
00:08:13,260 --> 00:08:18,070
Και τέλος, σε όχι περισσότερες από τρεις προτάσεις, πώς εργασίες επιλογής του είδους;

112
00:08:18,070 --> 00:08:20,370
Μήπως κάποιος θέλει να απαντήσει, και θα μετρήσει τις προτάσεις σας

113
00:08:20,370 --> 00:08:22,390
γιατί αν πάει πάνω από 3 -

114
00:08:25,530 --> 00:08:28,330
Θυμάται κανείς είδος επιλογής;

115
00:08:31,280 --> 00:08:37,809
Η επιλογή του είδους είναι συνήθως αρκετά εύκολο να θυμόμαστε μόνο από το όνομα.

116
00:08:37,809 --> 00:08:45,350
Απλά επαναλάβει πάνω στον πίνακα, να βρουν ό, τι η μεγαλύτερη τιμή είναι μικρότερη ή -

117
00:08:45,350 --> 00:08:47,290
Για ό, τι είστε μέσα διαλογή

118
00:08:47,290 --> 00:08:50,750
Ας πούμε ότι είμαστε διαλογή από το μικρότερο στο μεγαλύτερο.

119
00:08:50,750 --> 00:08:55,250
Θα επαναλάβει πάνω στον πίνακα, ψάχνει για ό, τι το ελάχιστο στοιχείο είναι,

120
00:08:55,250 --> 00:08:59,750
επιλέξτε το και, στη συνέχεια ανταλλάξουν ακριβώς ό, τι είναι στην πρώτη θέση.

121
00:08:59,750 --> 00:09:04,090
Και στη συνέχεια, στο δεύτερο πέρασμα πάνω από τον πίνακα, αναζητήστε το ελάχιστο στοιχείο και πάλι,

122
00:09:04,090 --> 00:09:07,490
επιλέξτε το και στη συνέχεια ανταλλάσσουν με ό, τι είναι στη δεύτερη θέση.

123
00:09:07,490 --> 00:09:10,650
Γι 'αυτό ακριβώς να πάρει και την επιλογή των ελάχιστων τιμών

124
00:09:10,650 --> 00:09:16,050
και την εισαγωγή τους στο μπροστινό μέρος του πίνακα, μέχρι να είναι ταξινομημένος.

125
00:09:19,210 --> 00:09:21,560
Ερωτήσεις σχετικά με αυτό;

126
00:09:21,560 --> 00:09:25,710
>> Αυτά αναπόφευκτα εμφανίζονται στα έντυπα που πρέπει να συμπληρώσετε όταν την υποβολή της PSET.

127
00:09:29,010 --> 00:09:32,360
Αυτά είναι βασικά οι απαντήσεις σε αυτά.

128
00:09:32,360 --> 00:09:34,230
Εντάξει, έτσι τώρα τα προβλήματα κωδικοποίησης.

129
00:09:34,230 --> 00:09:40,140
Έχω ήδη στείλει email από πάνω - Μήπως κάποιος δεν πάρει το μήνυμα ηλεκτρονικού ταχυδρομείου; Εντάξει.

130
00:09:40,140 --> 00:09:46,630
Έχω ήδη στείλει email πάνω από το χώρο που θα πάμε να χρησιμοποιούν,

131
00:09:46,630 --> 00:09:52,120
και αν κάνετε κλικ στο όνομά μου - έτσι νομίζω ότι είμαι πρόκειται να είναι στο κάτω μέρος

132
00:09:52,120 --> 00:09:57,170
λόγω της προς τα πίσω r - αλλά αν κάνετε κλικ στο όνομά μου, θα δείτε 2 αναθεωρήσεις.

133
00:09:57,170 --> 00:10:02,650
Αναθεώρηση 1 πρόκειται να έχω ήδη αντιγραφεί και επικολληθεί τον κώδικα σε χώρους

134
00:10:02,650 --> 00:10:06,900
για την αναζήτηση πράγμα που πρόκειται να πρέπει να εφαρμόσουν.

135
00:10:06,900 --> 00:10:10,540
Και Αναθεώρηση 2 θα είναι το πράγμα είδος που θα εφαρμόσουν μετά από αυτό.

136
00:10:10,540 --> 00:10:15,770
Έτσι, μπορείτε να κάνετε κλικ για την αναθεώρηση μου 1 και εργάζονται από εκεί.

137
00:10:17,350 --> 00:10:22,060
Και τώρα θέλουμε να εφαρμόσουμε δυαδική αναζήτηση.

138
00:10:22,060 --> 00:10:26,470
>> Υπάρχει κάποιος που θέλει να δώσει μόνο ένα ψευδοκώδικα υψηλού επιπέδου εξήγηση

139
00:10:26,470 --> 00:10:31,440
από ό, τι θα πάμε να πρέπει να κάνουμε για αναζήτηση; Ναι.

140
00:10:31,440 --> 00:10:36,170
[Φοιτητής] Παίρνετε ακριβώς στη μέση του πίνακα και να δούμε αν αυτό που ψάχνετε

141
00:10:36,170 --> 00:10:38,650
είναι μικρότερη από εκείνη ή περισσότερο από αυτό.

142
00:10:38,650 --> 00:10:41,080
Και αν είναι λιγότερο, θα πάτε με το μισό που είναι λιγότερο,

143
00:10:41,080 --> 00:10:44,750
και αν είναι περισσότερα, πηγαίνετε στο μισό που είναι περισσότερο και σας επαναλαμβάνω ότι μέχρι να πάρει μόνο ένα πράγμα.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Ναι.

145
00:10:46,570 --> 00:10:51,320
Σημειώστε ότι οι αριθμοί μας σειρά είναι ήδη ταξινομημένο,

146
00:10:51,320 --> 00:10:57,190
και έτσι αυτό σημαίνει ότι μπορούν να επωφεληθούν από αυτό και θα μπορούσαμε να πρώτα να ελέγξετε,

147
00:10:57,190 --> 00:11:00,390
εντάξει, εγώ ψάχνω για τον αριθμό 50.

148
00:11:00,390 --> 00:11:03,720
Έτσι, μπορώ να πάω στη μέση.

149
00:11:03,720 --> 00:11:07,380
Μέση είναι δύσκολο να καθοριστεί, όταν πρόκειται για ένα ακόμα πολλά πράγματα,

150
00:11:07,380 --> 00:11:10,820
αλλά ας πούμε ότι θα περικόψει πάντα στη μέση.

151
00:11:10,820 --> 00:11:14,420
Έτσι, εδώ έχουμε 8 πράγματα, έτσι ώστε η μέση θα είναι 16.

152
00:11:14,420 --> 00:11:17,330
Ψάχνω για το 50, έτσι 50 είναι μεγαλύτερο από 16.

153
00:11:17,330 --> 00:11:21,310
Έτσι τώρα μπορώ να τη θεραπεία βασικά σειρά μου, όπως τα στοιχεία αυτά.

154
00:11:21,310 --> 00:11:23,450
Μπορώ να ρίξει μακριά τα πάντα πάνω από 16.

155
00:11:23,450 --> 00:11:27,440
Τώρα σειρά μου είναι μόνο αυτά τα 4 στοιχεία, και το επαναλαμβάνω.

156
00:11:27,440 --> 00:11:31,910
Μέχρι τότε θέλω να βρω και πάλι τη μέση, η οποία θα είναι 42.

157
00:11:31,910 --> 00:11:34,730
42 είναι μικρότερο από 50, ώστε να μπορώ να πετάξετε αυτά τα δύο στοιχεία.

158
00:11:34,730 --> 00:11:36,890
Αυτή είναι η σειρά μου απομένει.

159
00:11:36,890 --> 00:11:38,430
Πάω να βρείτε τη μέση και πάλι.

160
00:11:38,430 --> 00:11:42,100
Υποθέτω ότι 50 ήταν ένα κακό παράδειγμα, γιατί ήμουν πάντα πετώντας μακριά τα πράγματα προς τα αριστερά,

161
00:11:42,100 --> 00:11:48,280
αλλά με το ίδιο μέτρο, αν ψάχνω για κάτι

162
00:11:48,280 --> 00:11:52,100
και είναι λιγότερο από ό, τι το στοιχείο είμαι σήμερα κοιτάζοντας,

163
00:11:52,100 --> 00:11:55,080
τότε Πάω να ρίξει μακριά τα πάντα προς τα δεξιά.

164
00:11:55,080 --> 00:11:58,150
Έτσι, τώρα θα πρέπει να εφαρμόσουν αυτό.

165
00:11:58,150 --> 00:12:02,310
Σημειώστε ότι θα πρέπει να περάσει σε μέγεθος.

166
00:12:02,310 --> 00:12:06,730
Μπορούμε, επίσης, δεν χρειάζεται να σκληρό κωδικό μέγεθος.

167
00:12:06,730 --> 00:12:11,640
Έτσι, αν θέλουμε να απαλλαγούμε από ότι # define -

168
00:12:19,630 --> 00:12:21,430
Εντάξει.

169
00:12:21,430 --> 00:12:27,180
Πώς μπορώ να καταλάβω πολύ καλά ποιο είναι το μέγεθος του πίνακα αριθμών είναι σήμερα;

170
00:12:27,180 --> 00:12:30,950
>> Πόσα είναι τα στοιχεία του πίνακα αριθμών;

171
00:12:30,950 --> 00:12:33,630
[Φοιτητής] Αριθμοί, στηρίγματα,. Μήκος;

172
00:12:33,630 --> 00:12:36,600
[Bowden] που δεν υπάρχει σε C.

173
00:12:36,600 --> 00:12:38,580
Χρειάζεστε. Μήκος.

174
00:12:38,580 --> 00:12:42,010
Συστοιχίες δεν έχουν ιδιότητες, έτσι δεν υπάρχει καμία ιδιότητα μήκος των συστοιχιών

175
00:12:42,010 --> 00:12:45,650
που θα σας δώσω όσο χρόνο και να συμβαίνει να είναι.

176
00:12:48,180 --> 00:12:51,620
[Φοιτητής] Δείτε πόση μνήμη έχει και διαιρέστε με το πόσο - >> Ναι.

177
00:12:51,620 --> 00:12:55,810
Πώς, λοιπόν, μπορούμε να δούμε πόση μνήμη έχει; >> [Φοιτητής] sizeof. >> Ναι, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof είναι ο φορέας που πρόκειται να επιστρέψει το μέγεθος του πίνακα αριθμών.

179
00:13:01,680 --> 00:13:10,060
Και αυτό πρόκειται να είναι πολλές, ωστόσο υπάρχουν ακέραιοι φορές το μέγεθος του ακεραίου

180
00:13:10,060 --> 00:13:14,050
δεδομένου ότι είναι πόση μνήμη είναι πραγματικά ανάληψη.

181
00:13:14,050 --> 00:13:17,630
Έτσι, αν θέλω τον αριθμό των πραγμάτων στη συστοιχία,

182
00:13:17,630 --> 00:13:20,560
τότε Πάω να θέλετε να διαιρέσετε με το μέγεθος του ακεραίου.

183
00:13:22,820 --> 00:13:26,010
Εντάξει. Έτσι, αυτό μου επιτρέπει να περάσει σε μέγεθος εδώ.

184
00:13:26,010 --> 00:13:29,430
Γιατί πρέπει να περάσει σε μέγεθος σε όλα;

185
00:13:29,430 --> 00:13:38,570
Γιατί δεν μπορώ να κάνω μόνο εδώ int size = sizeof (άχυρα) / sizeof (int);

186
00:13:38,570 --> 00:13:41,490
Γιατί αυτό δεν λειτουργεί;

187
00:13:41,490 --> 00:13:44,470
[Φοιτητής] Δεν είναι μια καθολική μεταβλητή.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack υπάρχει και είμαστε περνώντας σε αριθμούς, όπως άχυρα,

189
00:13:51,540 --> 00:13:54,700
και αυτό είναι το είδος της μια προαναγγελία του τι είναι να έρθει. Ναι.

190
00:13:54,700 --> 00:14:00,170
[Φοιτητής] Haystack είναι μόνο η αναφορά σε αυτό, γι 'αυτό θα επιστρέψει πόσο μεγάλη είναι η αναφορά.

191
00:14:00,170 --> 00:14:02,150
Ναι.

192
00:14:02,150 --> 00:14:09,000
Αμφιβάλλω σε διάλεξη που έχετε δει ακόμα τη στοίβα πραγματικά, έτσι δεν είναι;

193
00:14:09,000 --> 00:14:11,270
Έχουμε μιλήσει μόνο γι 'αυτό.

194
00:14:11,270 --> 00:14:16,090
Έτσι, η στοίβα είναι όπου όλοι οι μεταβλητές σας πρόκειται να αποθηκευτεί.

195
00:14:16,090 --> 00:14:19,960
>> Κάθε μνήμης που διατίθενται για τις τοπικές μεταβλητές συμβαίνει στη στοίβα,

196
00:14:19,960 --> 00:14:24,790
και κάθε λειτουργία έχει το δικό του χώρο στη στοίβα, τις δικές πλαίσιο της στοίβας είναι ό, τι λέγεται.

197
00:14:24,790 --> 00:14:31,590
Έτσι, έχει κύρια πλαίσιο της στοίβας, και μέσα από αυτό θα υπάρχει αυτή σειρά αριθμών,

198
00:14:31,590 --> 00:14:34,270
και πρόκειται να είναι του μεγέθους sizeof (αριθμοί).

199
00:14:34,270 --> 00:14:38,180
Είναι πρόκειται να έχουν το μέγεθος των αριθμών που χωρίζονται ανάλογα με το μέγεθος των στοιχείων,

200
00:14:38,180 --> 00:14:42,010
αλλά ότι όλες οι ζωές μέσα στο πλαίσιο της κύριας στοίβα.

201
00:14:42,010 --> 00:14:45,190
Όταν λέμε αναζήτηση, έρευνα αποκτά το δικό του πλαίσιο της στοίβας,

202
00:14:45,190 --> 00:14:48,840
δικό του χώρο για να αποθηκεύσετε όλες τις τοπικές μεταβλητές.

203
00:14:48,840 --> 00:14:56,420
Αλλά αυτά τα επιχειρήματα - έτσι άχυρα δεν είναι ένα αντίγραφο ολόκληρου του πίνακα.

204
00:14:56,420 --> 00:15:00,990
Δεν περνούν σε ολόκληρο τον πίνακα ως αντίγραφο στην αναζήτηση.

205
00:15:00,990 --> 00:15:04,030
Περνάει μόνο μια αναφορά στο εν λόγω πίνακα.

206
00:15:04,030 --> 00:15:11,470
Έτσι, αναζήτηση μπορεί να έχει πρόσβαση αυτούς τους αριθμούς μέσω αυτής της αναφοράς.

207
00:15:11,470 --> 00:15:17,100
Είναι πρόσβαση ακόμα τα πράγματα που ζουν στο εσωτερικό του πλαισίου στοίβας κύριο του,

208
00:15:17,100 --> 00:15:22,990
αλλά βασικά, όταν φτάνουμε στο δείκτες, η οποία θα πρέπει να είναι σύντομα,

209
00:15:22,990 --> 00:15:24,980
αυτό είναι ό, τι είναι δείκτες.

210
00:15:24,980 --> 00:15:29,400
Οι δείκτες είναι απλά αναφορές σε πράγματα, και μπορείτε να χρησιμοποιήσετε δείκτες να έχουν πρόσβαση τα πράγματα

211
00:15:29,400 --> 00:15:32,030
που βρίσκονται σε πλαίσια σωρό άλλα πράγματα ».

212
00:15:32,030 --> 00:15:37,660
Έτσι ακόμα κι αν οι αριθμοί είναι το τοπικό έως το κύριο, μπορούμε να έχουμε πρόσβαση ακόμα μέσω αυτού του δείκτη.

213
00:15:37,660 --> 00:15:41,770
Αλλά δεδομένου ότι είναι μόνο ένα δείκτη και αυτό είναι ακριβώς μια αναφορά,

214
00:15:41,770 --> 00:15:45,040
sizeof (άχυρα) επιστρέφει μόνο το μέγεθος της αναφοράς η ίδια.

215
00:15:45,040 --> 00:15:47,950
Δεν επιστρέφει το μέγεθος του πράγματος είναι ότι δείχνει να.

216
00:15:47,950 --> 00:15:51,110
Δεν επιστρέφει το πραγματικό μέγεθος των αριθμών.

217
00:15:51,110 --> 00:15:55,660
Και έτσι αυτό δεν πρόκειται να λειτουργήσει όπως θέλουμε να.

218
00:15:55,660 --> 00:15:57,320
>> Ερωτήσεις σχετικά με αυτό;

219
00:15:57,320 --> 00:16:03,250
Οι δείκτες θα πρέπει να πάει σε σημαντικά πιο φρικιαστικές λεπτομέρειες στις εβδομάδες που έρχονται.

220
00:16:06,750 --> 00:16:13,740
Και αυτός είναι ο λόγος πολλά πράγματα που βλέπετε, τα περισσότερα πράγματα αναζήτησης ή είδος πράγματα,

221
00:16:13,740 --> 00:16:16,990
από όπου και αν σχεδόν όλοι θα πρέπει να λάβει το πραγματικό μέγεθος του πίνακα,

222
00:16:16,990 --> 00:16:20,440
επειδή σε C, δεν έχουμε καμία ιδέα ποιο είναι το μέγεθος του πίνακα είναι.

223
00:16:20,440 --> 00:16:22,720
Θα πρέπει να περάσει με το χέρι μέσα

224
00:16:22,720 --> 00:16:27,190
Και δεν μπορείτε να περάσετε το χέρι σε όλη τη σειρά, επειδή είστε απλά περνώντας κατά την περίοδο αναφοράς

225
00:16:27,190 --> 00:16:30,390
και δεν μπορεί να πάρει από το μέγεθος της αναφοράς.

226
00:16:30,390 --> 00:16:32,300
Εντάξει.

227
00:16:32,300 --> 00:16:38,160
Έτσι, τώρα θέλουμε να εφαρμόσουμε ό, τι εξηγήθηκε πριν.

228
00:16:38,160 --> 00:16:41,530
Μπορείτε να εργάζονται σε αυτό για ένα λεπτό,

229
00:16:41,530 --> 00:16:45,250
και δεν έχετε να ανησυχείτε για να πάρει τα πάντα τέλεια 100% εργασίας.

230
00:16:45,250 --> 00:16:51,410
Απλά γράψτε το ψευδοκώδικα το ήμισυ για το πώς νομίζετε ότι θα πρέπει να λειτουργεί.

231
00:16:52,000 --> 00:16:53,630
Εντάξει.

232
00:16:53,630 --> 00:16:56,350
Δεν πρέπει να γίνεται με εντελώς αυτό ακόμα.

233
00:16:56,350 --> 00:17:02,380
Αλλά κανείς δεν αισθάνεται άνετα με ό, τι μέχρι τώρα,

234
00:17:02,380 --> 00:17:05,599
σαν κάτι που μπορούμε να εργαστούμε από κοινού;

235
00:17:05,599 --> 00:17:09,690
Υπάρχει κάποιος που θέλουν να γίνουν εθελοντές; Ή θα πάρει τυχαία.

236
00:17:12,680 --> 00:17:18,599
Δεν χρειάζεται να είναι σωστό από κάθε μέτρο, αλλά κάτι μπορούμε να τροποποιήσουμε σε μια κατάσταση εργασίας.

237
00:17:18,599 --> 00:17:20,720
[Φοιτητής] Σίγουρα. Εντάξει >>.

238
00:17:20,720 --> 00:17:27,220
Έτσι, μπορείτε να αποθηκεύσετε την αναθεώρηση κάνοντας κλικ στο εικονίδιο Αποθήκευση.

239
00:17:27,220 --> 00:17:29,950
Είσαι Ramya, έτσι δεν είναι; >> [Φοιτητής] Ναι. >> [Bowden] Εντάξει.

240
00:17:29,950 --> 00:17:35,140
Έτσι τώρα μπορώ να προβάλλω την αναθεώρηση σας και ο καθένας μπορεί να τραβήξει μέχρι και την αναθεώρηση.

241
00:17:35,140 --> 00:17:38,600
Και εδώ έχουμε - Εντάξει.

242
00:17:38,600 --> 00:17:43,160
Έτσι Ramya πήγε με την αναδρομική λύση, η οποία είναι σίγουρα μια έγκυρη λύση.

243
00:17:43,160 --> 00:17:44,970
Υπάρχουν δύο τρόποι που μπορείτε να κάνετε αυτό το πρόβλημα.

244
00:17:44,970 --> 00:17:48,060
Μπορείτε να το κάνετε είτε επαναληπτικά ή αναδρομικά.

245
00:17:48,060 --> 00:17:53,860
Τα περισσότερα προβλήματα που αντιμετωπίζετε αυτό μπορεί να γίνει κατ 'επανάληψη μπορεί να γίνει και επαναληπτικά.

246
00:17:53,860 --> 00:17:58,510
Έτσι, εδώ έχουμε κάνει κατ 'επανάληψη.

247
00:17:58,510 --> 00:18:03,730
>> Μήπως κάποιος θέλει να ορίσει τι σημαίνει να κάνει μια αναδρομική συνάρτηση;

248
00:18:07,210 --> 00:18:08,920
[Φοιτητής] Όταν έχετε μια λειτουργία αυτοαποκαλείται

249
00:18:08,920 --> 00:18:13,470
και αυτοαποκαλείται συνέχεια μέχρι να βγαίνει με πραγματική και αληθινή. Ναι >>.

250
00:18:13,470 --> 00:18:17,680
Μια αναδρομική συνάρτηση είναι απλώς μια λειτουργία που καλεί τον εαυτό της.

251
00:18:17,680 --> 00:18:24,140
Υπάρχουν τρία μεγάλα πράγματα που μια αναδρομική συνάρτηση πρέπει να έχει.

252
00:18:24,140 --> 00:18:27,310
Το πρώτο είναι προφανώς, η ίδια αποκαλεί.

253
00:18:27,310 --> 00:18:29,650
Το δεύτερο είναι η βασική περίπτωση.

254
00:18:29,650 --> 00:18:33,390
Έτσι, σε κάποιο σημείο η λειτουργία πρέπει να σταματήσει να αυτοαποκαλείται,

255
00:18:33,390 --> 00:18:35,610
και αυτό είναι η βασική περίπτωση είναι για.

256
00:18:35,610 --> 00:18:43,860
Έτσι, εδώ ξέρουμε ότι θα πρέπει να σταματήσει, θα πρέπει να δώσουμε σε αναζήτηση μας

257
00:18:43,860 --> 00:18:48,150
όταν έναρξης ισούται τέλος - και θα πάμε πάνω τι σημαίνει αυτό.

258
00:18:48,150 --> 00:18:52,130
Αλλά τελικά, το τελευταίο πράγμα που είναι σημαντικό για αναδρομικές συναρτήσεις:

259
00:18:52,130 --> 00:18:59,250
οι λειτουργίες πρέπει να προσεγγίσουμε με κάποιο τρόπο την βασική περίπτωση.

260
00:18:59,250 --> 00:19:04,140
Όπως και αν δεν είστε ενημέρωση στην πραγματικότητα τίποτα όταν κάνετε τη δεύτερη αναδρομική κλήση,

261
00:19:04,140 --> 00:19:07,880
αν είστε κυριολεκτικά καλώντας απλά τη λειτουργία και πάλι με τα ίδια επιχειρήματα

262
00:19:07,880 --> 00:19:10,130
και καθολικές μεταβλητές δεν έχουν αλλάξει ή τίποτα,

263
00:19:10,130 --> 00:19:14,430
ποτέ δεν θα φτάσει την υπόθεση βάσης, οπότε αυτό είναι κακό.

264
00:19:14,430 --> 00:19:17,950
Θα είναι μια άπειρη αναδρομή και μια υπερχείλιση στοίβας.

265
00:19:17,950 --> 00:19:24,330
Αλλά εδώ βλέπουμε ότι η ενημέρωση συμβαίνει επειδή είμαστε ενημέρωση ξεκινήσει + τέλος / 2,

266
00:19:24,330 --> 00:19:28,180
είμαστε ενημέρωση τέλος το επιχείρημα εδώ, είμαστε ενημέρωση το επιχείρημα εκκίνησης εδώ.

267
00:19:28,180 --> 00:19:32,860
Έτσι, σε όλες τις αναδρομικές κλήσεις μας ενημερώνετε κάτι. Εντάξει.

268
00:19:32,860 --> 00:19:38,110
Θέλετε να μας καθοδηγήσει λύση σας; Σίγουρα >>.

269
00:19:38,110 --> 00:19:44,270
Είμαι χρησιμοποιώντας SearchHelp έτσι ώστε κάθε φορά που κάνω αυτή την κλήση της συνάρτησης

270
00:19:44,270 --> 00:19:47,910
Έχω την έναρξη της όπου ψάχνω στη σειρά και το τέλος

271
00:19:47,910 --> 00:19:49,380
από όπου ψάχνω τον πίνακα.

272
00:19:49,380 --> 00:19:55,330
>> Σε κάθε βήμα, όπου λέει ότι είναι το μεσαίο στοιχείο, το οποίο είναι αρχή + τέλος / 2,

273
00:19:55,330 --> 00:19:58,850
είναι ότι η ισότητα σε ό, τι ψάχνουμε;

274
00:19:58,850 --> 00:20:04,650
Και αν είναι, τότε το βρήκαμε, και υποθέτω ότι παίρνει πέρασε πάνω από τα επίπεδα αναδρομή.

275
00:20:04,650 --> 00:20:12,540
Και αν αυτό δεν είναι αλήθεια, τότε θα ελέγξει αν η μέση τιμή του πίνακα είναι πολύ μεγάλη,

276
00:20:12,540 --> 00:20:19,320
οπότε κοιτάμε το αριστερό μισό του πίνακα με τη μετάβαση από την αρχή μέχρι το μέσο δείκτη.

277
00:20:19,320 --> 00:20:22,710
Και αλλιώς κάνουμε το μισό τέλος.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Εντάξει.

279
00:20:24,740 --> 00:20:27,730
Καλό ακούγεται.

280
00:20:27,730 --> 00:20:36,640
Εντάξει, έτσι, ένα ζευγάρι πράγματα, και στην πραγματικότητα, αυτό είναι ένα πολύ υψηλού επιπέδου πράγμα

281
00:20:36,640 --> 00:20:41,270
ότι ποτέ δεν θα πρέπει να ξέρετε για αυτό το μάθημα, αλλά είναι αλήθεια.

282
00:20:41,270 --> 00:20:46,080
Αναδρομικές συναρτήσεις, μπορείτε πάντα να ακούω ότι είναι μια κακή συμφωνία

283
00:20:46,080 --> 00:20:51,160
γιατί αν κατ 'επανάληψη καλέσει τον εαυτό σας πάρα πολλές φορές, μπορείτε να πάρετε υπερχείλιση στοίβας

284
00:20:51,160 --> 00:20:54,990
δεδομένου ότι, όπως είπα και πριν, κάθε λειτουργία έχει το δικό του πλαίσιο στοίβας.

285
00:20:54,990 --> 00:20:59,500
Έτσι, κάθε κλήση της επαναληπτικής λειτουργίας αποκτά το δικό του πλαίσιο στοίβας του.

286
00:20:59,500 --> 00:21:04,140
Έτσι, αν κάνετε 1.000 αναδρομικές κλήσεις, μπορείτε να πάρετε 1.000 καρέ στοίβα,

287
00:21:04,140 --> 00:21:08,390
και γρήγορα να σας οδηγήσουν να έχει πάρα πολλές πλαίσια στοίβα και να σπάσει τα πράγματα απλά.

288
00:21:08,390 --> 00:21:13,480
Έτσι, γι 'αυτό και αναδρομικές συναρτήσεις είναι γενικά κακή.

289
00:21:13,480 --> 00:21:19,370
Αλλά υπάρχει ένα ωραίο υποσύνολο των αναδρομικές συναρτήσεις που ονομάζεται ουρά-αναδρομικές συναρτήσεις,

290
00:21:19,370 --> 00:21:26,120
και αυτό συμβαίνει να είναι ένα παράδειγμα ενός όπου εάν ο μεταγλωττιστής προσέχει

291
00:21:26,120 --> 00:21:29,920
και θα έπρεπε, νομίζω - σε Clang αν περάσει αυτό το O2-σημαία

292
00:21:29,920 --> 00:21:33,250
τότε θα παρατηρήσετε αυτό είναι ουρά αναδρομική και να κάνει τα πράγματα καλά.

293
00:21:33,250 --> 00:21:40,050
>> Θα χρησιμοποιείτε τον ίδιο πλαίσιο στοίβα ξανά και ξανά για κάθε αναδρομική κλήση.

294
00:21:40,050 --> 00:21:47,010
Και έτσι επειδή είστε χρησιμοποιώντας το ίδιο πλαίσιο στοίβας, δεν χρειάζεται να ανησυχείτε για

295
00:21:47,010 --> 00:21:51,690
ποτέ στοίβα ξεχειλίζει, και την ίδια στιγμή, όπως σας είπα πριν,

296
00:21:51,690 --> 00:21:56,380
όπου τη στιγμή που θα επιστρέψει αληθής, τότε θα πρέπει να επιστρέψει μέχρι όλα αυτά τα πλαίσια στοίβας

297
00:21:56,380 --> 00:22:01,740
και το 10ο κλήση SearchHelp πρέπει να επιστρέψει στο 9ο, πρέπει να επιστρέψει στον 8ο.

298
00:22:01,740 --> 00:22:05,360
Έτσι, αυτό δεν πρέπει να συμβεί όταν οι λειτουργίες είναι αναδρομική ουρά.

299
00:22:05,360 --> 00:22:13,740
Και έτσι αυτό που κάνει αυτή η ουρά είναι αναδρομική λειτουργία ειδοποίηση ότι για οποιαδήποτε πρόσκληση για searchHelp

300
00:22:13,740 --> 00:22:18,470
η αναδρομική κλήση ότι είναι κάνει είναι αυτό που είναι επιστροφή.

301
00:22:18,470 --> 00:22:25,290
Έτσι, στην πρώτη πρόσκληση για SearchHelp, είτε θα επιστρέψει αμέσως ψευδή,

302
00:22:25,290 --> 00:22:29,590
επιστρέψει αμέσως αλήθεια, ή κάνουμε μια αναδρομική κλήση για SearchHelp

303
00:22:29,590 --> 00:22:33,810
όπου ό, τι είμαστε επιστροφή είναι αυτό που κλήση επιστρέφει.

304
00:22:33,810 --> 00:22:51,560
Και δεν θα μπορούσαμε να το κάνουμε αυτό, αν κάναμε κάτι σαν int x = SearchHelp, επιστροφή x * 2,

305
00:22:51,560 --> 00:22:55,440
μερικά μόνο τυχαία αλλαγή.

306
00:22:55,440 --> 00:23:01,470
>> Έτσι τώρα αυτή η αναδρομική κλήση, αυτό int x = SearchHelp αναδρομική κλήση,

307
00:23:01,470 --> 00:23:05,740
δεν είναι πλέον ουρά επαναληπτικό, γιατί πραγματικά δεν πρέπει να επιστρέψει

308
00:23:05,740 --> 00:23:10,400
πίσω σε μια προηγούμενη στοίβα πλαίσιο, έτσι ώστε ότι η προηγούμενη κλήση σε λειτουργία

309
00:23:10,400 --> 00:23:13,040
μπορεί στη συνέχεια να κάνουμε κάτι με την τιμή επιστροφής.

310
00:23:13,040 --> 00:23:22,190
Έτσι, αυτό δεν είναι αναδρομική ουρά, αλλά ό, τι είχαμε πριν είναι ωραία ουρά αναδρομική. Ναι.

311
00:23:22,190 --> 00:23:27,000
[Φοιτητής] Δεν θα έπρεπε η δεύτερη βασική περίπτωση να ελέγχονται πρώτα

312
00:23:27,000 --> 00:23:30,640
επειδή θα μπορούσε να υπάρξει μια κατάσταση όπου όταν περνάτε το επιχείρημα ότι

313
00:23:30,640 --> 00:23:35,770
έχετε ξεκινήσει = τέλος, αλλά είναι η αξία της βελόνας.

314
00:23:35,770 --> 00:23:47,310
Το ερώτημα αυτό δεν μπορεί να τρέξει σε περίπτωση όπου τέλος είναι η αξία της βελόνας

315
00:23:47,310 --> 00:23:52,000
ή να ξεκινήσετε = τέλος, κατάλληλα, ξεκινήστε = τέλος

316
00:23:52,000 --> 00:23:59,480
και δεν έχετε πραγματικά ελεγχθεί ότι η ιδιαίτερη αξία ακόμη,

317
00:23:59,480 --> 00:24:03,910
στη συνέχεια, ξεκινήστε + τέλος / 2 είναι ακριβώς πρόκειται να είναι η ίδια αξία.

318
00:24:03,910 --> 00:24:07,890
Αλλά έχουμε ήδη επιστρέψει ψευδείς και ποτέ δεν ελέγχεται πραγματικά την αξία.

319
00:24:07,890 --> 00:24:14,240
Έτσι, τουλάχιστον, στην πρώτη κλήση, αν το μέγεθος είναι 0, τότε θέλουμε να επιστρέψουμε ψευδείς.

320
00:24:14,240 --> 00:24:17,710
Αλλά αν το μέγεθος είναι 1, τότε ξεκίνημα δεν πρόκειται να ισούται τέλος,

321
00:24:17,710 --> 00:24:19,820
και θα ελέγχει τουλάχιστον το ένα στοιχείο.

322
00:24:19,820 --> 00:24:26,750
Αλλά νομίζω ότι έχετε δίκιο στο ότι μπορούμε να καταλήξουμε σε μια περίπτωση κατά την οποία αρχίζουν + τέλος / 2,

323
00:24:26,750 --> 00:24:31,190
έναρξη καταλήγει να είναι το ίδιο με την έναρξη + τέλος / 2,

324
00:24:31,190 --> 00:24:35,350
αλλά ποτέ δεν ελέγξαμε πραγματικότητα αυτό το στοιχείο.

325
00:24:35,350 --> 00:24:44,740
>> Έτσι, αν εμείς πρώτα να ελέγξετε είναι το μεσαίο στοιχείο η τιμή που ψάχνουμε,

326
00:24:44,740 --> 00:24:47,110
τότε μπορούμε να επιστρέψουν αμέσως αλήθεια.

327
00:24:47,110 --> 00:24:50,740
Αλλιώς αν είναι ίσες, τότε δεν υπάρχει νόημα να συνεχιστεί

328
00:24:50,740 --> 00:24:58,440
αφού είμαστε ακριβώς πρόκειται να ενημερώσει σε περίπτωση που είμαστε σε μια ενιαία στοιχείο του πίνακα.

329
00:24:58,440 --> 00:25:01,110
Αν μόνο στοιχείο που δεν είναι αυτός που ψάχνουμε,

330
00:25:01,110 --> 00:25:03,530
τότε όλα είναι λάθος. Ναι.

331
00:25:03,530 --> 00:25:08,900
[Μαθητής] Το θέμα είναι ότι, δεδομένου ότι το μέγεθος είναι στην πραγματικότητα μεγαλύτερο από τον αριθμό των στοιχείων στη συστοιχία,

332
00:25:08,900 --> 00:25:13,070
υπάρχει ήδη μια μετατόπιση - >> Έτσι θα μέγεθος -

333
00:25:13,070 --> 00:25:19,380
[Φοιτητής] Πείτε αν η σειρά ήταν μεγέθους 0, τότε η SearchHelp θα ελέγξει πραγματικά άχυρα από το 0

334
00:25:19,380 --> 00:25:21,490
για την πρώτη πρόσκληση.

335
00:25:21,490 --> 00:25:25,300
Η σειρά έχει μέγεθος 0, έτσι το 0 είναι - >> Ναι.

336
00:25:25,300 --> 00:25:30,750
Υπάρχει ένα άλλο πράγμα που - θα μπορούσε να είναι καλή. Ας σκεφτούμε.

337
00:25:30,750 --> 00:25:40,120
Έτσι, αν η σειρά είχε 10 στοιχεία και το μεσαίο θα πάμε για να ελέγξετε δείκτη είναι 5,

338
00:25:40,120 --> 00:25:45,700
έτσι είμαστε έλεγχο 5, και ας πούμε ότι η τιμή είναι μικρότερη.

339
00:25:45,700 --> 00:25:50,720
Έτσι, είμαστε ρίχνουν τα πάντα μακριά από τις 5 και μετά.

340
00:25:50,720 --> 00:25:54,030
Έτσι ξεκινούν + τέλος / 2 θα είναι το τέλος μας νέα,

341
00:25:54,030 --> 00:25:57,450
Οπότε ναι, είναι πάντα πρόκειται να μείνουν και μετά το τέλος της σειράς.

342
00:25:57,450 --> 00:26:03,570
Εάν είναι μια περίπτωση που ήταν ακόμη ή περίεργο, τότε θα ελέγξει, ας πούμε, 4,

343
00:26:03,570 --> 00:26:05,770
αλλά είμαστε ακόμα μακριά ρίχνουν -

344
00:26:05,770 --> 00:26:13,500
Οπότε ναι, τέλος είναι πάντα πρόκειται να είναι πέρα ​​από το πραγματικό τέλος του πίνακα.

345
00:26:13,500 --> 00:26:18,350
Έτσι, τα στοιχεία που έχουμε με επίκεντρο, τέλος πάντα θα είναι η μία μετά από αυτό.

346
00:26:18,350 --> 00:26:24,270
Και έτσι, αν ποτέ κάνει έναρξη ίση τέλος, είμαστε σε μια σειρά μεγέθους 0.

347
00:26:24,270 --> 00:26:35,600
>> Το άλλο πράγμα που σκεφτόμουν είναι να ενημερώνετε την αρχή μέχρι να ξεκινήσει + τέλος / 2,

348
00:26:35,600 --> 00:26:44,020
έτσι αυτό είναι η υπόθεση ότι έχω πρόβλημα με, όπου αρχίζουν + τέλος / 2

349
00:26:44,020 --> 00:26:46,820
είναι το στοιχείο είμαστε έλεγχο.

350
00:26:46,820 --> 00:26:58,150
Ας πούμε ότι είχαμε αυτό το 10-στοιχείο του πίνακα. Όποια και αν είναι.

351
00:26:58,150 --> 00:27:03,250
Έτσι ξεκινούν + τέλος / 2 πρόκειται να είναι κάτι σαν κι αυτό,

352
00:27:03,250 --> 00:27:07,060
και αν αυτό δεν είναι η τιμή, ας πούμε ότι θέλετε να ενημερώσετε.

353
00:27:07,060 --> 00:27:10,060
Η τιμή είναι μεγαλύτερη, έτσι θέλουμε να δούμε σε αυτό το μισό του πίνακα.

354
00:27:10,060 --> 00:27:15,910
Πώς, λοιπόν, είμαστε ενημέρωση ξεκίνημα, είμαστε ενημέρωση ξεκίνημα τώρα είναι αυτό το στοιχείο.

355
00:27:15,910 --> 00:27:23,790
Αλλά αυτό μπορεί να εξακολουθούν να εργάζονται, ή τουλάχιστον, μπορείτε να κάνετε εκκίνηση + τέλος / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Φοιτητής] Δεν χρειάζεται να ξεκινήσετε + τέλος [δεν ακούγεται] >> Ναι.

357
00:27:27,850 --> 00:27:33,240
Έχουμε ήδη ελέγξει αυτό το στοιχείο και να ξέρετε ότι δεν είναι αυτό που ψάχνουμε.

358
00:27:33,240 --> 00:27:36,800
Γι 'αυτό και δεν χρειάζεται να ενημερώσετε ξεκίνημα να είναι αυτό το στοιχείο.

359
00:27:36,800 --> 00:27:39,560
Μπορούμε να παραλείψετε αυτό ακριβώς και ενημέρωση αρχίσει να είναι αυτό το στοιχείο.

360
00:27:39,560 --> 00:27:46,060
Και υπάρχει πάντα μια περίπτωση, ας πούμε, ότι αυτό ήταν τέλος,

361
00:27:46,060 --> 00:27:53,140
ώστε στη συνέχεια, ξεκινήστε θα είναι αυτό, ξεκινήστε το τέλος + / 2 θα είναι αυτό,

362
00:27:53,140 --> 00:28:00,580
+ ξεκινήσει τέλος - Ναι, νομίζω ότι μπορεί να καταλήξει σε άπειρη αναδρομή.

363
00:28:00,580 --> 00:28:12,690
Ας πούμε ότι είναι απλά ένας πίνακας μεγέθους 2 ή σε ένα πίνακα μεγέθους 1. Νομίζω ότι αυτό θα λειτουργήσει.

364
00:28:12,690 --> 00:28:19,490
Έτσι, σήμερα, είναι ότι η αρχή και το τέλος στοιχείο είναι 1 πέρα ​​από αυτό.

365
00:28:19,490 --> 00:28:24,110
Έτσι, το στοιχείο ότι θα πάμε για να ελέγξετε είναι αυτό,

366
00:28:24,110 --> 00:28:29,400
και στη συνέχεια, όταν θα ενημερώσετε ξεκίνημα, είμαστε ενημέρωση αρχή να είναι 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
η οποία πρόκειται να μας τελειώσει πάλι με την έναρξη να είναι αυτό το στοιχείο.

368
00:28:33,160 --> 00:28:36,210
>> Έτσι είμαστε έλεγχο το ίδιο στοιχείο ξανά και ξανά.

369
00:28:36,210 --> 00:28:43,310
Έτσι, αυτή είναι η περίπτωση κατά την οποία κάθε αναδρομική κλήση πρέπει να ενημερώσετε πραγματικά κάτι.

370
00:28:43,310 --> 00:28:48,370
Έτσι πρέπει να κάνουμε αρχή + τέλος / 2 + 1, ή αλλιώς υπάρχει περίπτωση

371
00:28:48,370 --> 00:28:50,710
όπου δεν είμαστε πραγματικά έναρξη ενημέρωση.

372
00:28:50,710 --> 00:28:53,820
Όλοι είδατε αυτό;

373
00:28:53,820 --> 00:28:56,310
Εντάξει.

374
00:28:56,310 --> 00:29:03,860
Υπάρχει κάποιος που έχει ερωτήσεις σχετικά με αυτή τη λύση ή περισσότερα σχόλια;

375
00:29:05,220 --> 00:29:10,280
Εντάξει. Υπάρχει κάποιος που έχει μια επαναληπτική λύση που όλοι μπορούμε να δούμε;

376
00:29:17,400 --> 00:29:20,940
Μήπως κάνουμε όλοι αναδρομικά;

377
00:29:20,940 --> 00:29:25,950
Ή, επίσης, υποθέτω ότι αν ανοίξει το δικό της, τότε μπορεί να έχετε παρακαμφθεί προηγούμενο.

378
00:29:25,950 --> 00:29:28,810
Μήπως αυτόματα σώσει; Δεν είμαι θετικός.

379
00:29:35,090 --> 00:29:39,130
Υπάρχει κάποιος που έχει επαναληπτική;

380
00:29:39,130 --> 00:29:42,430
Μπορούμε να περπατάς με τα πόδια μαζί, αν δεν.

381
00:29:46,080 --> 00:29:48,100
Η ιδέα θα είναι η ίδια.

382
00:30:00,260 --> 00:30:02,830
Επαναληπτική λύση.

383
00:30:02,830 --> 00:30:07,140
Εμείς πάμε να θέλουν να κάνουν ουσιαστικά την ίδια ιδέα

384
00:30:07,140 --> 00:30:16,530
όπου θέλουμε να παρακολουθείτε το νέο τέλος της σειράς και τη νέα αρχή του πίνακα

385
00:30:16,530 --> 00:30:18,510
και να κάνουμε ότι ξανά και ξανά.

386
00:30:18,510 --> 00:30:22,430
Και αν αυτό που είμαστε την παρακολούθηση της ως την αρχή και το τέλος τέμνονται ποτέ,

387
00:30:22,430 --> 00:30:29,020
τότε δεν το βρείτε και μπορούμε να επιστρέψουμε ψευδείς.

388
00:30:29,020 --> 00:30:37,540
Λοιπόν, πώς μπορώ να το κάνω αυτό; Όποιος έχει προτάσεις ή κωδικό για μένα να σηκώσει;

389
00:30:42,190 --> 00:30:47,450
[Φοιτητής] Κάνετε ένα βρόχο while. Ναι >>.

390
00:30:47,450 --> 00:30:49,450
Θα έχετε την ευκαιρία να θέλουν να κάνουν ένα βρόχο.

391
00:30:49,450 --> 00:30:51,830
>> Μήπως έχετε κωδικό που θα μπορούσε να σηκώσει, ή ό, τι ήταν πας να προτείνετε;

392
00:30:51,830 --> 00:30:56,340
[Φοιτητής] Νομίζω πως ναι. >> Εντάξει. Αυτό κάνει τα πράγματα πιο εύκολα. Ποιο ήταν το όνομα σας;

393
00:30:56,340 --> 00:30:57,890
[Φοιτητής] Lucas.

394
00:31:00,140 --> 00:31:04,190
Αναθεώρηση 1. Εντάξει.

395
00:31:04,190 --> 00:31:13,200
Χαμηλή είναι αυτό που ονομάζεται ξεκινήσει πριν.

396
00:31:13,200 --> 00:31:17,080
Up δεν είναι αρκετά αυτό που ονομάζεται τέλος πριν.

397
00:31:17,080 --> 00:31:22,750
Στην πραγματικότητα, το τέλος είναι τώρα μέσα στον πίνακα. Είναι ένα στοιχείο που πρέπει να εξετάσουμε.

398
00:31:22,750 --> 00:31:26,890
Τόσο χαμηλό είναι 0, είναι μέχρι το μέγεθος του πίνακα - 1,

399
00:31:26,890 --> 00:31:34,780
και τώρα είμαστε looping, και εμείς τον έλεγχο -

400
00:31:34,780 --> 00:31:37,340
Υποθέτω ότι μπορείτε να περπατήσετε μέσα από αυτό.

401
00:31:37,340 --> 00:31:41,420
Ποια ήταν η σκέψη σας μέσα από αυτό; Περπατήστε μαζί μας μέσω κωδικού σας.

402
00:31:41,420 --> 00:31:49,940
[Φοιτητής] Σίγουρα. Κοιτάξτε την αξία άχυρα στη μέση και η σύγκρισή της με βελόνα.

403
00:31:49,940 --> 00:31:58,520
Έτσι, αν αυτό είναι μεγαλύτερο από ό, τι βελόνα σας, τότε θα θέλετε να - Ω, στην πραγματικότητα, αυτό θα πρέπει να είναι προς τα πίσω.

404
00:31:58,520 --> 00:32:05,180
Θα πάμε να θέλουν να πετάξουν το δεξί μισό, και έτσι ναι, αυτό θα πρέπει να είναι ο τρόπος.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Έτσι, αυτό πρέπει να είναι μικρότερη; Είναι ότι αυτό που είπατε; >> [Φοιτητής] Ναι.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Εντάξει. Λιγότερο.

407
00:32:10,390 --> 00:32:15,700
Έτσι, αν αυτό που ψάχνουμε σε είναι μικρότερη από ό, τι θέλουμε,

408
00:32:15,700 --> 00:32:19,410
τότε ναι, θέλουμε να ρίξει μακριά το αριστερό μισό,

409
00:32:19,410 --> 00:32:22,210
πράγμα που σημαίνει ότι ενημερώνετε ό, τι σκέφτεστε

410
00:32:22,210 --> 00:32:26,610
με μετακίνηση χαμηλά προς τα δεξιά της συστοιχίας.

411
00:32:26,610 --> 00:32:30,130
Αυτό φαίνεται καλό.

412
00:32:30,130 --> 00:32:34,550
Νομίζω ότι έχει το ίδιο θέμα που είπαμε στο προηγούμενο,

413
00:32:34,550 --> 00:32:49,760
όπου αν χαμηλό είναι 0 μέχρι και είναι 1, τότε χαμηλή έως + / 2 πρόκειται να συσταθεί για να είναι το ίδιο πράγμα ξανά.

414
00:32:49,760 --> 00:32:53,860
>> Και ακόμα κι αν αυτό δεν είναι η περίπτωση, είναι ακόμα πιο αποτελεσματική τουλάχιστον

415
00:32:53,860 --> 00:32:57,630
απλά να ρίξει μακριά το στοιχείο που μόλις κοίταξε την οποία γνωρίζουμε ότι είναι λάθος.

416
00:32:57,630 --> 00:33:03,240
Έτσι, χαμηλή έως + / 2 + 1 - >> [φοιτητής] Αυτό θα πρέπει να είναι ο άλλος τρόπος.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Ή αυτό θα πρέπει να είναι - 1 και το άλλο πρέπει να είναι + 1.

418
00:33:05,900 --> 00:33:09,580
[Φοιτητής] Και θα πρέπει να υπάρχει ένα διπλό ίσον. >> [Bowden] Ναι.

419
00:33:09,580 --> 00:33:11,340
[Φοιτητής] Ναι.

420
00:33:14,540 --> 00:33:15,910
Εντάξει.

421
00:33:15,910 --> 00:33:21,280
Και τέλος, τώρα που έχουμε αυτό το + 1 - 1 πράγμα,

422
00:33:21,280 --> 00:33:31,520
είναι - δεν μπορεί να είναι - είναι ποτέ δυνατόν για χαμηλό για να καταλήξουμε σε μια τιμή μεγαλύτερη από ό, τι μέχρι;

423
00:33:35,710 --> 00:33:40,320
Νομίζω ότι ο μόνος τρόπος που μπορεί να συμβεί - Είναι δυνατόν; >> [Φοιτητής] Δεν ξέρω.

424
00:33:40,320 --> 00:33:45,220
Αλλά αν παίρνει περικοπεί και στη συνέχεια να παίρνει μείον 1 και ότι στη συνέχεια - >> Ναι.

425
00:33:45,220 --> 00:33:47,480
[Φοιτητής] Θα ήταν ίσως πάρει μπέρδεμα πάνω.

426
00:33:49,700 --> 00:33:53,940
Νομίζω ότι θα είναι καλό μόνο και μόνο επειδή

427
00:33:53,940 --> 00:33:58,800
για να καταλήξουν κάτω θα πρέπει να είναι ίση, νομίζω.

428
00:33:58,800 --> 00:34:03,070
Αλλά αν είναι ίσες, τότε δεν θα είχαμε κάνει το βρόχο, ενώ για να αρχίσει με

429
00:34:03,070 --> 00:34:06,670
και εμείς απλώς θα επιστρέψει την αξία. Έτσι, νομίζω ότι είμαστε καλά τώρα.

430
00:34:06,670 --> 00:34:11,530
Σημειώστε ότι ακόμη και αν αυτό το πρόβλημα δεν είναι πλέον αναδρομικό

431
00:34:11,530 --> 00:34:17,400
το ίδιο είδος των ιδεών ισχύουν όπου μπορούμε να δούμε πώς αυτό το τόσο εύκολα προσφέρεται

432
00:34:17,400 --> 00:34:23,659
σε ένα αναδρομικό διάλυμα από το γεγονός ότι είμαστε μόνο την ενημέρωση τους δείκτες ξανά και ξανά,

433
00:34:23,659 --> 00:34:29,960
φτιάχνουμε το πρόβλημα όλο και μικρότερα, είμαστε εστιάζοντας σε ένα υποσύνολο του πίνακα.

434
00:34:29,960 --> 00:34:40,860
[Φοιτητής] Αν χαμηλή είναι 0 και είναι μέχρι 1, θα είναι και οι δύο 0 + 1/2, η οποία θα πάει στο 0,

435
00:34:40,860 --> 00:34:44,429
και τότε κάποιος θα είναι + 1, το ένα θα είναι - 1.

436
00:34:47,000 --> 00:34:50,870
[Φοιτητής] Όταν εμείς τον έλεγχο της ισότητας;

437
00:34:50,870 --> 00:34:55,100
Όπως και αν το μεσαίο είναι πραγματικά βελόνα;

438
00:34:55,100 --> 00:34:58,590
Εμείς δεν κάνουμε σήμερα αυτό; Oh!

439
00:35:00,610 --> 00:35:02,460
Αν it's -

440
00:35:05,340 --> 00:35:13,740
Ναι. Εμείς απλά δεν μπορεί να κάνει το τεστ εδώ κάτω, γιατί ας πούμε το πρώτο μεσαίο -

441
00:35:13,740 --> 00:35:16,430
[Φοιτητής] Είναι πραγματικά ήθελε να μην πετάτε το δεσμευμένο.

442
00:35:16,430 --> 00:35:20,220
Έτσι, αν έχετε ρίξει μακριά το δεσμευμένο, θα πρέπει να το ελέγξει πρώτα ή οτιδήποτε άλλο.

443
00:35:20,220 --> 00:35:23,350
Αχ. Ναι. >> [Φοιτητής] Ναι.

444
00:35:23,350 --> 00:35:29,650
Έτσι τώρα έχουμε ρίξει μακριά το ένα αυτή τη στιγμή κοίταξε,

445
00:35:29,650 --> 00:35:33,260
πράγμα που σημαίνει ότι τώρα πρέπει να έχουν επίσης

446
00:35:33,260 --> 00:35:44,810
αν (άχυρα [(χαμηλή έως +) / 2] == βελόνα), τότε μπορούμε να επιστρέψουμε αλήθεια.

447
00:35:44,810 --> 00:35:52,070
Και αν έβαλα άλλο ή αν απλά, αυτό σημαίνει κυριολεκτικά το ίδιο πράγμα

448
00:35:52,070 --> 00:35:57,110
επειδή αυτό θα είχε επιστρέψει αλήθεια.

449
00:35:57,110 --> 00:36:01,450
Γι 'αυτό και θα βάλει άλλο αν, αλλά δεν πειράζει.

450
00:36:01,450 --> 00:36:10,440
>> Έτσι, αν αυτό το άλλο, άλλο αυτό, και αυτό είναι ένα κοινό πράγμα που κάνω

451
00:36:10,440 --> 00:36:14,340
όπου ακόμα κι αν είναι η περίπτωση κατά την οποία όλα είναι καλά εδώ,

452
00:36:14,340 --> 00:36:22,780
όπως το χαμηλό δεν μπορεί ποτέ να είναι μεγαλύτερη από ό, τι μέχρι, δεν αξίζει λογική για το αν αυτό είναι αλήθεια.

453
00:36:22,780 --> 00:36:28,010
Έτσι, μπορείτε επίσης να πούμε, ενώ χαμηλά είναι μικρότερη ή ίση με

454
00:36:28,010 --> 00:36:30,720
ή χαμηλή, ενώ είναι λιγότερο από ό, τι

455
00:36:30,720 --> 00:36:35,300
έτσι αν είναι ποτέ ίσες ή χαμηλό συμβαίνει για να περάσει επάνω,

456
00:36:35,300 --> 00:36:40,130
τότε μπορούμε να ξεφύγουμε από αυτόν τον βρόχο.

457
00:36:41,410 --> 00:36:44,630
Ερωτήσεις, προβλήματα, παρατηρήσεις;

458
00:36:47,080 --> 00:36:49,270
Εντάξει. Αυτό φαίνεται καλό.

459
00:36:49,270 --> 00:36:52,230
Τώρα θέλουμε να κάνουμε το είδος.

460
00:36:52,230 --> 00:37:04,030
Αν πάμε στη δεύτερη αναθεώρηση μου, βλέπουμε αυτούς τους ίδιους αριθμούς,

461
00:37:04,030 --> 00:37:07,550
αλλά τώρα που δεν είναι πλέον σε ταξινομημένη σειρά.

462
00:37:07,550 --> 00:37:12,840
Και θέλουμε να υλοποιήσουμε τη χρήση οποιουδήποτε είδους αλγόριθμο του O n log n.

463
00:37:12,840 --> 00:37:17,240
Έτσι, ο αλγόριθμος που νομίζετε ότι θα πρέπει να εφαρμόσουμε εδώ; >> [Φοιτητής] είδος συγχώνευσης.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Ναι. Συγχώνευση sort είναι O (n log n), έτσι ώστε να είναι αυτό που πάμε να κάνουμε.

465
00:37:23,810 --> 00:37:26,680
Και το πρόβλημα θα είναι αρκετά παρόμοια,

466
00:37:26,680 --> 00:37:31,920
όπου προσφέρεται εύκολα σε μια αναδρομική λύση.

467
00:37:31,920 --> 00:37:35,580
Μπορούμε επίσης να καταλήξουμε σε μια επαναληπτική λύση, αν θέλουμε,

468
00:37:35,580 --> 00:37:42,540
αναδρομή, αλλά θα είναι πιο εύκολο εδώ και θα πρέπει να κάνουμε αναδρομή.

469
00:37:45,120 --> 00:37:49,530
Υποθέτω ότι θα περπατήσετε μέσα από το είδος συγχώνευσης κατ 'αρχάς,

470
00:37:49,530 --> 00:37:54,280
αν και υπάρχει ένα υπέροχο βίντεο για το είδος συγχώνευσης ήδη. [Γέλια]

471
00:37:54,280 --> 00:37:59,780
Έτσι συγχώνευση είδος υπάρχουν - Είμαι σπατάλη τόσο πολύ από αυτό το χαρτί.

472
00:37:59,780 --> 00:38:02,080
Ω, υπάρχει μόνο μία αριστερά.

473
00:38:02,080 --> 00:38:03,630
Έτσι συγχώνευση.

474
00:38:08,190 --> 00:38:12,470
Ω, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Εντάξει.

476
00:38:29,910 --> 00:38:33,460
Συγχώνευση παίρνει δύο χωριστές σειρές.

477
00:38:33,460 --> 00:38:36,780
Ατομικά οι δύο αυτές σειρές τόσο ταξινομημένο.

478
00:38:36,780 --> 00:38:40,970
Έτσι, αυτή η σειρά, 1, 3, 5, ταξινομημένο. Αυτός ο πίνακας, 0, 2, 4, ταξινομημένο.

479
00:38:40,970 --> 00:38:46,710
Τώρα τι συγχώνευση πρέπει να κάνουμε είναι να συνδυάσει σε ένα ενιαίο πίνακα που είναι η ίδια ταξινόμηση.

480
00:38:46,710 --> 00:38:57,130
Έτσι, θέλουμε μια σειρά μεγέθους 6 που θα έχουν αυτά τα στοιχεία στο εσωτερικό του

481
00:38:57,130 --> 00:38:59,390
σε ταξινομημένη σειρά.

482
00:38:59,390 --> 00:39:03,390
>> Και γι 'αυτό μπορούν να επωφεληθούν από το γεγονός ότι είναι ταξινομημένο αυτά τα δύο συστοιχίες

483
00:39:03,390 --> 00:39:06,800
να το κάνετε αυτό σε γραμμικό χρόνο,

484
00:39:06,800 --> 00:39:13,510
γραμμική έννοια του χρόνου, αν αυτή η σειρά είναι x μέγεθος και αυτό είναι y μέγεθος,

485
00:39:13,510 --> 00:39:20,970
τότε ο συνολικός αλγόριθμος θα πρέπει να είναι Ο (x + y). Εντάξει.

486
00:39:20,970 --> 00:39:23,150
Έτσι προτάσεις.

487
00:39:23,150 --> 00:39:26,030
[Φοιτητής] Θα μπορούσαμε να ξεκινήσουμε από την αριστερά;

488
00:39:26,030 --> 00:39:30,150
Έτσι, θα βάλετε το 0 κάτω πρώτα και στη συνέχεια το 1 και στη συνέχεια, εδώ είστε στο 2.

489
00:39:30,150 --> 00:39:33,320
Έτσι είναι το είδος του σαν να έχετε μια καρτέλα που κινείται προς τα δεξιά. >> [Bowden] Ναι.

490
00:39:33,320 --> 00:39:41,070
Για δύο από αυτούς τους πίνακες, αν επικεντρώνεται μόνο στην αριστερή στοιχείο.

491
00:39:41,070 --> 00:39:43,530
Επειδή είναι ταξινομημένο δύο συστοιχίες, γνωρίζουμε ότι αυτά τα 2 στοιχεία

492
00:39:43,530 --> 00:39:46,920
είναι τα μικρότερα στοιχεία σε οποιαδήποτε συστοιχία.

493
00:39:46,920 --> 00:39:53,500
Έτσι, αυτό σημαίνει ότι 1 από τα 2 αυτά στοιχεία θα πρέπει να είναι το μικρότερο στοιχείο σε νέα σειρά μας.

494
00:39:53,500 --> 00:39:58,190
Συμβαίνει ότι η μικρότερη είναι η μία στη δεξιά αυτή τη φορά.

495
00:39:58,190 --> 00:40:02,580
Έτσι παίρνουμε 0, τοποθετήστε το στην αριστερή πλευρά, επειδή το 0 είναι μικρότερο από 1,

496
00:40:02,580 --> 00:40:08,210
έτσι ώστε να λάβει 0, τοποθετήστε την στην πρώτη θέση μας, και στη συνέχεια θα ενημερώσει το

497
00:40:08,210 --> 00:40:12,070
να τώρα να επικεντρωθούν στο πρώτο στοιχείο.

498
00:40:12,070 --> 00:40:14,570
Και τώρα επαναλαμβάνουμε.

499
00:40:14,570 --> 00:40:20,670
Έτσι τώρα συγκρίνουμε 2 και 1. 1 είναι μικρότερη, οπότε θα εισάγετε 1.

500
00:40:20,670 --> 00:40:25,300
Ενημερώνουμε το δείκτη στο σημείο με αυτόν τον τύπο.

501
00:40:25,300 --> 00:40:33,160
Τώρα μπορούμε να το κάνουμε και πάλι, έτσι 2. Αυτό θα ενημερώσει, να συγκρίνουν αυτά τα 2, 3.

502
00:40:33,160 --> 00:40:37,770
Αυτή η ενημέρωση, στη συνέχεια, 4 και 5.

503
00:40:37,770 --> 00:40:42,110
Έτσι, αυτό είναι συγχώνευσης.

504
00:40:42,110 --> 00:40:49,010
>> Θα πρέπει να είναι αρκετά προφανές ότι είναι γραμμικό χρόνο από τότε που πήγαινε σε κάθε στοιχείο μια φορά.

505
00:40:49,010 --> 00:40:55,980
Και αυτό είναι το μεγαλύτερο βήμα για την εφαρμογή της συγχώνευσης είδος κάνει αυτό.

506
00:40:55,980 --> 00:40:59,330
Και δεν είναι ότι σκληρά.

507
00:40:59,330 --> 00:41:15,020
Ένα ζευγάρι πράγματα για να ανησυχούν είναι ας πούμε ότι ήταν συγχώνευση 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Στην περίπτωση αυτή, καταλήγουμε στο σενάριο όπου αυτό πρόκειται να είναι μικρότερο,

509
00:41:30,930 --> 00:41:36,160
τότε θα ενημερώσει αυτό το δείκτη, αυτό πρόκειται να είναι μικρότερο, να ενημερώσετε αυτό,

510
00:41:36,160 --> 00:41:41,280
αυτό είναι μικρότερο, και τώρα θα πρέπει να αναγνωρίσουν

511
00:41:41,280 --> 00:41:44,220
όταν έχετε ξεμείνει από πραγματικά στοιχεία για να συγκρίνουμε με.

512
00:41:44,220 --> 00:41:49,400
Από τη στιγμή που έχουν ήδη χρησιμοποιήσει όλη αυτή τη σειρά,

513
00:41:49,400 --> 00:41:55,190
τα πάντα σε αυτή την σειρά είναι τώρα μόλις εισαχθεί εδώ.

514
00:41:55,190 --> 00:42:02,040
Έτσι, αν ποτέ τρέξει στο σημείο όπου ένας από τους πίνακες μας είναι εντελώς συγχωνεύονται ήδη,

515
00:42:02,040 --> 00:42:06,510
τότε παίρνουμε μόνο όλα τα στοιχεία του άλλου πίνακα και τοποθετήστε τα μέσα στο άκρο της συστοιχίας.

516
00:42:06,510 --> 00:42:13,630
Έτσι μπορούμε να εισάγουμε μόνο 4, 5, 6. Εντάξει.

517
00:42:13,630 --> 00:42:18,070
Αυτό είναι ένα πράγμα που πρέπει να προσέξετε.

518
00:42:22,080 --> 00:42:26,120
Η εφαρμογή αυτή θα πρέπει να είναι το βήμα 1.

519
00:42:26,120 --> 00:42:32,600
Συγχώνευση ταξινομήσετε τότε με βάση αυτό, είναι 2 βήματα, 2 ανόητη βήματα.

520
00:42:38,800 --> 00:42:42,090
Ας δώσουμε ακριβώς αυτό το φάσμα.

521
00:42:57,920 --> 00:43:05,680
Έτσι συγχώνευση είδος, βήμα 1 είναι να σπάσει αναδρομικά τον πίνακα στη μέση.

522
00:43:05,680 --> 00:43:09,350
Έτσι, αυτή χωρίζεται σε σειρά μισά.

523
00:43:09,350 --> 00:43:22,920
Έχουμε τώρα 4, 15, 16, 50 και 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Και τώρα το κάνουμε ξανά και χωρίζουμε σε αυτά τα μισά.

525
00:43:25,800 --> 00:43:27,530
Απλά θα το κάνω σε αυτή την πλευρά.

526
00:43:27,530 --> 00:43:34,790
Έτσι 4, 15 και 16, 50.

527
00:43:34,790 --> 00:43:37,440
Εμείς θα κάνουμε το ίδιο πράγμα εδώ.

528
00:43:37,440 --> 00:43:40,340
Και τώρα που χωρίζεται στη μέση και πάλι.

529
00:43:40,340 --> 00:43:51,080
Και έχουμε 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Έτσι, αυτό είναι βασική περίπτωση μας.

531
00:43:53,170 --> 00:44:00,540
Μόλις οι συστοιχίες είναι μεγέθους 1, τότε θα σταματήσει με τη διάσπαση στη μέση.

532
00:44:00,540 --> 00:44:03,190
>> Τώρα τι θα κάνουμε με αυτό;

533
00:44:03,190 --> 00:44:15,730
Καταλήγουμε αυτό θα σπάσει σε 8, 23, 42, και 108.

534
00:44:15,730 --> 00:44:24,000
Έτσι, τώρα που είμαστε σε αυτό το σημείο, τώρα το βήμα δύο από είδος συγχώνευσης συγχώνευση μόνο ζεύγη στους καταλόγους.

535
00:44:24,000 --> 00:44:27,610
Έτσι θέλουμε να συγχωνεύσει αυτά. Απλά καλέστε συγχώνευση.

536
00:44:27,610 --> 00:44:31,410
Γνωρίζουμε συγχώνευση θα επιστρέψει αυτά σε ταξινομημένη σειρά.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Τώρα θέλουμε να συγχώνευσή τους, και ότι θα επιστρέψει μια λίστα με αυτούς σε ταξινομημένη σειρά,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Θα συγχωνεύσει αυτά - δεν μπορώ να γράψω - 8, 23 και 42, 108.

541
00:44:57,380 --> 00:45:02,890
Έτσι έχουμε νέα ζευγάρια φορά.

542
00:45:02,890 --> 00:45:05,140
Τώρα μόλις συγχώνευση και πάλι.

543
00:45:05,140 --> 00:45:10,130
Σημειώστε ότι κάθε μία από αυτές τις λίστες είναι ταξινομημένο από μόνη της,

544
00:45:10,130 --> 00:45:15,220
και στη συνέχεια μπορούμε να συγχωνευθούν μόνο αυτές τις λίστες για να πάρετε μια λίστα με μέγεθος 4, το οποίο είναι ταξινομημένο

545
00:45:15,220 --> 00:45:19,990
και να συγχωνεύσει τις δύο λίστες για να πάρετε μια λίστα με μέγεθος 4 που είναι ταξινομημένο.

546
00:45:19,990 --> 00:45:25,710
Και τέλος, μπορούμε να συγχωνεύσει τις δύο λίστες του μεγέθους 4 για να πάρετε μία λίστα μέγεθος 8 που είναι ταξινομημένο.

547
00:45:25,710 --> 00:45:34,030
Έτσι για να δείτε ότι αυτό είναι συνολικά n log n, έχουμε ήδη είδαμε ότι συγχώνευσης είναι γραμμική,

548
00:45:34,030 --> 00:45:40,390
έτσι όταν έχουμε να κάνουμε με τη συγχώνευση αυτών, έτσι όπως το συνολικό κόστος της συγχώνευσης

549
00:45:40,390 --> 00:45:43,410
για αυτές τις δύο λίστες είναι μόλις 2 επειδή -

550
00:45:43,410 --> 00:45:49,610
Ή επίσης, είναι από O n, n αλλά εδώ είναι μόνο αυτά τα 2 στοιχεία, γι 'αυτό είναι 2.

551
00:45:49,610 --> 00:45:52,850
Και οι 2 θα είναι 2 και οι 2 θα είναι 2 και οι 2 θα είναι 2,

552
00:45:52,850 --> 00:45:58,820
έτσι σε όλες τις συγχωνεύσεις που πρέπει να κάνουμε, καταλήγουν να κάνουν n.

553
00:45:58,820 --> 00:46:03,210
Like 2 + 2 + 2 + 2 είναι 8, η οποία είναι η,

554
00:46:03,210 --> 00:46:08,060
έτσι το κόστος της συγχώνευσης σε αυτό το σύνολο είναι n.

555
00:46:08,060 --> 00:46:10,810
Και τότε το ίδιο πράγμα εδώ.

556
00:46:10,810 --> 00:46:16,980
Θα συγχωνευθούν αυτά τα 2, τότε αυτά τα 2, και ατομικά συγχώνευση αυτή θα λάβει τέσσερις πράξεις,

557
00:46:16,980 --> 00:46:23,610
αυτή η συγχώνευση θα λάβει τέσσερις πράξεις, αλλά για μια ακόμη φορά, μεταξύ όλων αυτών,

558
00:46:23,610 --> 00:46:29,030
καταλήγουμε συγχώνευση n συνολικά τα πράγματα, έτσι και αυτό το βήμα παίρνει n.

559
00:46:29,030 --> 00:46:33,670
Και έτσι κάθε επίπεδο διαρκεί n στοιχεία που συγχωνεύονται.

560
00:46:33,670 --> 00:46:36,110
>> Και πόσα επίπεδα υπάρχουν;

561
00:46:36,110 --> 00:46:40,160
Σε κάθε επίπεδο, σειρά μας μεγαλώνει ανάλογα με το μέγεθος 2.

562
00:46:40,160 --> 00:46:44,590
Εδώ συστοιχίες μας είναι μεγέθους 1, εδώ από όπου και αν το μέγεθος της 2, εδώ από όπου και αν μεγέθους 4,

563
00:46:44,590 --> 00:46:46,470
και, τέλος, από όπου και αν το μέγεθος 8.

564
00:46:46,470 --> 00:46:56,450
Έτσι, δεδομένου ότι ο διπλασιασμός, υπάρχουν πρόκειται να είναι ένα σύνολο από n log από αυτά τα επίπεδα.

565
00:46:56,450 --> 00:47:02,090
Έτσι, με log n επίπεδα, κάθε επίπεδο, λαμβάνοντας n σύνολο της δραστηριότητας,

566
00:47:02,090 --> 00:47:05,720
έχουμε ένα log n n αλγόριθμο.

567
00:47:05,720 --> 00:47:07,790
Ερωτήσεις;

568
00:47:08,940 --> 00:47:13,320
Έχουν οι άνθρωποι ήδη σημειώσει πρόοδο σχετικά με το πώς να εφαρμόσουν αυτό;

569
00:47:13,320 --> 00:47:18,260
Υπάρχει κάποιος ήδη σε μια κατάσταση όπου μπορώ ακριβώς να σηκώσει τον κωδικό τους;

570
00:47:20,320 --> 00:47:22,260
Μπορώ να σας δώσω ένα λεπτό.

571
00:47:24,770 --> 00:47:27,470
Αυτός πρόκειται να είναι περισσότερο.

572
00:47:27,470 --> 00:47:28,730
Συστήνω ιδιαίτερα επαναληφθεί -

573
00:47:28,730 --> 00:47:30,510
Δεν χρειάζεται να κάνετε αναδρομή για συγχώνευση

574
00:47:30,510 --> 00:47:33,750
γιατί να κάνω αναδρομή για συγχώνευση, εσείς πρόκειται να πρέπει να περάσει μια δέσμη των διαφορετικών μεγεθών.

575
00:47:33,750 --> 00:47:37,150
Μπορείτε, αλλά είναι ενοχλητικό.

576
00:47:37,150 --> 00:47:43,720
Αλλά αναδρομή για το ίδιο είδος είναι αρκετά εύκολο.

577
00:47:43,720 --> 00:47:49,190
Απλά καλέστε κυριολεκτικά είδος στο αριστερό μισό, είδος στο δεξί μισό. Εντάξει.

578
00:47:51,770 --> 00:47:54,860
Όποιος έχει κάτι που μπορώ να σηκώσει ακόμα;

579
00:47:54,860 --> 00:47:57,540
Ή αλλιώς θα σας δώσω ένα λεπτό.

580
00:47:58,210 --> 00:47:59,900
Εντάξει.

581
00:47:59,900 --> 00:48:02,970
Όποιος έχει κάτι που μπορεί να λειτουργήσει με;

582
00:48:05,450 --> 00:48:09,680
Ή αλλιώς θα δουλέψουν με αυτό και στη συνέχεια, αναπτύξτε από εκεί.

583
00:48:09,680 --> 00:48:14,050
>> Όποιος έχει περισσότερο από αυτό που μπορώ να σηκώσει;

584
00:48:14,050 --> 00:48:17,770
[Φοιτητής] Ναι. Μπορείτε να σηκώσει ορυχείο. >> Εντάξει.

585
00:48:17,770 --> 00:48:19,730
Ναι!

586
00:48:22,170 --> 00:48:25,280
[Φοιτητής] Υπήρχαν πολλές προϋποθέσεις. >> Ω, πυροβολούν. Μπορείτε να -

587
00:48:25,280 --> 00:48:28,110
[Φοιτητής] Έχω να το αποθηκεύσετε. Ναι >>.

588
00:48:32,420 --> 00:48:35,730
Γι 'αυτό και έκανα τη συγχώνευση χωριστά.

589
00:48:35,730 --> 00:48:38,570
Ναι, αλλά δεν είναι τόσο άσχημα.

590
00:48:39,790 --> 00:48:41,650
Εντάξει.

591
00:48:41,650 --> 00:48:47,080
Έτσι το είδος είναι η ίδια ακριβώς ζητούν mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Εξηγήστε μας τι mergeSortHelp κάνει.

593
00:48:49,530 --> 00:48:55,700
[Φοιτητής] MergeSortHelp λίγο πολύ κάνει τα δύο βασικά βήματα,

594
00:48:55,700 --> 00:49:01,270
η οποία είναι να ταξινομεί κάθε μισό της συστοιχίας και κατόπιν να συγχωνεύσει και τους δύο.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Εντάξει, έτσι ώστε να μου δώσει μια δεύτερη.

596
00:49:10,850 --> 00:49:13,210
Νομίζω ότι αυτό - >> [φοιτητής] θα πρέπει να -

597
00:49:17,100 --> 00:49:19,400
Ναι. Είμαι λείπει κάτι.

598
00:49:19,400 --> 00:49:23,100
Σε συγχώνευση, συνειδητοποιώ ότι πρέπει να δημιουργηθεί μια νέα σειρά

599
00:49:23,100 --> 00:49:26,530
γιατί δεν θα μπορούσε να το κάνει στη θέση του. Ναι >>. Δεν μπορείς. Διορθώστε.

600
00:49:26,530 --> 00:49:28,170
[Φοιτητής] Έτσι, μπορώ να δημιουργήσω ένα νέο πίνακα.

601
00:49:28,170 --> 00:49:31,510
Ξέχασα το τέλος της συγχώνευσης την εκ νέου αλλαγή.

602
00:49:31,510 --> 00:49:34,490
Εντάξει. Χρειαζόμαστε μια νέα σειρά.

603
00:49:34,490 --> 00:49:41,000
Σε τέτοια συγχώνευση, αυτό είναι σχεδόν πάντα αλήθεια.

604
00:49:41,000 --> 00:49:44,340
Μέρος του κόστους για ένα καλύτερο αλγόριθμο-σοφός

605
00:49:44,340 --> 00:49:47,310
είναι σχεδόν πάντα χρειάζεται να χρησιμοποιήσετε λίγο περισσότερη μνήμη.

606
00:49:47,310 --> 00:49:51,570
Μέχρι εδώ, δεν έχει σημασία πώς θα το κάνετε συγχώνευση είδος,

607
00:49:51,570 --> 00:49:54,780
αναπόφευκτα θα χρειαστεί να χρησιμοποιήσετε κάποια επιπλέον μνήμη.

608
00:49:54,780 --> 00:49:58,240
Αυτός ή αυτή δημιούργησε μια νέα σειρά.

609
00:49:58,240 --> 00:50:03,400
Και μετά λέτε στο τέλος το μόνο που χρειάζεται να αντιγράψετε νέα σειρά στην αρχική σειρά.

610
00:50:03,400 --> 00:50:04,830
[Φοιτητής] Έτσι νομίζω, ναι.

611
00:50:04,830 --> 00:50:08,210
Δεν ξέρω αν αυτό λειτουργεί από την άποψη της καταμέτρησης από την αναφορά ή οτιδήποτε άλλο -

612
00:50:08,210 --> 00:50:11,650
Ναι, αυτό θα λειτουργήσει. >> [Φοιτητής] Εντάξει.

613
00:50:20,620 --> 00:50:24,480
Μήπως προσπαθείτε λειτουργεί αυτό; >> [Φοιτητής] Όχι, όχι ακόμα. Εντάξει >>.

614
00:50:24,480 --> 00:50:28,880
Δοκιμάστε να εκτελέσετε αυτό, και στη συνέχεια θα μιλήσω γι 'αυτό για ένα δευτερόλεπτο.

615
00:50:28,880 --> 00:50:35,200
[Φοιτητής] θα πρέπει να έχει όλα τα πρωτότυπα λειτουργία και τα πάντα, όμως, έτσι δεν είναι;

616
00:50:37,640 --> 00:50:40,840
Τα πρωτότυπα συναρτήσεων. Εννοείς όπως - Ναι.

617
00:50:40,840 --> 00:50:43,040
Ταξινόμηση καλεί mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Έτσι, προκειμένου για το είδος να καλέσετε mergeSortHelp, mergeSortHelp πρέπει είτε έχουν καθοριστεί

619
00:50:47,390 --> 00:50:56,370
πριν από το είδος ή το μόνο που χρειάζεται το πρωτότυπο. Απλά αντιγράψτε και επικολλήστε αυτό.

620
00:50:56,370 --> 00:50:59,490
Και ομοίως, mergeSortHelp καλεί συγχώνευση,

621
00:50:59,490 --> 00:51:03,830
αλλά η συγχώνευση δεν έχει οριστεί ακόμη, έτσι ώστε να μπορούμε να την αφήσουμε mergeSortHelp ξέρω

622
00:51:03,830 --> 00:51:08,700
ότι η συγχώνευση είναι αυτό πρόκειται να μοιάσει, και αυτό είναι αυτό.

623
00:51:09,950 --> 00:51:15,730
Έτσι mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Έχουμε εδώ ένα ζήτημα όπου δεν έχουμε καμία περίπτωση βάση.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp είναι αναδρομικές, έτσι ώστε κάθε αναδρομική συνάρτηση

626
00:51:38,110 --> 00:51:42,610
θα χρειαστεί κάποιο είδος της υπόθεσης βάση για να ξέρει πότε να σταματήσει κατ 'επανάληψη το ίδιο καλώντας.

627
00:51:42,610 --> 00:51:45,590
Τι είναι η βασική περίπτωση μας πρόκειται να εδώ; Ναι.

628
00:51:45,590 --> 00:51:49,110
[Φοιτητής] Εάν το μέγεθος είναι 1; >> [Bowden] Ναι.

629
00:51:49,110 --> 00:51:56,220
Έτσι, όπως είδαμε εκεί, σταματήσαμε συστοιχίες διάσπαση

630
00:51:56,220 --> 00:52:01,850
μόλις φτάσαμε σε συστοιχίες μεγέθους 1, το οποίο αναπόφευκτα οι ίδιοι ταξινομημένο.

631
00:52:01,850 --> 00:52:09,530
Έτσι, αν το μέγεθος είναι ίσο με 1, γνωρίζουμε ότι ο πίνακας είναι ήδη ταξινομημένο,

632
00:52:09,530 --> 00:52:12,970
έτσι μπορούμε απλά να επιστρέψουν.

633
00:52:12,970 --> 00:52:16,880
>> Σημειώστε ότι είναι άκυρη, έτσι δεν επιστρέφουν τίποτα συγκεκριμένο, απλά επιστρέφει.

634
00:52:16,880 --> 00:52:19,580
Εντάξει. Έτσι, αυτό είναι βασική περίπτωση μας.

635
00:52:19,580 --> 00:52:27,440
Υποθέτω ότι βασική περίπτωση μας θα μπορούσε επίσης να είναι, αν τυχαίνει να συγχωνεύονται μια σειρά μεγέθους 0,

636
00:52:27,440 --> 00:52:30,030
που πιθανώς να θέλετε να σταματήσει σε κάποιο σημείο,

637
00:52:30,030 --> 00:52:33,610
έτσι μπορούμε να πούμε μόνο μέγεθος μικρότερο από 2 ή μικρότερη από ή ίση με 1

638
00:52:33,610 --> 00:52:37,150
έτσι ώστε αυτό θα λειτουργήσει για οποιαδήποτε συστοιχία τώρα.

639
00:52:37,150 --> 00:52:38,870
Εντάξει.

640
00:52:38,870 --> 00:52:42,740
Έτσι, αυτό είναι βασική περίπτωση μας.

641
00:52:42,740 --> 00:52:45,950
Τώρα θέλετε να μας καθοδηγήσει συγχώνευση;

642
00:52:45,950 --> 00:52:49,140
Τι σημαίνουν όλες αυτές οι περιπτώσεις;

643
00:52:49,140 --> 00:52:54,480
Μέχρι εδώ, κάνουμε ακριβώς την ίδια ιδέα, η -

644
00:52:56,970 --> 00:53:02,470
[Φοιτητής] θα πρέπει να περνούν το μέγεθος με όλες τις κλήσεις mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Πρόσθεσα μέγεθος ως πρόσθετη πρωτοβάθμιας και δεν υπάρχει, όπως το μέγεθος / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Ω, μέγεθος / 2, το μέγεθος / 2. >> [Μαθητής] Ναι, και επίσης στην ανωτέρω λειτουργία, καθώς και.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Εδώ; >> [Φοιτητής] Απλά μέγεθος. >> [Bowden] Αχ. Μέγεθος, το μέγεθος; >> [Φοιτητής] Ναι.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Εντάξει.

649
00:53:23,010 --> 00:53:26,580
Επιτρέψτε μου να σκεφτούμε για ένα δευτερόλεπτο.

650
00:53:26,580 --> 00:53:28,780
Έχουμε τρέξει σε ένα θέμα;

651
00:53:28,780 --> 00:53:33,690
Είμαστε θεραπεία πάντα το αριστερό ως 0. >> [Φοιτητής] Όχι.

652
00:53:33,690 --> 00:53:36,340
Αυτό είναι πολύ λάθος. Λυπάμαι. Θα πρέπει να είναι εκκίνηση. Ναι.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Εντάξει. Μου αρέσει ότι η καλύτερη.

654
00:53:39,230 --> 00:53:43,880
Και τέλος. Εντάξει.

655
00:53:43,880 --> 00:53:47,200
Έτσι, τώρα θέλετε να μας καθοδηγήσει συγχώνευση; >> [Φοιτητής] Εντάξει.

656
00:53:47,200 --> 00:53:52,150
Είμαι απλά περπατώντας μέσα από αυτή τη νέα σειρά που έχω δημιουργήσει.

657
00:53:52,150 --> 00:53:57,420
Το μέγεθός του είναι το μέγεθος του τμήματος της συστοιχίας που θέλουμε να ταξινόμηση

658
00:53:57,420 --> 00:54:03,460
και προσπαθεί να βρει το στοιχείο που θα πρέπει να τεθούν σε νέα σειρά βήμα.

659
00:54:03,460 --> 00:54:10,140
Έτσι, για να γίνει αυτό, πρώτα Φεύγω αν το αριστερό μισό του πίνακα εξακολουθεί να έχει κάποια περισσότερα στοιχεία,

660
00:54:10,140 --> 00:54:14,260
και αν δεν το κάνει, τότε θα πάει κάτω σε αυτό το άλλο όρο, που λέει ακριβώς

661
00:54:14,260 --> 00:54:20,180
εντάξει, πρέπει να είναι στη σωστή σειρά, και θα βάλουμε ότι στην τρέχουσα δείκτη του newArray.

662
00:54:20,180 --> 00:54:27,620
>> Και στη συνέχεια, αλλιώς, Φεύγω εάν η δεξιά πλευρά του πίνακα είναι επίσης τελειώσει,

663
00:54:27,620 --> 00:54:30,630
οπότε εγώ απλά βάλτε στο αριστερό.

664
00:54:30,630 --> 00:54:34,180
Αυτό δεν θα μπορούσε πράγματι να είναι απαραίτητη. Δεν είμαι σίγουρος.

665
00:54:34,180 --> 00:54:40,970
Αλλά έτσι κι αλλιώς, οι άλλες δύο επιταγή ποια από τις δύο είναι μικρότερα στην αριστερή ή τη δεξιά.

666
00:54:40,970 --> 00:54:49,770
Και επίσης, σε κάθε περίπτωση, είμαι προσαύξηση ανάλογα με το ποια θα αυξήσετε κράτησης θέσης.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Εντάξει.

668
00:54:52,040 --> 00:54:53,840
Αυτό φαίνεται καλό.

669
00:54:53,840 --> 00:54:58,800
Υπάρχει κάποιος που έχει τα σχόλια ή ανησυχίες ή ερωτήσεις;

670
00:55:00,660 --> 00:55:07,720
Έτσι, οι τέσσερις περιπτώσεις που έχουμε να φέρει τα πράγματα σε λίγο είναι - ή θα μοιάζει με πέντε -

671
00:55:07,720 --> 00:55:13,100
αλλά θα πρέπει να εξετάσει κατά πόσον η αριστερή παράταξη έχει εξαντληθεί τα πράγματα που πρέπει να συγχωνευθούν,

672
00:55:13,100 --> 00:55:16,390
αν η δεξιά διάταξη έχει εξαντληθεί τα πράγματα που πρέπει να συγχωνευθούν -

673
00:55:16,390 --> 00:55:18,400
Είμαι δείχνει σε τίποτα.

674
00:55:18,400 --> 00:55:21,730
Έτσι, αν η αριστερή παράταξη έχει εξαντληθεί τα πράγματα ή η δεξιά διάταξη έχει εξαντληθεί τα πράγματα.

675
00:55:21,730 --> 00:55:24,320
Πρόκειται για δύο περιπτώσεις.

676
00:55:24,320 --> 00:55:30,920
Χρειαζόμαστε επίσης την τετριμμένη περίπτωση του αν η αριστερά πράγμα είναι λιγότερο από ό, τι το σωστό πράγμα.

677
00:55:30,920 --> 00:55:33,910
Στη συνέχεια, θέλουμε να επιλέξετε το αριστερό πράγμα.

678
00:55:33,910 --> 00:55:37,630
Αυτοί είναι οι περιπτώσεις.

679
00:55:37,630 --> 00:55:40,990
Έτσι, αυτό ήταν σωστό, έτσι ώστε να είναι αυτό.

680
00:55:40,990 --> 00:55:46,760
Array αριστερά. Είναι 1, 2, 3. Εντάξει. Οπότε ναι, αυτά είναι τα τέσσερα πράγματα που ίσως να θέλετε να το κάνετε.

681
00:55:50,350 --> 00:55:54,510
Και εμείς δεν θα πάει πέρα ​​από μια επαναληπτική λύση.

682
00:55:54,510 --> 00:55:55,980
Δεν θα συνιστούσα -

683
00:55:55,980 --> 00:56:03,070
Συγχώνευση είδος είναι ένα παράδειγμα μιας συνάρτησης που είναι και οι δύο δεν ουρά αναδρομικό

684
00:56:03,070 --> 00:56:07,040
δεν είναι εύκολο να γίνει ουρά αναδρομικό

685
00:56:07,040 --> 00:56:13,450
αλλά επίσης δεν είναι πολύ εύκολο να γίνει επαναληπτική.

686
00:56:13,450 --> 00:56:16,910
Αυτό είναι πολύ εύκολο.

687
00:56:16,910 --> 00:56:19,170
Αυτό το είδος της εφαρμογής της συγχώνευσης,

688
00:56:19,170 --> 00:56:22,140
συγχώνευση, δεν έχει σημασία τι θα κάνεις, θα πάμε να οικοδομήσουμε συγχώνευση.

689
00:56:22,140 --> 00:56:29,170
>> Έτσι συγχώνευση είδος χτισμένο στην κορυφή της συγχώνευσης είναι αναδρομικά μόνο αυτές οι τρεις γραμμές.

690
00:56:29,170 --> 00:56:34,700
Επαναληπτικά, είναι πιο ενοχλητικό και πιο δύσκολο να σκεφτούμε.

691
00:56:34,700 --> 00:56:41,860
Να σημειωθεί όμως ότι δεν είναι αναδρομική από την ουρά mergeSortHelp - όταν αυτοαποκαλείται -

692
00:56:41,860 --> 00:56:46,590
χρειάζεται ακόμη να κάνουμε τα πράγματα μετά από αυτό επιστρέφει αναδρομική κλήση.

693
00:56:46,590 --> 00:56:50,830
Έτσι, αυτό το πλαίσιο στοίβας πρέπει να συνεχίσει να υπάρχει ακόμα και μετά την κλήση αυτή.

694
00:56:50,830 --> 00:56:54,170
Και στη συνέχεια, όταν σας καλούν αυτό, το πλαίσιο στοίβας πρέπει να συνεχίσει να υπάρχει

695
00:56:54,170 --> 00:56:57,780
γιατί ακόμα και μετά από αυτή την κλήση, θα πρέπει ακόμα να συγχωνευθούν.

696
00:56:57,780 --> 00:57:01,920
Και αυτό είναι προβληματικό να κάνουν αυτό το αναδρομικό ουρά.

697
00:57:04,070 --> 00:57:06,270
Ερωτήσεις;

698
00:57:08,300 --> 00:57:09,860
Εντάξει.

699
00:57:09,860 --> 00:57:13,400
Έτσι, πηγαίνει πίσω για να ταξινομήσετε - ω, υπάρχουν δύο πράγματα που θέλω να δείξω. Εντάξει.

700
00:57:13,400 --> 00:57:17,840
Πηγαίνοντας πίσω στο είδος, θα το κάνετε αυτό γρήγορα.

701
00:57:17,840 --> 00:57:21,030
'Η ψάξτε. Ταξινόμηση; Ταξινόμηση. Ναι.

702
00:57:21,030 --> 00:57:22,730
Πηγαίνοντας πίσω στις απαρχές του είδους.

703
00:57:22,730 --> 00:57:29,870
Θέλουμε να δημιουργήσουμε έναν αλγόριθμο που ταξινομεί το array χρησιμοποιώντας οποιοδήποτε αλγόριθμο

704
00:57:29,870 --> 00:57:33,660
O από το n.

705
00:57:33,660 --> 00:57:40,860
Λοιπόν, πώς είναι αυτό δυνατόν; Υπάρχει κάποιος που να έχει οποιοδήποτε είδος του -

706
00:57:40,860 --> 00:57:44,300
I υπαινίχθηκε πριν σε -

707
00:57:44,300 --> 00:57:48,300
Αν είμαστε έτοιμοι να βελτιωθεί από n log n Ξ της n,

708
00:57:48,300 --> 00:57:51,450
έχουμε βελτιώσει τον αλγόριθμο μας χρόνος-σοφός,

709
00:57:51,450 --> 00:57:55,250
πράγμα που σημαίνει τι πρόκειται να πρέπει να κάνουμε για να αναπληρώσετε αυτό;

710
00:57:55,250 --> 00:57:59,520
[Φοιτητής] Space. Ναι >>. Εμείς πάμε για να χρησιμοποιεί περισσότερο χώρο.

711
00:57:59,520 --> 00:58:04,490
Και δεν είναι καν μόνο περισσότερο χώρο, είναι εκθετικά περισσότερο χώρο.

712
00:58:04,490 --> 00:58:14,320
Νομίζω λοιπόν ότι αυτό το είδος του αλγορίθμου είναι ψευδο κάτι, polynom ψευδο -

713
00:58:14,320 --> 00:58:18,980
ψευδο - Δεν μπορώ να θυμηθώ. Ψευδο κάτι.

714
00:58:18,980 --> 00:58:22,210
Αλλά αυτό συμβαίνει γιατί πρέπει να χρησιμοποιήσουμε τόσο πολύ χώρο

715
00:58:22,210 --> 00:58:28,610
ότι αυτό είναι εφικτό, αλλά δεν είναι ρεαλιστικό.

716
00:58:28,610 --> 00:58:31,220
>> Και πώς θα επιτευχθεί αυτό;

717
00:58:31,220 --> 00:58:36,810
Μπορούμε να το επιτύχουμε αυτό, αν εγγυόμαστε ότι κάποιο συγκεκριμένο στοιχείο του πίνακα

718
00:58:36,810 --> 00:58:39,600
είναι κάτω από ένα ορισμένο μέγεθος.

719
00:58:42,070 --> 00:58:44,500
Έτσι, ας πούμε ότι το μέγεθος είναι 200,

720
00:58:44,500 --> 00:58:48,130
κάθε στοιχείο σε μία συστοιχία είναι κάτω από το μέγεθος 200.

721
00:58:48,130 --> 00:58:51,080
Και αυτό είναι πραγματικά πολύ ρεαλιστικό.

722
00:58:51,080 --> 00:58:58,660
Μπορείτε πολύ εύκολα να έχουν μια σειρά που ξέρετε τα πάντα σε αυτό

723
00:58:58,660 --> 00:59:00,570
πρόκειται να είναι μικρότερη από κάποιο αριθμό.

724
00:59:00,570 --> 00:59:07,400
Όπως και αν έχετε κάποια απολύτως μαζική φορέα ή κάτι

725
00:59:07,400 --> 00:59:11,810
αλλά ξέρετε τα πάντα πρόκειται να είναι μεταξύ 0 και 5,

726
00:59:11,810 --> 00:59:14,790
τότε πρόκειται να είναι πολύ πιο γρήγορα για να γίνει αυτό.

727
00:59:14,790 --> 00:59:17,930
Και η δεσμευμένη σε οποιοδήποτε από τα στοιχεία είναι 5,

728
00:59:17,930 --> 00:59:21,980
έτσι αυτό δεσμεύεται, δηλαδή πόση μνήμη θα πάμε να χρησιμοποιούν.

729
00:59:21,980 --> 00:59:26,300
Έτσι, το όριο είναι 200.

730
00:59:26,300 --> 00:59:32,960
Στη θεωρία υπάρχει πάντα ένα δεσμευμένο αφού ένας ακέραιος μπορεί να είναι μόνο μέχρι 4 δισεκατομμύρια,

731
00:59:32,960 --> 00:59:40,600
αλλά αυτό είναι ρεαλιστικό δεδομένου ότι τότε θα ήμασταν χρήση χώρου

732
00:59:40,600 --> 00:59:44,400
της τάξης των 4 δισ. ευρώ. Έτσι, αυτό είναι εξωπραγματικό.

733
00:59:44,400 --> 00:59:47,060
Αλλά εδώ θα σας πούμε δεσμεύεται μας είναι 200.

734
00:59:47,060 --> 00:59:59,570
Το τέχνασμα για να το κάνουμε σε n Ξ είναι να κάνουμε μια άλλη σειρά που ονομάζεται Η ΔΕΣΜΕΥΣΗ του μεγέθους.

735
00:59:59,570 --> 01:00:10,470
Έτσι, στην πραγματικότητα, αυτό είναι μια συντόμευση για - Εγώ πραγματικά δεν ξέρω αν Clang το κάνει αυτό.

736
01:00:11,150 --> 01:00:15,330
Αλλά στο GCC τουλάχιστον - I'm Clang υποθέτοντας ότι κάνει πάρα πολύ -

737
01:00:15,330 --> 01:00:18,180
αυτό θα προετοιμαστεί μόνο ολόκληρη τη συστοιχία να είναι 0s.

738
01:00:18,180 --> 01:00:25,320
Έτσι, αν δεν θέλω να το κάνω αυτό, τότε θα μπορούσα να κάνω χωριστά για (int i = 0?

739
01:00:25,320 --> 01:00:31,500
i <BOUND? i + +) και Η [i] = 0?

740
01:00:31,500 --> 01:00:35,260
Μέχρι τώρα όλα είναι αρχικοποιείται σε 0.

741
01:00:35,260 --> 01:00:39,570
Έχω επαναλάβει κατά σειρά μου,

742
01:00:39,570 --> 01:00:51,920
και αυτό που κάνω εγώ είναι μετρώντας τον αριθμό των κάθε - Ας πάμε εδώ κάτω.

743
01:00:51,920 --> 01:00:55,480
Έχουμε 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Τι είμαι καταμέτρηση είναι ο αριθμός των εμφανίσεων του καθενός από αυτά τα στοιχεία.

745
01:01:00,010 --> 01:01:03,470
Ας πραγματικά να προσθέσει ένα ζευγάρι περισσότερο εδώ με μερικές επαναλήψεις.

746
01:01:03,470 --> 01:01:11,070
Έτσι, η αξία που έχουμε εδώ, η αξία της θα είναι array [i].

747
01:01:11,070 --> 01:01:14,850
Έτσι val θα μπορούσε να είναι 4 ή 8 ή οτιδήποτε άλλο.

748
01:01:14,850 --> 01:01:18,870
Και τώρα είμαι μετρώντας πόσα από αυτή την τιμή που έχω δει,

749
01:01:18,870 --> 01:01:21,230
Η ούτως [val] + +?

750
01:01:21,230 --> 01:01:29,430
Αφού γίνει αυτό, Η πρόκειται να δούμε κάτι σαν 0001.

751
01:01:29,430 --> 01:01:42,190
Ας κάνουμε Η [val] - BOUND + 1.

752
01:01:42,190 --> 01:01:48,230
>> Τώρα αυτό είναι μόνο να λογοδοτήσουν για το γεγονός ότι είμαστε ξεκινώντας από το 0.

753
01:01:48,230 --> 01:01:50,850
Έτσι, εάν 200 πρόκειται να είναι μεγαλύτερο αριθμό μας,

754
01:01:50,850 --> 01:01:54,720
τότε 0-200 είναι 201 πράγματα.

755
01:01:54,720 --> 01:02:01,540
Η Οπότε, αυτό θα μοιάζει 00001, γιατί έχουμε ένα 4.

756
01:02:01,540 --> 01:02:10,210
Τότε θα έχουμε 0001, όπου θα έχουμε ένα 1 στο 8ο δείκτη του αριθμού.

757
01:02:10,210 --> 01:02:14,560
Θα έχει 2 στην 23η δείκτη του αριθμού.

758
01:02:14,560 --> 01:02:17,630
Θα έχουμε ένα 2 στο δείκτη 42η μετράνε.

759
01:02:17,630 --> 01:02:21,670
Έτσι, μπορούμε να χρησιμοποιήσουμε μετράνε.

760
01:02:34,270 --> 01:02:44,920
Έτσι num_of_item = Η [i].

761
01:02:44,920 --> 01:02:52,540
Και έτσι αν num_of_item είναι 2, αυτό σημαίνει ότι θέλουμε να εισάγετε 2 του αριθμού i

762
01:02:52,540 --> 01:02:55,290
ταξινομημένο σε σειρά μας.

763
01:02:55,290 --> 01:03:02,000
Γι 'αυτό και πρέπει να παρακολουθείτε πόσο μακριά είμαστε στη σειρά.

764
01:03:02,000 --> 01:03:05,470
Έτσι δείκτης = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Θα γράψω απλά.

766
01:03:16,660 --> 01:03:18,020
Μετρά -

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i?

768
01:03:28,580 --> 01:03:32,490
Είναι αυτό που θέλω; Νομίζω ότι είναι αυτό που θέλω.

769
01:03:35,100 --> 01:03:38,290
Ναι, αυτό φαίνεται καλό. Εντάξει.

770
01:03:38,290 --> 01:03:43,050
Έτσι, ο καθένας έχει καταλάβει ποιος είναι ο σκοπός του Η σειρά μου είναι;

771
01:03:43,050 --> 01:03:48,140
Είναι μετρώντας τον αριθμό των εμφανίσεων καθενός από αυτούς τους αριθμούς.

772
01:03:48,140 --> 01:03:51,780
Στη συνέχεια, είμαι πάνω από την επανάληψη αυτού του πίνακα Η,

773
01:03:51,780 --> 01:03:57,190
και η i-θέση στη συστοιχία Η

774
01:03:57,190 --> 01:04:01,930
είναι ο αριθμός του i είναι που θα πρέπει να εμφανίζονται σε ταξινομημένη σειρά μου.

775
01:04:01,930 --> 01:04:06,840
Γι 'Η από 4 πρόκειται να είναι 1

776
01:04:06,840 --> 01:04:11,840
Η και από 8 πρόκειται να είναι 1, Η από 23 θα είναι 2.

777
01:04:11,840 --> 01:04:16,900
Έτσι, αυτό είναι το πώς πολλοί από αυτούς θέλω να εισαγάγει ταξινομημένο σειρά μου.

778
01:04:16,900 --> 01:04:19,200
Στη συνέχεια, εγώ απλά κάνω αυτό.

779
01:04:19,200 --> 01:04:28,960
Είμαι εισαγωγή num_of_item i είναι ταξινομημένο σε σειρά μου.

780
01:04:28,960 --> 01:04:31,670
>> Ερωτήσεις;

781
01:04:32,460 --> 01:04:43,100
Και έτσι πάλι, αυτό είναι γραμμικό χρόνο από τη στιγμή που είναι ακριβώς πάνω από την επανάληψη αυτή τη φορά,

782
01:04:43,100 --> 01:04:47,470
αλλά είναι επίσης γραμμική σε ό, τι ο αριθμός αυτός τυχαίνει να είναι,

783
01:04:47,470 --> 01:04:50,730
και γι 'αυτό εξαρτάται σε μεγάλο βαθμό από το τι σας είναι συνδεδεμένη.

784
01:04:50,730 --> 01:04:53,290
Με δεσμεύεται από 200, αυτό δεν είναι τόσο άσχημα.

785
01:04:53,290 --> 01:04:58,330
Αν δεσμευμένο σας πρόκειται να είναι 10.000, τότε αυτό είναι λίγο χειρότερα,

786
01:04:58,330 --> 01:05:01,360
αλλά αν δεσμεύεται σας πρόκειται να είναι 4 δισ. ευρώ, αυτό είναι τελείως ρεαλιστικό

787
01:05:01,360 --> 01:05:07,720
και αυτή η σειρά θα πρέπει να είναι μεγέθους 4 δισ. ευρώ, το οποίο δεν είναι ρεαλιστικό.

788
01:05:07,720 --> 01:05:10,860
Έτσι αυτό είναι αυτό. Ερωτήσεις;

789
01:05:10,860 --> 01:05:13,270
[Ακούγεται ανταπόκριση των φοιτητών] >> Εντάξει.

790
01:05:13,270 --> 01:05:15,710
Κατάλαβα ένα άλλο πράγμα, όταν πηγαίναμε κατευθείαν.

791
01:05:17,980 --> 01:05:23,720
Νομίζω ότι το πρόβλημα ήταν του Lucas και πιθανώς κάθε ένα που έχουμε δει.

792
01:05:23,720 --> 01:05:26,330
Ξέχασα εντελώς.

793
01:05:26,330 --> 01:05:31,040
Το μόνο πράγμα που ήθελα να σχολιάσω είναι ότι όταν έχουμε να κάνουμε με πράγματα όπως δείκτες,

794
01:05:31,040 --> 01:05:38,320
δεν μπορείτε ποτέ πραγματικά να δείτε αυτό όταν είστε γραπτώς μια για βρόχο,

795
01:05:38,320 --> 01:05:41,120
αλλά τεχνικά, όταν έχουμε να κάνουμε με αυτούς τους δείκτες,

796
01:05:41,120 --> 01:05:45,950
θα πρέπει να είναι πάντα λίγο πολύ ασχολούνται με μη προσημασμένους ακεραίους.

797
01:05:45,950 --> 01:05:53,850
Ο λόγος για αυτό είναι όταν έχεις να κάνεις με υπογραφή ακέραιοι,

798
01:05:53,850 --> 01:05:56,090
οπότε αν έχετε 2 υπογράψει ακέραιοι και τα προσθέτετε μαζί

799
01:05:56,090 --> 01:06:00,640
και καταλήγουν πάρα πολύ μεγάλο, τότε θα καταλήξετε με έναν αρνητικό αριθμό.

800
01:06:00,640 --> 01:06:03,410
Έτσι, αυτό είναι ό, τι είναι ακέραιος υπερχείλιση.

801
01:06:03,410 --> 01:06:10,500
>> Αν μπορώ να προσθέσω 2 δισεκατομμυρίων και 1 δισ. ευρώ, θα καταλήξετε με αρνητικό 1 δισ. ευρώ.

802
01:06:10,500 --> 01:06:15,480
Αυτό είναι το πώς ακέραιοι λειτουργεί σε υπολογιστές.

803
01:06:15,480 --> 01:06:17,510
Έτσι, το πρόβλημα με τη χρήση -

804
01:06:17,510 --> 01:06:23,500
Αυτό είναι πρόστιμο, εκτός αν χαμηλό συμβαίνει να είναι 2 δις και μέχρι να συμβεί αυτό είναι 1 δισ. ευρώ,

805
01:06:23,500 --> 01:06:27,120
τότε αυτό θα είναι αρνητική 1 δισ. ευρώ και στη συνέχεια θα πάμε να τα διαιρέσουμε με το 2

806
01:06:27,120 --> 01:06:29,730
και καταλήγουν με αρνητική 500 εκατ. ευρώ.

807
01:06:29,730 --> 01:06:33,760
Έτσι, αυτό είναι μόνο ένα θέμα, αν τυχαίνει να ψάχνουν μέσα από μια σειρά

808
01:06:33,760 --> 01:06:38,070
δισεκατομμύρια των πραγμάτων.

809
01:06:38,070 --> 01:06:44,050
Αλλά αν συμβεί + χαμηλή έως υπερχείλιση, τότε αυτό είναι ένα πρόβλημα.

810
01:06:44,050 --> 01:06:47,750
Μόλις κάνουμε τους ανυπόγραφο, στη συνέχεια, 2 δισεκατομμύρια συν 1 δισεκατομμύριο 3 δισ. ευρώ.

811
01:06:47,750 --> 01:06:51,960
3 δισεκατομμύρια διαιρούμενο δια του 2 είναι 1,5 δισ. ευρώ.

812
01:06:51,960 --> 01:06:55,670
Έτσι, από τη στιγμή που είσαι ανυπόγραφο, όλα είναι τέλεια.

813
01:06:55,670 --> 01:06:59,900
Και έτσι αυτό είναι επίσης ένα θέμα όταν είστε γραπτώς σας για βρόχους,

814
01:06:59,900 --> 01:07:03,940
και στην πραγματικότητα, κάνει πιθανώς αυτόματα.

815
01:07:09,130 --> 01:07:12,330
Θα πραγματικά φωνάζω μόνο σε σας.

816
01:07:12,330 --> 01:07:21,610
Έτσι, αν ο αριθμός αυτός είναι πολύ μεγάλο για να είναι μέσα σε μόλις έναν ακέραιο, αλλά θα ταίριαζε σε ένα ανυπόγραφο ακέραιος,

817
01:07:21,610 --> 01:07:24,970
θα φωνάζω σε σας, έτσι ώστε να είναι γιατί ποτέ δεν θα τρέξει σε πραγματικά το θέμα.

818
01:07:29,150 --> 01:07:34,820
Μπορείτε να δείτε ότι ο δείκτης δεν πρόκειται ποτέ να είναι αρνητική,

819
01:07:34,820 --> 01:07:39,220
και έτσι όταν είστε επανάληψη πάνω από έναν πίνακα,

820
01:07:39,220 --> 01:07:43,970
μπορείτε σχεδόν πάντα λένε unsigned int i, αλλά πραγματικά δεν χρειάζεται να.

821
01:07:43,970 --> 01:07:47,110
Τα πράγματα πηγαίνουν να εργαστούν λίγο πολύ το ίδιο καλά.

822
01:07:48,740 --> 01:07:50,090
Εντάξει. [Ψίθυροι] Τι ώρα είναι;

823
01:07:50,090 --> 01:07:54,020
Το τελευταίο πράγμα που ήθελα να δείξω - και εγώ θα κάνω μόνο αυτό πραγματικά γρήγορα.

824
01:07:54,020 --> 01:08:03,190
Ξέρεις πώς έχουμε # define έτσι μπορούμε να ορίσουμε ως MAX # 5 ή κάτι άλλο;

825
01:08:03,190 --> 01:08:05,940
Ας μην κάνουμε MAX. # Define δεσμεύονται ως 200. Αυτό είναι ό, τι κάναμε πριν.

826
01:08:05,940 --> 01:08:10,380
Που καθορίζει μια σταθερή, το οποίο είναι ακριβώς πρόκειται να αντιγραφεί και επικολληθεί

827
01:08:10,380 --> 01:08:13,010
όπου τυχαίνει να γράψει ΔΕΣΜΕΥΣΗ.

828
01:08:13,010 --> 01:08:18,189
>> Έτσι, μπορούμε να κάνουμε στην πραγματικότητα περισσότερο με # ορίζει.

829
01:08:18,189 --> 01:08:21,170
Μπορούμε να ορίσουμε # λειτουργίες.

830
01:08:21,170 --> 01:08:23,410
Δεν είναι πραγματικά λειτουργίες, αλλά θα καλέσει τους λειτουργίες.

831
01:08:23,410 --> 01:08:36,000
Ένα παράδειγμα θα ήταν κάτι σαν MAX (x, y) ορίζεται ως (χ <y y:? X). Εντάξει.

832
01:08:36,000 --> 01:08:40,660
Έτσι, θα πρέπει να συνηθίσουν στην τριμερή σύνταξη του τελεστή,

833
01:08:40,660 --> 01:08:49,029
αλλά είναι μικρότερη από χ y; Επιστροφή y, x επιστρέψουν άλλο.

834
01:08:49,029 --> 01:08:54,390
Έτσι, μπορείτε να δείτε μπορείτε να κάνετε αυτό μια ξεχωριστή λειτουργία,

835
01:08:54,390 --> 01:09:01,399
και η λειτουργία θα μπορούσε να είναι όπως bool MAX διαρκεί 2 επιχειρήματα, επιστρέφει αυτό.

836
01:09:01,399 --> 01:09:08,340
Αυτό είναι ένα από τα πιο κοινά βλέπω γίνει σαν αυτό. Καλούμε τους μακροεντολές.

837
01:09:08,340 --> 01:09:11,790
Αυτή είναι μια μακροεντολή.

838
01:09:11,790 --> 01:09:15,859
Αυτό είναι μόνο η σύνταξη γι 'αυτό.

839
01:09:15,859 --> 01:09:18,740
Μπορείτε να γράψετε μια μακροεντολή για να κάνετε ό, τι θέλετε.

840
01:09:18,740 --> 01:09:22,649
Βλέπετε συχνά μακροεντολές για τον εντοπισμό σφαλμάτων και printfs πράγματα.

841
01:09:22,649 --> 01:09:29,410
Έτσι, ένα είδος printf, υπάρχουν ειδικές σταθερές σε C, όπως υπογραμμίζουν LINE υπογραμμίζουν,

842
01:09:29,410 --> 01:09:31,710
2 υπογραμμίζει LINE υπογραμμίζουν,

843
01:09:31,710 --> 01:09:37,550
και υπάρχει επίσης νομίζω 2 υπογραμμίζει FUNC. Αυτό θα μπορούσε να είναι αυτό. Κάτι σαν αυτό.

844
01:09:37,550 --> 01:09:40,880
Αυτά τα πράγματα θα αντικατασταθεί με το όνομα της συνάρτησης

845
01:09:40,880 --> 01:09:42,930
ή ο αριθμός της γραμμής που βρίσκεστε.

846
01:09:42,930 --> 01:09:48,630
Συχνά, μπορείτε να γράψετε τον εντοπισμό σφαλμάτων printfs ότι εδώ κάτω θα μπορούσα να γράψω στη συνέχεια, μόλις

847
01:09:48,630 --> 01:09:54,260
DEBUG και θα εκτυπώσει τον αριθμό της γραμμής και τη λειτουργία που τυχαίνει να είναι σε

848
01:09:54,260 --> 01:09:57,020
ότι αντιμετώπισε τη δήλωση DEBUG.

849
01:09:57,020 --> 01:09:59,550
Και μπορείτε επίσης να εκτυπώσετε άλλα πράγματα.

850
01:09:59,550 --> 01:10:05,990
Έτσι, ένα πράγμα που πρέπει να προσέξετε είναι αν τυχαίνει να καθορίσει # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
ως κάτι σαν 2 * y και x 2 *.

852
01:10:11,380 --> 01:10:14,310
Έτσι, για λόγους οτιδήποτε άλλο, τυχαίνει να το κάνουμε αυτό πολύ.

853
01:10:14,310 --> 01:10:16,650
Έτσι, βεβαιωθείτε ότι μια μακροεντολή.

854
01:10:16,650 --> 01:10:18,680
Αυτό είναι στην πραγματικότητα σπάσει.

855
01:10:18,680 --> 01:10:23,050
Θα ήθελα να το αποκαλούν κάνοντας κάτι σαν DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Λοιπόν, τι πρέπει να επιστραφεί;

857
01:10:28,840 --> 01:10:30,580
[Φοιτητής] 12.

858
01:10:30,580 --> 01:10:34,800
Ναι, 12 θα πρέπει να επιστραφούν, και 12 επιστρέφεται.

859
01:10:34,800 --> 01:10:43,350
3 παίρνει αντικατασταθεί για χ, 6 παίρνει αντικαθίσταται για y, και επιστρέφουμε 2 * 6, η οποία είναι 12.

860
01:10:43,350 --> 01:10:47,710
Τώρα τι γίνεται με αυτό; Τι θα πρέπει να επιστραφούν;

861
01:10:47,710 --> 01:10:50,330
[Φοιτητής] 14. >> Ιδανικά, 14.

862
01:10:50,330 --> 01:10:55,290
Το θέμα είναι ότι το πώς ορίζει την εργασία του κατακερματισμού, να θυμάστε ότι είναι μια κυριολεκτική αντιγραφή και επικόλληση

863
01:10:55,290 --> 01:11:00,160
του σχεδόν τα πάντα, έτσι ώστε ό, τι αυτό θα πρέπει να ερμηνευθεί ως

864
01:11:00,160 --> 01:11:11,270
3 είναι μικρότερη από 1 συν 6, 2 φορές 1 συν 6, 2 φορές 3.

865
01:11:11,270 --> 01:11:19,780
>> Έτσι, για το λόγο αυτό σχεδόν πάντα τυλίξτε τα πάντα σε παρένθεση.

866
01:11:22,180 --> 01:11:25,050
Κάθε μεταβλητή που σχεδόν πάντα τυλίγετε σε παρένθεση.

867
01:11:25,050 --> 01:11:29,570
Υπάρχουν περιπτώσεις όπου δεν έχετε να, όπως ξέρω ότι δεν χρειάζεται να το κάνουμε αυτό εδώ

868
01:11:29,570 --> 01:11:32,110
επειδή λιγότερο από ό, τι είναι λίγο πολύ πάντα ακριβώς πρόκειται να λειτουργήσει,

869
01:11:32,110 --> 01:11:34,330
αν και αυτό δεν θα μπορούσε ακόμη και να είναι αλήθεια.

870
01:11:34,330 --> 01:11:41,870
Αν υπάρχει κάτι γελοίο, όπως DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
τότε που πρόκειται να πάρει αντικατασταθεί με 3 λιγότερο από 1 ισούται ισούται με 2,

872
01:11:49,760 --> 01:11:53,460
και έτσι στη συνέχεια πρόκειται να κάνετε 3 λιγότερο από 1, ότι η ισότητα δεν 2,

873
01:11:53,460 --> 01:11:55,620
το οποίο δεν είναι αυτό που θέλουμε.

874
01:11:55,620 --> 01:12:00,730
Έτσι, προκειμένου να αποτραπούν τυχόν προβλήματα χειριστή προτεραιότητα,

875
01:12:00,730 --> 01:12:02,870
πάντα τυλίγετε σε παρένθεση.

876
01:12:03,290 --> 01:12:07,700
Εντάξει. Και αυτό είναι όλο, 5:30.

877
01:12:08,140 --> 01:12:12,470
Αν έχετε οποιεσδήποτε ερωτήσεις σχετικά με τη PSET, ενημερώστε μας.

878
01:12:12,470 --> 01:12:18,010
Θα πρέπει να είναι διασκέδαση, και η έκδοση χάκερ είναι επίσης πολύ πιο ρεαλιστική

879
01:12:18,010 --> 01:12:22,980
από την έκδοση του χάκερ του περασμένου έτους, έτσι ελπίζουμε ότι πολλοί από εσάς να το δοκιμάσετε.

880
01:12:22,980 --> 01:12:26,460
Πέρυσι ήταν πολύ εντυπωσιακή.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]