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

2
00:00:05,830 --> 00:00:07,910
>> Εντάξει, έτσι, υπολογιστική πολυπλοκότητα.

3
00:00:07,910 --> 00:00:10,430
Ακριβώς ένα κομμάτι της προειδοποίησης
πριν βουτήξει σε πάρα εως τώρα

4
00:00:10,430 --> 00:00:13,070
Αυτό κατά πάσα πιθανότητα θα είναι μεταξύ
Οι πιο μαθηματικά-βαριά πράγματα

5
00:00:13,070 --> 00:00:14,200
μιλάμε για σε CS50.

6
00:00:14,200 --> 00:00:16,950
Ας ελπίσουμε ότι δεν θα είναι πάρα πολύ συντριπτική
και εμείς θα προσπαθήσουμε και να σας καθοδηγήσει

7
00:00:16,950 --> 00:00:19,200
μέσω της διαδικασίας, αλλά
απλά ένα κομμάτι από μια δίκαιη προειδοποίηση.

8
00:00:19,200 --> 00:00:21,282
Υπάρχει ένα μικρό κομμάτι
των μαθηματικών που εμπλέκονται εδώ.

9
00:00:21,282 --> 00:00:23,990
Εντάξει, έτσι ώστε να καταστεί
χρήση των υπολογιστικών πόρων μας

10
00:00:23,990 --> 00:00:28,170
στον πραγματικό world-- είναι πραγματικά
σημαντικό να κατανοήσουμε αλγορίθμων

11
00:00:28,170 --> 00:00:30,750
και πώς να επεξεργάζονται δεδομένα.

12
00:00:30,750 --> 00:00:32,810
Αν έχουμε μια πραγματικά
αποδοτικό αλγόριθμο, μπορούμε

13
00:00:32,810 --> 00:00:36,292
μπορεί να ελαχιστοποιήσει το ποσό των πόρων
έχουμε στη διάθεσή μας για να ασχοληθεί με το θέμα.

14
00:00:36,292 --> 00:00:38,750
Αν έχουμε έναν αλγόριθμο ο οποίος
πρόκειται να πάρει πολλή δουλειά

15
00:00:38,750 --> 00:00:41,210
να επεξεργαστεί ένα πραγματικά
μεγάλο σύνολο των δεδομένων, είναι

16
00:00:41,210 --> 00:00:44,030
θα απαιτήσει περισσότερο
και περισσότερους πόρους, η οποία

17
00:00:44,030 --> 00:00:47,980
είναι τα χρήματα, μνήμη RAM, όλα τα τέτοιου είδους πράγματα.

18
00:00:47,980 --> 00:00:52,090
>> Έτσι, είναι σε θέση να αναλύσει μια
αλγόριθμο χρησιμοποιώντας αυτό το σύνολο εργαλείων,

19
00:00:52,090 --> 00:00:56,110
Βασικά, ζητά από την question--
Πώς αυτό κλίμακας αλγόριθμο

20
00:00:56,110 --> 00:00:59,020
όπως έχουμε ρίξει όλο και περισσότερα δεδομένα σε αυτό;

21
00:00:59,020 --> 00:01:02,220
Σε CS50, το ποσό των δεδομένων που είμαστε
που εργάζονται με είναι αρκετά μικρό.

22
00:01:02,220 --> 00:01:05,140
Σε γενικές γραμμές, τα προγράμματα μας θα
να τρέχει σε ένα δεύτερο ή less--

23
00:01:05,140 --> 00:01:07,830
πιθανώς πολύ λιγότερο
ιδιαίτερα νωρίς.

24
00:01:07,830 --> 00:01:12,250
>> Αλλά σκεφτείτε για μια εταιρεία που ασχολείται
με εκατοντάδες εκατομμύρια πελάτες.

25
00:01:12,250 --> 00:01:14,970
Και πρέπει να επεξεργαστούν
ότι τα δεδομένα των πελατών.

26
00:01:14,970 --> 00:01:18,260
Καθώς ο αριθμός των πελατών που
έχουν παίρνει όλο και μεγαλύτερες,

27
00:01:18,260 --> 00:01:21,230
πρόκειται να απαιτήσει
όλο και περισσότερους πόρους.

28
00:01:21,230 --> 00:01:22,926
Πόσες περισσότερους πόρους;

29
00:01:22,926 --> 00:01:25,050
Λοιπόν, αυτό εξαρτάται από το πόσο
αναλύουμε τον αλγόριθμο,

30
00:01:25,050 --> 00:01:28,097
χρησιμοποιώντας τα εργαλεία της εργαλειοθήκης.

31
00:01:28,097 --> 00:01:31,180
Όταν μιλάμε για την πολυπλοκότητα των
ένα algorithm-- το οποίο μερικές φορές θα

32
00:01:31,180 --> 00:01:34,040
ακούσετε να αναφέρεται ως χρόνος
πολυπλοκότητας ή χωρική πολυπλοκότητα

