1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Έτσι σε CS50 μάθαμε για
μια ποικιλία από διαλογή και την αναζήτηση

3
00:00:08,900 --> 00:00:09,442
αλγορίθμων.

4
00:00:09,442 --> 00:00:11,400
Και μερικές φορές μπορεί να είναι
λίγο δύσκολο να κρατήσει

5
00:00:11,400 --> 00:00:14,161
παρακολουθείτε τι αλγορίθμου κάνει τι.

6
00:00:14,161 --> 00:00:15,910
Έχουμε πραγματικά μόνο
αποκορυφωμένο την επιφάνεια πάρα πολύ,

7
00:00:15,910 --> 00:00:18,740
υπάρχουν πολλά άλλα αναζήτηση
και αλγορίθμων ταξινόμησης.

8
00:00:18,740 --> 00:00:21,780
Έτσι, σε αυτό το βίντεο ας
μόλις πάρει μερικά λεπτά

9
00:00:21,780 --> 00:00:24,980
να προσπαθήσουμε και να μετατρέψει κάθε αλγόριθμο
κάτω στα βασικά στοιχεία της

10
00:00:24,980 --> 00:00:27,810
ώστε να μπορείτε να θυμηθείτε το πιο
Σημαντικές πληροφορίες σχετικά με τους

11
00:00:27,810 --> 00:00:31,970
και να είναι σε θέση να αρθρώσει η
διαφορές, εάν είναι απαραίτητο.

12
00:00:31,970 --> 00:00:34,220
>> Το πρώτο είδος είναι επιλογή.

13
00:00:34,220 --> 00:00:38,210
Η βασική ιδέα πίσω από την επιλογή του είδους
είναι να βρούμε το μικρότερο στοιχείο αδιαχώριστα

14
00:00:38,210 --> 00:00:42,890
σε μια σειρά και να ανταλλάξουν με το
αδιαχώριστα πρώτο στοιχείο του εν λόγω πίνακα.

15
00:00:42,890 --> 00:00:46,620
Είπαμε ότι η χειρότερη περίπτωση
χρόνος λειτουργίας ήταν ότι n τετράγωνο.

16
00:00:46,620 --> 00:00:50,060
Και αν θέλετε να ανακαλέσετε γιατί, να λάβει
Μια ματιά στο βίντεο είδος επιλογής.

17
00:00:50,060 --> 00:00:54,560
Ο χρόνος λειτουργίας καλύτερη περίπτωση
Επίσης n τετράγωνο.

18
00:00:54,560 --> 00:00:58,910
>> Bubble sort, η ιδέα πίσω από αυτό
η μία είναι να ανταλλάξουν γειτονικά ζεύγη.

19
00:00:58,910 --> 00:01:01,730
Έτσι, αυτό είναι το κλειδί που σας βοηθά
θυμηθείτε τη διαφορά εδώ.

20
00:01:01,730 --> 00:01:04,920
Επιλογή sort είναι, μέχρι στιγμής,
βρείτε το smallest-- φούσκα

21
00:01:04,920 --> 00:01:06,790
sort είναι swap δίπλα ζεύγη.

22
00:01:06,790 --> 00:01:08,710
Έχουμε ανταλλάξει γειτονικών ζευγών
των στοιχείων, εφόσον

23
00:01:08,710 --> 00:01:12,530
είναι εκτός λειτουργίας, η οποία αποτελεσματικά
φυσαλίδες μεγαλύτερα στοιχεία προς τα δεξιά,

24
00:01:12,530 --> 00:01:17,060
και συγχρόνως αρχίζει επίσης
να κινηθεί μικρότερα στοιχεία προς τα αριστερά.

25
00:01:17,060 --> 00:01:20,180
Η χειρότερη περίπτωση χρόνος τρέχει περίπτωση
του bubble sort είναι n τετράγωνο.

26
00:01:20,180 --> 00:01:23,476
Ο χρόνος λειτουργίας καλύτερη περίπτωση
του bubble sort είναι n.

27
00:01:23,476 --> 00:01:25,350
Επειδή σε αυτή την κατάσταση
δεν actually--

28
00:01:25,350 --> 00:01:27,141
ίσως να μην χρειάζεται να
προβεί σε ανταλλαγές σε όλα.

29
00:01:27,141 --> 00:01:31,026
Έχουμε μόνο να κάνει ένα
να περάσει σε όλους τους n στοιχεία.

30
00:01:31,026 --> 00:01:34,600
>> Στην ταξινόμηση με εισαγωγή, η
βασική ιδέα εδώ είναι η στροφή.

