1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Συγχώνευση Ταξινόμηση]

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

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

4
00:00:07,000 --> 00:00:09,000
Ας μιλήσουμε για το είδος συγχώνευσης.

5
00:00:09,000 --> 00:00:14,000
Μέχρι στιγμής έχετε δει bubble sort, ταξινόμηση με εισαγωγή, ταξινόμηση και επιλογή.

6
00:00:14,000 --> 00:00:17,000
Αν και εγώ θα το είδος του κύματος το χέρι μου σε ό, τι εννοώ με την καλύτερη,

7
00:00:17,000 --> 00:00:21,000
συγχώνευση είδος εκτελεί γενικά καλύτερα από ό, τι οποιοδήποτε από αυτά τα 3 είδη.

8
00:00:22,000 --> 00:00:27,000
>> Αλλά πριν να μιλάμε για τέτοια συγχώνευση, ας μιλήσουμε για συγχώνευση 2 Ταξινόμηση λίστες.

9
00:00:27,000 --> 00:00:31,000
Θα καλέσετε τη διαδικασία λαμβάνοντας 2 ταξινομημένο καταλόγους, όπως αυτοί,

10
00:00:31,000 --> 00:00:35,000
και κάνοντας μια ενιαία ταξινομημένη λίστα από αυτούς - συγχώνευση των καταλόγων.

11
00:00:35,000 --> 00:00:37,750
Πώς μπορούμε να το κάνουμε αυτό;

12
00:00:37,750 --> 00:00:41,290
Λοιπόν, μια ιδέα είναι να κολλήσει μόνο μια λίστα στο τέλος του άλλου λίστα

13
00:00:41,290 --> 00:00:43,830
ταξινομήσετε και στη συνέχεια το αποτέλεσμα λίστα.

14
00:00:43,830 --> 00:00:47,220
>> Ενώ αυτή η εργασία, είναι μια πολλά περιττά δουλειά.

15
00:00:47,220 --> 00:00:49,900
Μπορούμε να το κάνουμε πιο γρήγορα από ό, τι ακριβώς διαλογή.

16
00:00:49,900 --> 00:00:54,100
Παρατηρήστε ότι ένα λάθος ιδέα είναι να πάρει μόνο εναλλασσόμενο φλιτζάνια από κάθε λίστα.

17
00:00:54,100 --> 00:00:56,460
Ενώ αυτό μπορεί να φαίνεται σαν αυτό λειτουργεί σε πρώτη φάση,

18
00:00:56,460 --> 00:01:05,760
κάνει ότι καταλήγουμε με 4, 8, 15, 23, 16 - ειδοποίηση ότι 16 και 23 είναι εκτός τόπου.

19
00:01:05,760 --> 00:01:09,380
Αυτό οφείλεται στο γεγονός ότι 2 στοιχεία που θα πρέπει να εμφανίζονται διαδοχικά στην νέα λίστα

20
00:01:09,380 --> 00:01:11,720
βρίσκονται στην ίδια αρχικό κατάλογο.

21
00:01:11,720 --> 00:01:14,850
Και οι δύο 15 και 16 βρίσκονται στη λίστα στα αριστερά.

22
00:01:14,850 --> 00:01:19,810
Το κόλπο είναι να επωφεληθούν από το γεγονός ότι και οι δύο λίστες έχουν ήδη ταξινομημένο.

23
00:01:19,810 --> 00:01:23,320
Αυτό σημαίνει ότι αν εξετάσουμε μόνο τα πρώτα στοιχεία των δύο λιστών -

24
00:01:23,320 --> 00:01:29,580
εδώ, 4 και 8 - ένας από αυτούς πρέπει να είναι το πρώτο στοιχείο της νέας λίστας.

25
00:01:29,580 --> 00:01:31,620
Λοιπόν, γιατί συμβαίνει αυτό;

26
00:01:31,620 --> 00:01:33,520
Και οι δύο από αυτές τις λίστες είναι ήδη ταξινομημένο,

27
00:01:33,520 --> 00:01:38,410
και έτσι είτε 4 ή 8 πρέπει να είναι το μικρότερο στοιχείο όταν συνδυάζουμε τις 2 λίστες.

28
00:01:38,410 --> 00:01:41,770
Σε αυτή την περίπτωση, το μικρότερο είναι 4,

29
00:01:41,770 --> 00:01:46,370
έτσι μπορούμε να πάρουμε από 4 και να είναι το πρώτο στοιχείο της νέας λίστας μας.