33
00:01:34,040 --> 00:01:36,190
αλλά είμαστε ακριβώς πρόκειται
να καλέσει complexity--

34
00:01:36,190 --> 00:01:38,770
είμαστε γενικά μιλάμε για
το χειρότερο σενάριο.

35
00:01:38,770 --> 00:01:42,640
Με δεδομένη την απόλυτη χειρότερο σωρός του
στοιχεία που θα μπορούσαν να ρίχνουν σε αυτό,

36
00:01:42,640 --> 00:01:46,440
πώς ο αλγόριθμος αυτός θα
επεξεργάζονται ή να ασχοληθούν με αυτά τα δεδομένα;

37
00:01:46,440 --> 00:01:51,450
Εμείς γενικά ονομάζουμε την χειρότερη περίπτωση
εκτέλεσης ενός αλγορίθμου big-O.

38
00:01:51,450 --> 00:01:56,770
Έτσι, ένας αλγόριθμος θα μπορούσε να ειπωθεί ότι
εκτελείται σε O Ν ή Ο Ν τετράγωνο.

39
00:01:56,770 --> 00:01:59,110
Και περισσότερα για το τι
εκείνων σημαίνει σε ένα δευτερόλεπτο.

40
00:01:59,110 --> 00:02:01,620
>> Μερικές φορές, όμως, κάνουμε φροντίδα
σχετικά με το αισιόδοξο σενάριο.

41
00:02:01,620 --> 00:02:05,400
Εάν τα δεδομένα είναι όλα όσα θέλαμε
να είναι και ήταν απολύτως τέλεια

42
00:02:05,400 --> 00:02:09,630
και μας στέλνει αυτό το τέλειο
το σύνολο των δεδομένων μέσω του αλγορίθμου μας.

43
00:02:09,630 --> 00:02:11,470
Πώς θα το χειριστεί σε αυτήν την κατάσταση;

44
00:02:11,470 --> 00:02:15,050
Εμείς μερικές φορές αναφέρονται σε αυτό ως
big-Omega, τόσο σε αντίθεση με τα μεγάλα-O,

45
00:02:15,050 --> 00:02:16,530
έχουμε μεγάλη-Ωμέγα.

46
00:02:16,530 --> 00:02:18,880
Big-Omega για το καλύτερο σενάριο.

47
00:02:18,880 --> 00:02:21,319
Big-O για το χειρότερο σενάριο.

48
00:02:21,319 --> 00:02:23,860
Σε γενικές γραμμές, όταν μιλάμε για
η πολυπλοκότητα ενός αλγορίθμου,

49
00:02:23,860 --> 00:02:26,370
μιλάμε για το
στη χειρότερη περίπτωση.

50
00:02:26,370 --> 00:02:28,100
Έτσι κρατήστε αυτό κατά νου.

51
00:02:28,100 --> 00:02:31,510
>> Και σε αυτή την κατηγορία, είμαστε γενικά θα
να αποχωρήσει από την αυστηρή ανάλυση άκρη.

52
00:02:31,510 --> 00:02:35,350
Υπάρχουν επιστήμες και τομείς
προορίζεται για αυτό το είδος της ουσίας.

53
00:02:35,350 --> 00:02:37,610
Όταν μιλάμε για το σκεπτικό
μέσω αλγορίθμων,

54
00:02:37,610 --> 00:02:41,822
το οποίο θα κάνουμε το κομμάτι-από-κομμάτι για πολλούς
αλγόριθμοι μιλάμε για μέσα στην τάξη.

55
00:02:41,822 --> 00:02:44,780
Είμαστε πραγματικά ακριβώς μιλάμε για
σκεπτικό μέσα από αυτό με την κοινή λογική,

56
00:02:44,780 --> 00:02:47,070
όχι με τους τύπους, ή αποδείξεις,
ή κάτι τέτοιο.

57
00:02:47,070 --> 00:02:51,600
Γι 'αυτό μην ανησυχείτε, δεν θα είναι
να μετατραπεί σε ένα μεγάλο μάθημα των Μαθηματικών.

58
00:02:51,600 --> 00:02:55,920
>> Έτσι είπα εμείς ενδιαφερόμαστε για την πολυπλοκότητα
γιατί θέτει το ερώτημα, πώς

59
00:02:55,920 --> 00:03:00,160
δεν αλγορίθμων μας χειρίζονται μεγαλύτερα και
μεγαλύτερα σύνολα δεδομένων που ρίχνονται σε αυτούς.

60
00:03:00,160 --> 00:03:01,960
Λοιπόν, τι είναι ένα σύνολο δεδομένων;

61
00:03:01,960 --> 00:03:03,910
Τι εννοούσα όταν είπα αυτό;

62
00:03:03,910 --> 00:03:07,600
Αυτό σημαίνει ότι ό, τι κάνει το πιο
νόημα στο πλαίσιο, για να είμαι ειλικρινής.