31
00:01:34,600 --> 00:01:36,630
Αυτή είναι η λέξη-κλειδί για την ταξινόμηση με εισαγωγή.

32
00:01:36,630 --> 00:01:39,630
Εμείς πάμε για να ενισχύσει μια φορά μέσα
η σειρά από τα αριστερά προς τα δεξιά.

33
00:01:39,630 --> 00:01:41,670
Και όπως εμείς, είμαστε
πρόκειται να αλλάξει τα στοιχεία

34
00:01:41,670 --> 00:01:46,260
έχουμε ήδη δει να κάνει χώρο για
μικρότερα που χρειάζεται για να χωρέσει κάπου

35
00:01:46,260 --> 00:01:48,080
πίσω σε εκείνο το τμήμα ταξινομημένο.

36
00:01:48,080 --> 00:01:51,600
Έτσι χτίζουμε τον ταξινομημένο πίνακα ένα
στοιχείο σε έναν χρόνο, αριστερά προς τα δεξιά,

37
00:01:51,600 --> 00:01:54,740
και θα μετακινήσει τα πράγματα για να κάνει χώρο.

38
00:01:54,740 --> 00:01:58,650
Ο χρόνος εκτέλεσης χειρότερης περίπτωσης της
ταξινόμηση με εισαγωγή είναι n τετράγωνο.

39
00:01:58,650 --> 00:02:02,380
Η καλύτερη περίπτωση τρέχει ο χρόνος είναι n.

40
00:02:02,380 --> 00:02:05,380
>> Συγχώνευση sort-- την λέξη-κλειδί
εδώ είναι χωρισμένη και να συγχωνεύσετε.

41
00:02:05,380 --> 00:02:08,949
Έχουμε χωρίσει την πλήρη σειρά, αν
είναι έξι στοιχεία, οκτώ στοιχεία,

42
00:02:08,949 --> 00:02:13,790
10.000 elements-- θα το χωρίσει
προς τα κάτω κατά το ήμισυ, κατά το ήμισυ, κατά το ήμισυ,

43
00:02:13,790 --> 00:02:17,720
μέχρι να έχουμε κάτω πίνακα
ν μια συστοιχίες στοιχείο.

44
00:02:17,720 --> 00:02:19,470
Ένα σύνολο από n μία σειρές στοιχείων.

45
00:02:19,470 --> 00:02:22,640
Έτσι ξεκινήσαμε με ένα
1.000 στοιχείο του πίνακα,

46
00:02:22,640 --> 00:02:26,550
και θα φτάσουμε στο σημείο όπου θα
έχει 1.000 συστοιχίες ένα στοιχείο.

47
00:02:26,550 --> 00:02:30,990
Στη συνέχεια αρχίζουμε να συγχωνεύσει αυτές τις συστοιχίες υπο
πίσω μαζί με τη σωστή σειρά.

48
00:02:30,990 --> 00:02:34,860
Έτσι παίρνουμε δύο συστοιχίες ενός στοιχείου
και να δημιουργήσει μια συστοιχία δύο στοιχείων.

49
00:02:34,860 --> 00:02:38,180
Παίρνουμε δύο συστοιχίες δύο-στοιχείων
και να δημιουργήσει μια συστοιχία τεσσάρων στοιχείων

50
00:02:38,180 --> 00:02:43,900
και ούτω καθεξής και ούτω καθεξής μέχρι να έχουμε
ξαναχτίστηκε και πάλι μια συστοιχία n στοιχείο.

51
00:02:43,900 --> 00:02:48,410
>> Ο χρόνος εκτέλεσης χειρότερης περίπτωσης της
ταξινόμηση με συγχώνευση είναι Ν φορές log n.

52
00:02:48,410 --> 00:02:52,390
Έχουμε n στοιχεία, αλλά
Αυτή η διαδικασία ανασυνδυασμο

53
00:02:52,390 --> 00:02:56,960
παίρνει log n βήματα για να πάρει
πίσω σε μια πλήρη σειρά.

54
00:02:56,960 --> 00:03:01,160
Η καλύτερη περίπτωση τρέχει ο χρόνος είναι επίσης n log
n επειδή η διαδικασία αυτή δεν έχει πραγματικά

55
00:03:01,160 --> 00:03:04,090
με ενδιαφέρει αν ο πίνακας ήταν
ταξινομούνται ή όχι να αρχίσει με.

56
00:03:04,090 --> 00:03:07,590
Η διαδικασία είναι η ίδια, υπάρχει
δεν υπάρχει τρόπος να τα πράγματα σύντομο κύκλωμα.