30
00:01:46,370 --> 00:01:50,710
Τώρα συνεχίζουμε τη συγχώνευση τα υπόλοιπα 3 στοιχεία του πρώτου καταλόγου

31
00:01:50,710 --> 00:01:52,920
και 4 στοιχεία της δεύτερης λίστας.

32
00:01:52,920 --> 00:01:57,150
>> Για άλλη μια φορά, το μόνο που χρειάζεται να δούμε το πρώτο στοιχείο και των δύο καταλόγων.

33
00:01:57,150 --> 00:02:01,060
Το μικρότερο από τα 2 πρέπει να είναι το δεύτερο στοιχείο της νέας λίστας μας.

34
00:02:01,060 --> 00:02:05,440
Αυτή τη φορά, μεταξύ 8 και 15 το μικρότερο είναι 8, και έτσι ώστε εισάγουμε

35
00:02:05,440 --> 00:02:09,240
ως το δεύτερο στοιχείο της ταξινομημένη λίστα μας.

36
00:02:09,240 --> 00:02:12,180
Μπορούμε να συνεχίσουμε συγκρίνοντας τα πρώτα στοιχεία των δύο λιστών

37
00:02:12,180 --> 00:02:14,420
και αφαιρώντας το μικρότερο του 2.

38
00:02:14,420 --> 00:02:19,460
Συγκρίνοντας 15 και 23, 15 και είναι μικρότερη έτσι ώστε το τρίτο στοιχείο μας.

39
00:02:21,000 --> 00:02:23,910
Τώρα συγκρίνοντας 16 και 23, 16 είναι μικρότερη.

40
00:02:23,910 --> 00:02:26,820
Έτσι, αυτό είναι το τέταρτο στοιχείο.

41
00:02:26,820 --> 00:02:30,390
>> Σημειώστε ότι 2 στοιχεία προέρχονται από την ίδια λίστα σε μια σειρά.

42
00:02:30,390 --> 00:02:34,400
Για το λόγο αυτό η νέα λίστα δεν μπορεί απλώς εναλλακτική στοιχεία από τις 2 λίστες.

43
00:02:34,400 --> 00:02:40,020
Συγκρίνοντας 50 και 23, 23 είναι μικρότερη, οπότε η επιλογή του.

44
00:02:40,770 --> 00:02:44,070
Μεταξύ 50 και 42, 42 είναι μικρότερο.

45
00:02:44,070 --> 00:02:48,290
Μεταξύ 50 και 108, 50 είναι μικρότερο.

46
00:02:48,290 --> 00:02:52,330
Και, τέλος, έχουμε μόνο 108, γι 'αυτό πρέπει να πάει στο τέλος της λίστας μας.

47
00:02:53,750 --> 00:02:56,180
Παρατηρήστε ότι έχουμε μια ωραία, ταξινομημένη λίστα.

48
00:02:56,180 --> 00:02:59,040
Κάθε φορά που συγκρίναμε τα πρώτα 2 στοιχεία των πινάκων 2

49
00:02:59,040 --> 00:03:02,730
ήμασταν σε θέση να καθορίσει το επόμενο στοιχείο της νέας λίστας.

50
00:03:02,730 --> 00:03:08,070
Αυτό σημαίνει ότι εάν ο τελικός κατάλογος περιέχει n αριθμούς, όπου η είναι εδώ 8,

51
00:03:08,070 --> 00:03:12,610
τότε χρειαζόμαστε το πολύ n συγκρίσεις για να πάρετε όλα αυτά τα νούμερα στο σωστό μέρος.

52
00:03:13,230 --> 00:03:16,230
Ένας τέτοιος αλγόριθμος λέγεται να τρέχει σε γραμμικό χρόνο,

53
00:03:16,230 --> 00:03:18,090
αλλά μην ανησυχείτε γι 'αυτό εδώ.

54
00:03:18,570 --> 00:03:22,810
>> Χρησιμοποιώντας τον αλγόριθμο μας για τη συγχώνευση, μπορούμε να κάνουμε ένα γρήγορο αλγόριθμο είδος συγχώνευσης.

55
00:03:22,810 --> 00:03:25,170
Έτσι, ας επαναφορά τους καταλόγους μας.

56
00:03:35,210 --> 00:03:37,750
Υπάρχουν 2 μεγάλα βήματα στη διαδικασία της συγχώνευσης είδος.