63
00:03:07,600 --> 00:03:11,160
Αν έχουμε έναν αλγόριθμο, το
Διεργασίες Strings-- είμαστε πιθανώς

64
00:03:11,160 --> 00:03:13,440
μιλάμε για το μέγεθος του string.

65
00:03:13,440 --> 00:03:15,190
Αυτό είναι τα δεδομένα set--
το μέγεθος, ο αριθμός

66
00:03:15,190 --> 00:03:17,050
των χαρακτήρων που συνθέτουν τη σειρά.

67
00:03:17,050 --> 00:03:20,090
Αν μιλάμε για ένα
αλγόριθμο που επεξεργάζεται αρχεία,

68
00:03:20,090 --> 00:03:23,930
θα μπορούσαμε να μιλάμε για το πώς
πολλές kilobytes περιλαμβάνει αυτό το αρχείο.

69
00:03:23,930 --> 00:03:25,710
Και αυτό είναι το σύνολο των δεδομένων.

70
00:03:25,710 --> 00:03:28,870
Αν μιλάμε για έναν αλγόριθμο
ότι χειρίζεται συστοιχίες γενικότερα,

71
00:03:28,870 --> 00:03:31,510
όπως αλγορίθμων ταξινόμησης
ή την αναζήτηση αλγορίθμων,

72
00:03:31,510 --> 00:03:36,690
πιθανόν μιλάμε για τον αριθμό
των στοιχείων που περιλαμβάνουν μία συστοιχία.

73
00:03:36,690 --> 00:03:39,272
>> Τώρα, μπορούμε να μετρήσουμε μια
algorithm-- ειδικότερα,

74
00:03:39,272 --> 00:03:40,980
όταν λέω ότι μπορούμε
μετρούν έναν αλγόριθμο, που

75
00:03:40,980 --> 00:03:43,840
σημαίνει ότι μπορεί να μετρήσει πόσο
πολλοί πόροι που καταλαμβάνει.

76
00:03:43,840 --> 00:03:48,990
Είτε είναι οι πόροι αυτοί, πόσα
bytes της RAM-- ή ΜΒ RAM

77
00:03:48,990 --> 00:03:49,790
χρησιμοποιεί.

78
00:03:49,790 --> 00:03:52,320
Ή πόσο χρόνο χρειάζεται για να τρέξει.

79
00:03:52,320 --> 00:03:56,200
Και μπορούμε να ονομάσουμε αυτό
μετρούν, αυθαίρετα, στ ν.

80
00:03:56,200 --> 00:03:59,420
Όπου n είναι ο αριθμός των
στοιχείων στο σύνολο δεδομένων.

81
00:03:59,420 --> 00:04:02,640
Και στ του ν είναι πόσα Κάτι.

82
00:04:02,640 --> 00:04:07,530
Πόσες μονάδες των πόρων δεν
απαιτεί να επεξεργαστεί τα δεδομένα.

83
00:04:07,530 --> 00:04:10,030
>> Τώρα, έχουμε πραγματικά δεν με νοιάζει
για το τι στ ν είναι ακριβώς.

84
00:04:10,030 --> 00:04:13,700
Στην πραγματικότητα, πολύ σπάνια will--
Σίγουρα δεν θα είναι ποτέ σε αυτό το class-- μου

85
00:04:13,700 --> 00:04:18,709
βουτιά σε οποιαδήποτε πραγματικά βαθιά
ανάλυση του τι στ ν είναι.

86
00:04:18,709 --> 00:04:23,510
Εμείς απλά θα μιλήσουμε για το τι στ της
n είναι περίπου ή τι τείνει να.

87
00:04:23,510 --> 00:04:27,600
Και η τάση ενός αλγορίθμου είναι
υπαγορεύεται από το ανώτατο όρο της τάξης.

88
00:04:27,600 --> 00:04:29,440
Και μπορούμε να δούμε τι θα
εννοούμε με τον όρο ότι με τη λήψη

89
00:04:29,440 --> 00:04:31,910
Μια ματιά σε ένα πιο συγκεκριμένο παράδειγμα.

90
00:04:31,910 --> 00:04:34,620
>> Ας πούμε ότι έχουμε
τρεις διαφορετικοί αλγόριθμοι.

91
00:04:34,620 --> 00:04:39,350
Η πρώτη από τις οποίες λαμβάνει n
κύβους, ορισμένες μονάδες των πόρων

92
00:04:39,350 --> 00:04:42,880
να επεξεργαστεί ένα σύνολο δεδομένων μεγέθους n.

93
00:04:42,880 --> 00:04:47,000
Έχουμε ένα δεύτερο αλγόριθμο που λαμβάνει
n κύβο συν n τετράγωνο πόρων

94
00:04:47,000 --> 00:04:49,350
να επεξεργαστεί ένα σύνολο δεδομένων μεγέθους n.

95
00:04:49,350 --> 00:04:52,030
Και έχουμε ένα τρίτο
αλγόριθμος που τρέχει in-- ότι