57
00:03:07,590 --> 00:03:11,610
Έτσι n log n στη χειρότερη περίπτωση,
n log n στην καλύτερη περίπτωση.

58
00:03:11,610 --> 00:03:13,960
>> Μιλήσαμε για δύο
αναζήτηση αλγορίθμων.

59
00:03:13,960 --> 00:03:16,230
Έτσι γραμμική αναζήτηση είναι για την επανάληψη.

60
00:03:16,230 --> 00:03:19,500
Προχωρούμε σε όλη τη σειρά
μία φορά, από αριστερά προς τα δεξιά,

61
00:03:19,500 --> 00:03:21,950
προσπαθούν να βρουν τον αριθμό
ότι ψάχνουμε για.

62
00:03:21,950 --> 00:03:24,550
Η χειρότερη περίπτωση να τρέξει ο χρόνος είναι μεγάλος O Ν.

63
00:03:24,550 --> 00:03:27,610
Θα μπορούσε να μας πάρει την επανάληψη
σε όλη κάθε στοιχείου

64
00:03:27,610 --> 00:03:30,660
για να βρείτε το στοιχείο που ψάχνουμε
για, είτε στην τελευταία θέση,

65
00:03:30,660 --> 00:03:31,630
ή καθόλου.

66
00:03:31,630 --> 00:03:34,720
Αλλά δεν μπορούμε να επιβεβαιώσουμε ότι μέχρι
έχουμε κοίταξε τα πάντα.

67
00:03:34,720 --> 00:03:36,730
m η καλύτερη περίπτωση, θα βρούμε αμέσως.

68
00:03:36,730 --> 00:03:41,060
Ο χρόνος λειτουργίας καλύτερη περίπτωση
γραμμική αναζήτηση είναι ωμέγα 1.

69
00:03:41,060 --> 00:03:43,689
>> Τέλος, υπήρχε δυαδική αναζήτηση,
η οποία απαιτεί ανάμικτες σειρά.

70
00:03:43,689 --> 00:03:45,605
Να θυμάστε ότι είναι μια πολύ
σημαντική παράμετρος

71
00:03:45,605 --> 00:03:47,155
όταν εργάζεστε με δυαδική αναζήτηση.

72
00:03:47,155 --> 00:03:50,180
Είναι μια προϋπόθεση για τη χρήση it--
ο πίνακας που ψάχνετε μέσα

73
00:03:50,180 --> 00:03:52,160
πρέπει να ταξινομηθούν.

74
00:03:52,160 --> 00:03:54,500
Διαφορετικά, η λέξη-κλειδί
είναι διαίρει και βασίλευε.

75
00:03:54,500 --> 00:03:58,310
Χωρίστε τη σειρά σε μισό και
εξαλειφθούν τα μισά από τα στοιχεία

76
00:03:58,310 --> 00:04:00,780
κάθε φορά καθώς προχωράτε μέσα.

77
00:04:00,780 --> 00:04:04,330
Εξαιτίας αυτού του διαίρει και βασίλευε
και διαχωρισμό πράγματα στο μισό προσέγγιση,

78
00:04:04,330 --> 00:04:07,450
το χρόνο εκτέλεσης χειρότερης περίπτωσης
της δυαδικής αναζήτησης είναι

79
00:04:07,450 --> 00:04:11,730
log n, η οποία είναι ουσιαστικά
καλύτερα από ό, n γραμμικά αναζήτησης.

80
00:04:11,730 --> 00:04:13,570
Η καλύτερη περίπτωση τρέχει ο χρόνος είναι ακόμα ένα.

81
00:04:13,570 --> 00:04:17,010
>> Θα μπορούσαμε να το βρείτε αμέσως το
πρώτη φορά που κάνουμε μια διαίρεση, αλλά,

82
00:04:17,010 --> 00:04:19,339
και πάλι, να θυμάστε ότι
αν είναι δυαδική αναζήτηση

83
00:04:19,339 --> 00:04:24,030
σημαντικά καλύτερη από τη γραμμική αναζήτηση
λόγω του ότι είναι log n έναντι n,

84
00:04:24,030 --> 00:04:27,110
ίσως χρειαστεί να περάσει μέσα από το έργο
διαλογής σειρά σας πρώτα, η οποία

85
00:04:27,110 --> 00:04:32,010
θα μπορούσαν να καταστήσουν λιγότερο αποτελεσματική ανάλογα
σχετικά με το μέγεθος της την επανάληψη ταξινομημένο.

86
00:04:32,010 --> 00:04:35,250
>> Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.

87
00:04:35,250 --> 00:04:36,757