57
00:03:37,750 --> 00:03:41,500
Κατ 'αρχάς, χωρίζεται συνεχώς τον κατάλογο των κυπέλλων στη μέση

58
00:03:41,500 --> 00:03:44,860
μέχρι να έχουμε ένα σωρό λίστες με μόλις 1 φλιτζάνι σε αυτά.

59
00:03:44,860 --> 00:03:47,350
Μην ανησυχείτε εάν ένας κατάλογος περιέχει ένα μονό αριθμό

60
00:03:47,350 --> 00:03:49,880
και δεν μπορείτε να κάνετε μια απόλυτα καθαρή κοπή μεταξύ τους.

61
00:03:49,880 --> 00:03:53,750
Απλά επιλέξτε αυθαίρετα ποια λίστα να περιλαμβάνει το επιπλέον φλιτζάνι μέσα

62
00:03:53,750 --> 00:03:56,240
Έτσι, ας χωρίσει τους καταλόγους αυτούς.

63
00:03:58,140 --> 00:04:01,310
Τώρα έχουμε 2 λίστες.

64
00:04:04,120 --> 00:04:06,570
Τώρα έχουμε 4 λίστες.

65
00:04:10,350 --> 00:04:13,870
>> Και τώρα έχουμε 8 λίστες με ένα μόνο φλιτζάνι σε κάθε λίστα.

66
00:04:13,870 --> 00:04:16,630
Έτσι, αυτό είναι όλο για το βήμα 1.

67
00:04:16,630 --> 00:04:22,230
Για το βήμα 2, έχουμε επανειλημμένα ζεύγη συγχώνευση των καταλόγων χρησιμοποιώντας τον αλγόριθμο συγχώνευσης μάθαμε πριν.

68
00:04:22,230 --> 00:04:29,160
Συγχώνευση 108 και 15, καταλήγουμε με τον κατάλογο 15, 108.

69
00:04:30,330 --> 00:04:36,250
Συγχώνευση 50 και 4, καταλήγουμε με 4, 50.

70
00:04:36,960 --> 00:04:41,400
Συγχώνευση 8 και 42, καταλήγουμε με 8, 42.

71
00:04:42,790 --> 00:04:48,130
Και τη συγχώνευση 23 και 16, καταλήγουμε με 16, 23.

72
00:04:49,740 --> 00:04:52,450
Τώρα όλες τις λίστες μας είναι το μέγεθος 2.

73
00:04:53,020 --> 00:04:56,180
Παρατηρήστε ότι κάθε ένα από τα 4 καταλόγων είναι ταξινομημένος.

74
00:04:56,180 --> 00:04:59,160
>> Έτσι, μπορούμε να αρχίσουμε τη συγχώνευση ζεύγη των καταλόγων και πάλι.

75
00:04:59,160 --> 00:05:03,240
Συγχωνεύοντας 15 και 108 και 4 και 50 -

76
00:05:03,240 --> 00:05:11,170
πρώτα λάβει το 4, τότε το 15, τότε το 50, τότε το 108.

77
00:05:11,170 --> 00:05:15,120
Συγχωνευόμενες 8, 42 και 16, 23,

78
00:05:15,120 --> 00:05:22,440
πρέπει πρώτα να λάβει τα 8, τότε το 16, τότε το 23, τότε το 42.

79
00:05:22,440 --> 00:05:27,370
Έτσι τώρα έχουμε μόλις 2 καταλόγους μεγέθους 4, καθένα από τα οποία είναι ταξινομημένο.

80
00:05:27,370 --> 00:05:30,980
Έτσι τώρα έχουμε συγχωνεύσει αυτά τα 2 λίστες.

81
00:05:30,980 --> 00:05:33,440
Πρώτα παίρνουμε το 4.

82
00:05:33,440 --> 00:05:36,580
Στη συνέχεια παίρνουμε το 8.

83
00:05:36,580 --> 00:05:50,700
Τότε παίρνουμε το 15 και 16, στη συνέχεια 23, στη συνέχεια 42, 50, στη συνέχεια, στη συνέχεια 108.

84
00:05:50,700 --> 00:05:52,220
Και τελειώσαμε.

85
00:05:52,220 --> 00:05:54,900
Έχουμε τώρα μια ταξινομημένη λίστα.

86
00:05:54,900 --> 00:05:57,890
Έτσι, πόσο γρήγορα ήταν αυτό, ακριβώς;