96
00:04:52,030 --> 00:04:58,300
καταλαμβάνει n κύβους μείον 8η τετράγωνο
συν 20 n μονάδες των πόρων

97
00:04:58,300 --> 00:05:02,370
να επεξεργαστεί έναν αλγόριθμο
με τα δεδομένα που του μεγέθους n.

98
00:05:02,370 --> 00:05:05,594
>> Τώρα πάλι, πραγματικά δεν πρόκειται
να μπει σε αυτό το επίπεδο λεπτομέρειας.

99
00:05:05,594 --> 00:05:08,260
Είμαι πραγματικά ακριβώς έχουν αυτά τα επάνω
εδώ ως μια απεικόνιση ενός σημείου

100
00:05:08,260 --> 00:05:10,176
ότι Πάω να είναι
αποφάσεων σε μια δεύτερη, η οποία

101
00:05:10,176 --> 00:05:12,980
είναι ότι έχουμε μόνο πραγματικά νοιάζονται
για την τάση των πραγμάτων

102
00:05:12,980 --> 00:05:14,870
όπως τα σύνολα δεδομένων μεγαλώνουν.

103
00:05:14,870 --> 00:05:18,220
Έτσι, αν το σύνολο δεδομένων είναι μικρή, δεν υπάρχει
στην πραγματικότητα μια αρκετά μεγάλη διαφορά

104
00:05:18,220 --> 00:05:19,870
σε αυτούς τους αλγορίθμους.

105
00:05:19,870 --> 00:05:23,000
Ο τρίτος αλγόριθμος υπάρχει
λαμβάνει 13 φορές περισσότερο,

106
00:05:23,000 --> 00:05:27,980
13 φορές το ποσό των πόρων
να τρέξει σε σχέση με την πρώτη.

107
00:05:27,980 --> 00:05:31,659
>> Εάν το σύνολο δεδομένων μας είναι μέγεθος 10, η οποία
είναι μεγαλύτερο, αλλά όχι απαραίτητα τεράστιο,

108
00:05:31,659 --> 00:05:33,950
μπορούμε να δούμε ότι υπάρχει
στην πραγματικότητα ένα κομμάτι της διαφοράς.

109
00:05:33,950 --> 00:05:36,620
Η τρίτη αλγόριθμος
γίνεται πιο αποτελεσματική.

110
00:05:36,620 --> 00:05:40,120
Πρόκειται για πραγματικά 40% -
ή 60% πιο αποτελεσματική.

111
00:05:40,120 --> 00:05:41,580
Παίρνει 40%, το ποσό του χρόνου.

112
00:05:41,580 --> 00:05:45,250
Μπορεί run-- μπορεί να πάρει
400 μονάδες πόρων

113
00:05:45,250 --> 00:05:47,570
να επεξεργαστεί ένα σύνολο δεδομένων μεγέθους 10.

114
00:05:47,570 --> 00:05:49,410
Ότι η πρώτη
αλγόριθμο, αντιθέτως,

115
00:05:49,410 --> 00:05:54,520
παίρνει 1.000 μονάδες πόρων
να επεξεργαστεί ένα σύνολο δεδομένων μεγέθους 10.

116
00:05:54,520 --> 00:05:57,240
Αλλά κοιτάξτε τι συμβαίνει ως
αριθμοί μας να πάρει ακόμη μεγαλύτερο.

117
00:05:57,240 --> 00:05:59,500
>> Τώρα, η διαφορά
μεταξύ αυτών των αλγορίθμων

118
00:05:59,500 --> 00:06:01,420
αρχίζουν να γίνονται λίγο λιγότερο εμφανής.

119
00:06:01,420 --> 00:06:04,560
Και το γεγονός ότι υπάρχουν
χαμηλότερης τάξης terms-- ή μάλλον,

120
00:06:04,560 --> 00:06:09,390
όρους με χαμηλότερο exponents--
αρχίζουν να καταστεί άνευ αντικειμένου.

121
00:06:09,390 --> 00:06:12,290
Εάν ένα σύνολο δεδομένων είναι το μέγεθος
1000 και το πρώτο αλγόριθμο

122
00:06:12,290 --> 00:06:14,170
τρέχει σε ένα δισεκατομμύριο βήματα.

123
00:06:14,170 --> 00:06:17,880
Και ο δεύτερος αλγόριθμος τρέχει σε
ένα δισεκατομμύριο και ένα εκατομμύριο βήματα.

124
00:06:17,880 --> 00:06:20,870
Και ο τρίτος αλγόριθμος τρέχει
σε μόλις ντροπαλός του ενός δισεκατομμυρίου βήματα.

125
00:06:20,870 --> 00:06:22,620
Είναι λίγο πολύ ένα δισεκατομμύριο βήματα.

126
00:06:22,620 --> 00:06:25,640
Αυτοί οι όροι κατώτερο προκειμένου να ξεκινήσει
να γίνει πραγματικά άσχετη.

127
00:06:25,640 --> 00:06:27,390
Και ακριβώς για να πραγματικά
σφυρί το σπίτι της point--

128
00:06:27,390 --> 00:06:31,240
αν η είσοδος δεδομένων είναι ένα μέγεθος
million-- τα τρία από αυτά λίγο πολύ

129
00:06:31,240 --> 00:06:34,960
πάρτε ένα quintillion-- αν
μαθηματικά μου είναι correct-- βήματα

130
00:06:34,960 --> 00:06:37,260
να επεξεργαστεί μια είσοδο δεδομένων
του μεγέθους του ένα εκατομμύριο.

131
00:06:37,260 --> 00:06:38,250
Αυτό είναι πολλά βήματα.

132
00:06:38,250 --> 00:06:42,092
Και το γεγονός ότι ένας από αυτούς μπορεί να
πάρτε ένα ζευγάρι από 100.000, ή ένα ζευγάρι 100

133
00:06:42,092 --> 00:06:44,650
εκατομμύρια ακόμη λιγότερο όταν
μιλάμε για έναν αριθμό

134
00:06:44,650 --> 00:06:46,990
big-- ότι αυτό είναι το είδος της άσχετο.

135
00:06:46,990 --> 00:06:50,006
Όλα τείνουν να λάβουν
περίπου n κύβους,

136
00:06:50,006 --> 00:06:52,380
και γι 'αυτό θα αναφερθώ στην πραγματικότητα
σε όλες αυτές τις αλγορίθμων

137
00:06:52,380 --> 00:06:59,520
ως της τάξης του n
κύβους ή μεγάλο-Ο Ν κύβους.

138
00:06:59,520 --> 00:07:03,220
>> Εδώ είναι μια λίστα με μερικά από τα πιο
κοινή υπολογιστική πολυπλοκότητα κατηγορίες

139
00:07:03,220 --> 00:07:05,820
ότι θα συναντήσετε στο
αλγορίθμων, σε γενικές γραμμές.

140
00:07:05,820 --> 00:07:07,970
Και, επίσης, ειδικά σε CS50.

141
00:07:07,970 --> 00:07:11,410
Αυτά είναι παραγγελθούν από
γενικά ταχύτερος στην κορυφή,

142
00:07:11,410 --> 00:07:13,940
για γενικά βραδύτερη στο κάτω μέρος.

143
00:07:13,940 --> 00:07:16,920
Έτσι, οι αλγόριθμοι τείνουν σταθερά χρόνου
να είναι ο ταχύτερος, ανεξαρτήτως

144
00:07:16,920 --> 00:07:19,110
του μεγέθους του
εισαγωγής δεδομένων περνάτε.

145
00:07:19,110 --> 00:07:23,760
Παίρνουν πάντα μία πράξη ή
μία μονάδα των πόρων για την αντιμετώπιση.

146
00:07:23,760 --> 00:07:25,730
Θα μπορούσε να είναι 2, θα μπορούσε να
είναι 3, θα μπορούσε να είναι 4.

147
00:07:25,730 --> 00:07:26,910
Αλλά είναι ένας σταθερός αριθμός.

148
00:07:26,910 --> 00:07:28,400
Αυτό δεν μεταβάλλεται.

149
00:07:28,400 --> 00:07:31,390
>> Λογαριθμική αλγόριθμοι χρόνο
είναι ελαφρώς καλύτερη.

150
00:07:31,390 --> 00:07:33,950
Και ένα πολύ καλό παράδειγμα
λογαριθμική αλγόριθμο

151
00:07:33,950 --> 00:07:37,420
έχετε σίγουρα δει μέχρι τώρα είναι η
σχίσιμο του τηλεφωνικού καταλόγου

152
00:07:37,420 --> 00:07:39,480
να βρείτε Mike Smith στον τηλεφωνικό κατάλογο.

153
00:07:39,480 --> 00:07:40,980
Κόβουμε το πρόβλημα στη μέση.

154
00:07:40,980 --> 00:07:43,580
Και έτσι καθώς το n μεγαλώνει
και μεγαλύτερα και larger--

155
00:07:43,580 --> 00:07:47,290
Στην πραγματικότητα, κάθε φορά που θα διπλασιαστεί
n, παίρνει μόνο ένα ακόμη βήμα.

156
00:07:47,290 --> 00:07:49,770
Οπότε αυτό είναι ένα πολύ καλύτερο
από ό, τι, ας πούμε, γραμμικό χρόνο.

157
00:07:49,770 --> 00:07:53,030
Ποια είναι αν διπλασιαστεί η, το
Δέχεται διπλούς τον αριθμό των βημάτων.

158
00:07:53,030 --> 00:07:55,980
Αν τριπλασιαστεί n, παίρνει
τριπλασιάσει τον αριθμό των βημάτων.