87
00:05:57,890 --> 00:06:02,000
Σε τεχνικούς όρους, συγχώνευση sort είναι O (n log n),

88
00:06:02,000 --> 00:06:07,380
ενώ όλες του bubble sort, ταξινόμηση με εισαγωγή, ταξινόμηση και επιλογή είναι O (n ²).

89
00:06:07,380 --> 00:06:11,120
Στην πραγματικότητα, όπως θα μάθετε σύντομα, δεν θα είναι σε θέση να καταλήξει σε ένα είδος

90
00:06:11,120 --> 00:06:14,820
που εκτελεί καλύτερα από O (n log n) στη γενική περίπτωση.

91
00:06:14,820 --> 00:06:19,120
Και πάλι, μην ανησυχείτε για αυτό το μεγάλο συμβολισμό O αν δεν το έχετε δει ακόμα.

92
00:06:19,120 --> 00:06:23,490
>> Απλά ξέρω ότι αυτό σημαίνει ότι αν θέλαμε να ταξινομήσετε μια πραγματικά μεγάλη λίστα

93
00:06:23,490 --> 00:06:26,820
bubble sort, ταξινόμηση με εισαγωγή, και η επιλογή του είδους θα μπορούσαν δυνητικά να

94
00:06:26,820 --> 00:06:29,500
σημαντικά μεγαλύτερη από ό, τι είδος συγχώνευσης.

95
00:06:29,500 --> 00:06:33,210
Αυτό δεν σημαίνει ότι η συγχώνευση είδος θα είναι ταχύτερη για όλες τις λίστες

96
00:06:33,210 --> 00:06:36,220
ή ακόμα και για κάθε ενιαίο κατάλογο κάτω από ένα ορισμένο μέγεθος.

97
00:06:36,220 --> 00:06:41,950
Για παράδειγμα, η ταξινόμηση με εισαγωγή μπορεί να είναι η ταχύτερη ταξινόμησης για όλους τους καταλόγους μικρότερα από 5 στοιχεία.

98
00:06:41,950 --> 00:06:47,360
Στην πράξη, συγχώνευση είδος είναι συνήθως πιο γρήγορα για τους καταλόγους τόσο μικρό όσο 50 στοιχεία.

99
00:06:47,360 --> 00:06:51,120
>> Αλλά αυτή η επιπλέον ταχύτητα δεν έρχεται χωρίς μια τιμή.

100
00:06:51,120 --> 00:06:54,770
Σε αντίθεση με άλλα είδη μας, η οποία λαμβάνει μια λίστα και να τροποποιήσετε τη λίστα στη θέση του

101
00:06:54,770 --> 00:06:58,740
μέχρι να πάρετε μια ταξινομημένη λίστα, συγχώνευση είδος χρειάζεται κάποια επιπλέον χώρο

102
00:06:58,740 --> 00:07:00,900
να συγχωνεύσει 2 λίστες μαζί.

103
00:07:00,900 --> 00:07:04,690
Δεν μπορείτε να χρησιμοποιήσετε αμέσως τις λίστες που θα συγχωνευθεί για να αποθηκεύσετε την νέα λίστα

104
00:07:04,690 --> 00:07:08,880
από τη στιγμή που θα μπορούσε να παρακάμψει τα στοιχεία που πρέπει ακόμη να συγχωνευθούν.

105
00:07:08,880 --> 00:07:13,540
Αυτός ο χώρος είναι ένα κομμάτι από μια τιμή, αλλά συνήθως δεν είναι παράλογο.

106
00:07:13,540 --> 00:07:15,330
Και αυτό είναι το είδος για συγχώνευση.

107
00:07:15,330 --> 00:07:18,490
>> Το όνομά μου είναι Rob Bowden, και αυτό είναι CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- Και η επιλογή του είδους.

110
00:07:24,000 --> 00:07:25,880
[Γέλια]

111
00:07:25,880 --> 00:07:31,480
Ω, έχεις να λάβει ότι από πάρα πολύ, επειδή άλλαξα τρόπο με τον οποίο είχα την παρουσίαση.

112
00:07:31,480 --> 00:07:35,680
Κατάλογος για την αριστερά. Αυτό ήταν ένα τυπογραφικό λάθος.

113
00:07:35,680 --> 00:07:39,290
[Έκανε λάθος] σκάτωσα -

114
00:07:39,290 --> 00:07:41,190
[Γέλια]

115
00:07:41,190 --> 00:07:44,190
Δεν ξέρω τι -