159
00:07:55,980 --> 00:07:58,580
Ένα βήμα ανά μονάδα.

160
00:07:58,580 --> 00:08:01,790
>> Στη συνέχεια, τα πράγματα παίρνουν μια μικρή more--
Λίγο λιγότερο μεγάλη από εκεί.

161
00:08:01,790 --> 00:08:06,622
Έχετε γραμμική ρυθμική χρόνο, μερικές φορές
που ονομάζεται log γραμμικού χρόνου ή απλά n log n.

162
00:08:06,622 --> 00:08:08,330
Και θα αποτελεί παράδειγμα
από έναν αλγόριθμο που

163
00:08:08,330 --> 00:08:13,370
τρέχει στο n log n, η οποία είναι ακόμη καλύτερα
από τετραγωνική time-- n τετράγωνο.

164
00:08:13,370 --> 00:08:17,320
Ή πολυωνυμικό χρόνο, n δύο
οποιοσδήποτε αριθμός μεγαλύτερος από δύο.

165
00:08:17,320 --> 00:08:20,810
Ή εκθετικό χρόνο, η οποία
είναι ακόμη worse-- C έως το n.

166
00:08:20,810 --> 00:08:24,670
Έτσι, κάποιοι σταθερός αριθμός αυξήθηκε σε
η ισχύς του μεγέθους της εισόδου.

167
00:08:24,670 --> 00:08:28,990
Έτσι, αν υπάρχει 1,000-- εάν η
εισαγωγή δεδομένων έχει μέγεθος 1.000,

168
00:08:28,990 --> 00:08:31,310
θα χρειαζόταν C στην 1000η εξουσία.

169
00:08:31,310 --> 00:08:33,559
Είναι μια πολύ χειρότερα από ό, τι πολυωνυμικό χρόνο.

170
00:08:33,559 --> 00:08:35,030
>> Παραγοντικό χρόνος είναι ακόμη χειρότερη.

171
00:08:35,030 --> 00:08:37,760
Και στην πραγματικότητα, πραγματικά υπάρχει
Υπάρχουν άπειρες αλγορίθμων χρόνου,

172
00:08:37,760 --> 00:08:43,740
όπως το λεγόμενο ηλίθιο sort-- των οποίων
δουλειά είναι να ανακατέψετε τυχαία μια σειρά

173
00:08:43,740 --> 00:08:45,490
και, στη συνέχεια, ελέγξτε για να δείτε
αν αυτό είναι ταξινομημένο.

174
00:08:45,490 --> 00:08:47,589
Και αν δεν είναι, τυχαία
ανακατέψει και πάλι τον πίνακα

175
00:08:47,589 --> 00:08:49,130
και ελέγξτε για να δείτε αν είναι ταξινομημένο.

176
00:08:49,130 --> 00:08:51,671
Και όπως μπορείτε να imagine--
μπορείτε να φανταστείτε μια κατάσταση

177
00:08:51,671 --> 00:08:55,200
όπου στην χειρότερη περίπτωση, ότι βούληση
στην πραγματικότητα ποτέ δεν ξεκινήσει με τη συστοιχία.

178
00:08:55,200 --> 00:08:57,150
Ότι ο αλγόριθμος θα τρέχει για πάντα.

179
00:08:57,150 --> 00:08:59,349
Και έτσι ώστε θα ήταν μια
άπειρο χρόνο αλγόριθμος.

180
00:08:59,349 --> 00:09:01,890
Ας ελπίσουμε ότι δεν θα πρέπει να γράφει
κάθε παραγοντικό ή άπειρο χρόνο

181
00:09:01,890 --> 00:09:04,510
αλγορίθμων σε CS50.

182
00:09:04,510 --> 00:09:09,150
>> Έτσι, ας ρίξουμε λίγο περισσότερο
σκυρόδεμα ματιά σε κάποια απλούστερη

183
00:09:09,150 --> 00:09:11,154
υπολογιστική κλάσεις πολυπλοκότητας.

184
00:09:11,154 --> 00:09:13,070
Έτσι, έχουμε μια example--
ή δύο παραδείγματα here--

185
00:09:13,070 --> 00:09:15,590
σταθερής αλγορίθμων χρόνου,
η οποία να λαμβάνει πάντα

186
00:09:15,590 --> 00:09:17,980
μια ενιαία πράξη στη χειρότερη περίπτωση.

187
00:09:17,980 --> 00:09:20,050
Έτσι, το πρώτο example--
έχουμε μια συνάρτηση

188
00:09:20,050 --> 00:09:23,952
κάλεσε 4 για σας, η οποία
λαμβάνει μια σειρά μεγέθους 1.000.

189
00:09:23,952 --> 00:09:25,660
Στη συνέχεια, όμως προφανώς
στην πραγματικότητα δεν φαίνονται

190
00:09:25,660 --> 00:09:29,000
σε it-- δεν ενδιαφέρονται πραγματικά ό, τι είναι
στο εσωτερικό του, της εν λόγω διάταξης.

191
00:09:29,000 --> 00:09:30,820
Πάντα επιστρέφει μόλις τέσσερις.

192
00:09:30,820 --> 00:09:32,940
Έτσι, ότι ο αλγόριθμος,
παρά το γεγονός ότι

193
00:09:32,940 --> 00:09:35,840
παίρνει 1.000 στοιχεία δεν
κάνει τίποτα μαζί τους.

194
00:09:35,840 --> 00:09:36,590
Απλά επιστρέφει τέσσερις.

195
00:09:36,590 --> 00:09:38,240
Είναι πάντα ένα βήμα.

196
00:09:38,240 --> 00:09:41,600
>> Στην πραγματικότητα, προσθέστε 2 nums-- οποία
έχουμε δει στο παρελθόν, όπως well--

197
00:09:41,600 --> 00:09:43,680
επεξεργάζεται μόνο δύο ακέραιους αριθμούς.

198
00:09:43,680 --> 00:09:44,692
Δεν είναι ένα μόνο βήμα.

199
00:09:44,692 --> 00:09:45,900
Είναι πραγματικά βήματα ένα ζευγάρι.

200
00:09:45,900 --> 00:09:50,780
Μπορείτε να πάρετε ένα, μπορείτε να πάρετε b, μπορείτε να τους προσθέσετε
μαζί, και θα εξάγει τα αποτελέσματα.

201
00:09:50,780 --> 00:09:53,270
Έτσι είναι 84 βήματα.

202
00:09:53,270 --> 00:09:55,510
Αλλά είναι πάντα σταθερή,
ανεξάρτητα από α ή β.

203
00:09:55,510 --> 00:09:59,240
Θα πρέπει να πάρετε ένα, να πάρει β, προσθέστε
μαζί, το αποτέλεσμα εξόδου.

204
00:09:59,240 --> 00:10:02,900
Οπότε αυτό είναι ένα σταθερό χρόνο αλγόριθμος.

205
00:10:02,900 --> 00:10:05,170
>> Εδώ είναι ένα παράδειγμα ενός
γραμμικό χρόνο algorithm--

206
00:10:05,170 --> 00:10:08,740
ένας αλγόριθμος που gets-- ότι παίρνει
ένα επιπλέον βήμα, ενδεχομένως,

207
00:10:08,740 --> 00:10:10,740
ως συμβολή σας αυξάνεται κατά 1.

208
00:10:10,740 --> 00:10:14,190
Έτσι, ας πούμε ότι ψάχνετε
ο αριθμός 5 στο εσωτερικό μιας συστοιχίας.

209
00:10:14,190 --> 00:10:16,774
Μπορεί να έχετε μια κατάσταση όπου
μπορείτε να το βρείτε αρκετά νωρίς.

210
00:10:16,774 --> 00:10:18,606
Αλλά θα μπορούσε επίσης να έχει
μια κατάσταση όπου

211
00:10:18,606 --> 00:10:20,450
θα μπορούσε να είναι το τελευταίο στοιχείο της συστοιχίας.

212
00:10:20,450 --> 00:10:23,780
Σε μια σειρά μεγέθους 5, εάν
ψάχνουμε για τον αριθμό 5.

213
00:10:23,780 --> 00:10:25,930
Θα χρειαστούν 5 βήματα.

214
00:10:25,930 --> 00:10:29,180
Και στην πραγματικότητα, να φανταστείτε ότι υπάρχει
Δεν 5 οπουδήποτε σε αυτό το φάσμα.

215
00:10:29,180 --> 00:10:32,820
Είμαστε ακόμα στην πραγματικότητα πρέπει να εξετάσουμε
κάθε στοιχείο της συστοιχίας

216
00:10:32,820 --> 00:10:35,550
προκειμένου να καθοριστεί
έστω 5 υπάρχει.

217
00:10:35,550 --> 00:10:39,840
>> Έτσι, στη χειρότερη περίπτωση, η οποία είναι η
το στοιχείο είναι η τελευταία στη συστοιχία

218
00:10:39,840 --> 00:10:41,700
ή δεν υπάρχει καθόλου.

219
00:10:41,700 --> 00:10:44,690
Έχουμε ακόμη να δούμε
όλα τα n στοιχεία.

220
00:10:44,690 --> 00:10:47,120
Και έτσι αυτό αλγόριθμος
εκτελείται σε γραμμικό χρόνο.

221
00:10:47,120 --> 00:10:50,340
Μπορείτε να επιβεβαιώσετε ότι από
προέκταση λίγο λέγοντας,

222
00:10:50,340 --> 00:10:53,080
αν είχαμε μια σειρά 6-στοιχείων και
ψάχναμε για τον αριθμό 5,

223
00:10:53,080 --> 00:10:54,890
μπορεί να πάρει 6 βήματα.

224
00:10:54,890 --> 00:10:57,620
Αν έχουμε μια σειρά 7 στοιχείο και
ψάχνουμε για τον αριθμό 5.

225
00:10:57,620 --> 00:10:59,160
Θα μπορούσε να λάβει 7 βήματα.

226
00:10:59,160 --> 00:11:02,920
Καθώς προσθέτουμε ένα ακόμη στοιχείο που πρέπει να μας
σειρά, παίρνει ένα ακόμη βήμα.

227
00:11:02,920 --> 00:11:06,750
Αυτό είναι ένα γραμμικό αλγόριθμο
στη χειρότερη περίπτωση.

228
00:11:06,750 --> 00:11:08,270
>> Ζευγάρι γρήγορες ερωτήσεις για σας.

229
00:11:08,270 --> 00:11:11,170
Ποια είναι η runtime-- τι είναι
η χειρότερη περίπτωση εκτέλεσης

230
00:11:11,170 --> 00:11:13,700
του συγκεκριμένου αποσπάσματος κώδικα;

231
00:11:13,700 --> 00:11:17,420
Έτσι έχω ένα 4 βρόχο που τρέχει εδώ
από j ισούται με 0, σε όλη τη διαδρομή μέχρι το m.

232
00:11:17,420 --> 00:11:21,980
Και ό, τι βλέπω εδώ, είναι ότι η
σώμα του βρόχου εκτελείται σε σταθερό χρόνο.

233
00:11:21,980 --> 00:11:24,730
Έτσι, χρησιμοποιώντας την ορολογία που
έχουμε ήδη μιλήσει about-- τι

234
00:11:24,730 --> 00:11:29,390
θα είναι η χειρότερη περίπτωση
runtime αυτού του αλγορίθμου;

235
00:11:29,390 --> 00:11:31,050
Πάρτε ένα δευτερόλεπτο.

236
00:11:31,050 --> 00:11:34,270
Το εσωτερικό μέρος του βρόχου
εκτελείται σε σταθερό χρόνο.

237
00:11:34,270 --> 00:11:37,510
Και το εξωτερικό μέρος του
βρόχος πρόκειται να τρέξει m φορές.

238
00:11:37,510 --> 00:11:40,260
Έτσι ποια είναι η χειρότερη περίπτωση χρόνου εκτέλεσης εδώ;

239
00:11:40,260 --> 00:11:43,210
Μήπως να μαντέψετε μεγάλος-O του m;

240
00:11:43,210 --> 00:11:44,686
Θα ήθελα να είναι σωστή.

241
00:11:44,686 --> 00:11:46,230
>> Τι θα λέγατε για ένα άλλο;

242
00:11:46,230 --> 00:11:48,590
Αυτή τη φορά έχουμε ένα
βρόχος μέσα από ένα βρόχο.

243
00:11:48,590 --> 00:11:50,905
Έχουμε ένα εξωτερικό βρόχο
που εκτείνεται από μηδέν έως σ.

244
00:11:50,905 --> 00:11:54,630
Και έχουμε ένα εσωτερικό βρόχο που τρέχει
από μηδέν σε p, και στο εσωτερικό του ότι,

245
00:11:54,630 --> 00:11:57,890
Δηλώνω ότι το σώμα της
βρόχος εκτελείται σε σταθερό χρόνο.

246
00:11:57,890 --> 00:12:02,330
Έτσι ποια είναι η χειρότερη περίπτωση εκτέλεσης
του συγκεκριμένου αποσπάσματος κώδικα;

247
00:12:02,330 --> 00:12:06,140
Λοιπόν, και πάλι, έχουμε μια
εξωτερικός βρόχος που τρέχει φορές σ.

248
00:12:06,140 --> 00:12:09,660
Και κάθε time-- επανάληψη
του εν λόγω βρόχου, μάλλον.

249
00:12:09,660 --> 00:12:13,170
Έχουμε ένα εσωτερικό βρόχο
που τρέχει επίσης φορές σ.

250
00:12:13,170 --> 00:12:16,900
Και στη συνέχεια, μέσα από αυτό, υπάρχει η
σταθερή time-- μικρό απόσπασμα εκεί.

251
00:12:16,900 --> 00:12:19,890
>> Έτσι, αν έχουμε ένα εξωτερικό βρόχο που
τρέχει φορές p εντός του οποίου είναι

252
00:12:19,890 --> 00:12:22,880
ένα εσωτερικό βρόχο που
τρέχει σ times-- ό, τι είναι

253
00:12:22,880 --> 00:12:26,480
η χειρότερη περίπτωση εκτέλεσης
αυτής απόσπασμα του κώδικα;

254
00:12:26,480 --> 00:12:30,730
Μήπως να μαντέψετε μεγάλο-Ο π τετράγωνο;

255
00:12:30,730 --> 00:12:31,690
>> Είμαι ο Νταγκ Lloyd.

256
00:12:31,690 --> 00:12:33,880
Αυτό είναι CS50.

257
00:12:33,880 --> 00:12:35,622