1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Πιθανόν να έχετε ακούσει ανθρώπους να μιλούν για ένα γρήγορο ή αποτελεσματικό αλγόριθμο

2
00:00:10,950 --> 00:00:13,090
για την εκτέλεση συγκεκριμένης εργασίας σας,

3
00:00:13,090 --> 00:00:16,110
αλλά τι ακριβώς σημαίνει αυτό για έναν αλγόριθμο για να είναι γρήγορη ή αποδοτικό;

4
00:00:16,110 --> 00:00:18,580
Λοιπόν, δεν είναι να μιλάμε για μια μέτρηση σε πραγματικό χρόνο,

5
00:00:18,580 --> 00:00:20,500
σαν δευτερόλεπτα ή λεπτά.

6
00:00:20,500 --> 00:00:22,220
Αυτό συμβαίνει επειδή το υλικό του υπολογιστή

7
00:00:22,220 --> 00:00:24,260
και το λογισμικό διαφέρουν δραστικά.

8
00:00:24,260 --> 00:00:26,020
Το πρόγραμμά μου θα τρέχει πιο αργά από τη δική σας,

9
00:00:26,020 --> 00:00:28,000
επειδή είμαι να τρέχει σε παλαιότερο υπολογιστή,

10
00:00:28,000 --> 00:00:30,110
ή επειδή τυχαίνει να παίζει ένα online παιχνίδι βίντεο

11
00:00:30,110 --> 00:00:32,670
την ίδια στιγμή, η οποία hogging όλα μνήμη μου,

12
00:00:32,670 --> 00:00:35,400
ή θα μπορούσε να τρέχει το πρόγραμμα μου με διαφορετικό λογισμικό

13
00:00:35,400 --> 00:00:37,550
η οποία επικοινωνεί με το μηχάνημα διαφορετικά σε χαμηλό επίπεδο.

14
00:00:37,550 --> 00:00:39,650
Είναι σαν να συγκρίνουμε μήλα και τα πορτοκάλια.

15
00:00:39,650 --> 00:00:41,940
Ακριβώς επειδή αργό υπολογιστή μου παίρνει περισσότερο

16
00:00:41,940 --> 00:00:43,410
από τη δική σας για να δώσει μια απάντηση πίσω

17
00:00:43,410 --> 00:00:45,510
δεν σημαίνει ότι έχετε την πιο αποδοτικό αλγόριθμο.

18
00:00:45,510 --> 00:00:48,830
>> Έτσι, δεδομένου ότι δεν μπορούμε να συγκρίνουμε άμεσα τα runtimes των προγραμμάτων

19
00:00:48,830 --> 00:00:50,140
σε δευτερόλεπτα ή λεπτά,

20
00:00:50,140 --> 00:00:52,310
πώς μπορούμε να συγκρίνουμε 2 διαφορετικές αλγορίθμων

21
00:00:52,310 --> 00:00:55,030
ανεξάρτητα από το υλικό τους ή το περιβάλλον του λογισμικού;

22
00:00:55,030 --> 00:00:58,000
Για να δημιουργήσετε ένα πιο ομοιόμορφο τρόπο μέτρησης της αποδοτικότητας αλγοριθμικής,

23
00:00:58,000 --> 00:01:00,360
επιστήμονες της πληροφορικής και μαθηματικοί έχουν επινοήσει

24
00:01:00,360 --> 00:01:03,830
έννοιες για τη μέτρηση της ασυμπτωτική πολυπλοκότητα ενός προγράμματος

25
00:01:03,830 --> 00:01:06,110
και μια σημειογραφία που ονομάζεται «Big Ohnotation»

26
00:01:06,110 --> 00:01:08,320
για την περιγραφή αυτή.

27
00:01:08,320 --> 00:01:10,820
Ο επίσημος ορισμός είναι ότι η συνάρτηση f (x)

28
00:01:10,820 --> 00:01:13,390
τρέχει της τάξεως των g (x)

29
00:01:13,390 --> 00:01:15,140
εάν υπάρχει κάποια (χ) τιμή, χ και ₀

30
00:01:15,140 --> 00:01:17,630
κάποια σταθερά, C, για τις οποίες

31
00:01:17,630 --> 00:01:19,340
f (x) είναι μικρότερη ή ίση προς

32
00:01:19,340 --> 00:01:21,230
ότι η συνεχής χρόνοι g (x)

33
00:01:21,230 --> 00:01:23,190
για κάθε x μεγαλύτερο από x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Αλλά δεν πρέπει να φοβάται μακριά από τον επίσημο ορισμό.

35
00:01:25,290 --> 00:01:28,020
Τι ακριβώς σημαίνει αυτό σε λιγότερο θεωρητικό επίπεδο;

36
00:01:28,020 --> 00:01:30,580
Λοιπόν, αυτό είναι ουσιαστικά ένας τρόπος ανάλυσης

37
00:01:30,580 --> 00:01:33,580
πόσο γρήγορα εκτέλεσης ενός προγράμματος αυξάνεται ασυμπτωτικά.

38
00:01:33,580 --> 00:01:37,170
Δηλαδή, όπως το μέγεθος των εισροών σας αυξάνεται προς το άπειρο,

39
00:01:37,170 --> 00:01:41,390
λένε, είστε διαλογή μια σειρά από μεγέθους 1000 σε σύγκριση με ένα πίνακα μεγέθους 10.

40
00:01:41,390 --> 00:01:44,950
Πώς το χρόνο εκτέλεσης του προγράμματος σας να αυξηθεί;

41
00:01:44,950 --> 00:01:47,390
Για παράδειγμα, υποθέστε μετρώντας τον αριθμό των χαρακτήρων

42
00:01:47,390 --> 00:01:49,350
σε μια σειρά ο απλούστερος τρόπος

43
00:01:49,350 --> 00:01:51,620
 με τα πόδια σε όλη τη σειρά

44
00:01:51,620 --> 00:01:54,790
γράμμα-από-γράμμα και προσθέτοντας 1 σε ένα μετρητή για κάθε χαρακτήρα.

45
00:01:55,700 --> 00:01:58,420
Αυτός ο αλγόριθμος λέγεται για να τρέξει σε γραμμικό χρόνο

46
00:01:58,420 --> 00:02:00,460
σε σχέση με τον αριθμό των χαρακτήρων,

47
00:02:00,460 --> 00:02:02,670
'N' στη συμβολοσειρά.

48
00:02:02,670 --> 00:02:04,910
Με λίγα λόγια, τρέχει σε χρόνο O (n).

49
00:02:05,570 --> 00:02:07,290
Γιατί συμβαίνει αυτό;

50
00:02:07,290 --> 00:02:09,539
Λοιπόν, με την χρησιμοποίηση της προσέγγισης αυτής, ο χρόνος που απαιτείται

51
00:02:09,539 --> 00:02:11,300
να διασχίσει ολόκληρη τη συμβολοσειρά

52
00:02:11,300 --> 00:02:13,920
είναι ανάλογη προς τον αριθμό των χαρακτήρων.

53
00:02:13,920 --> 00:02:16,480
Μετρώντας τον αριθμό των χαρακτήρων σε μια συμβολοσειρά 20-χαρακτήρων

54
00:02:16,480 --> 00:02:18,580
πρόκειται να πάρει δύο φορές όσο χρειάζεται

55
00:02:18,580 --> 00:02:20,330
για την καταμέτρηση των χαρακτήρων σε μια συμβολοσειρά 10-χαρακτήρων,

56
00:02:20,330 --> 00:02:23,000
γιατί πρέπει να εξετάσουμε όλους τους χαρακτήρες

57
00:02:23,000 --> 00:02:25,740
και κάθε χαρακτήρας παίρνει το ίδιο χρονικό διάστημα για να δούμε.

58
00:02:25,740 --> 00:02:28,050
Όπως μπορείτε να αυξήσετε τον αριθμό των χαρακτήρων,

59
00:02:28,050 --> 00:02:30,950
ο χρόνος εκτέλεσης θα αυξηθεί γραμμικά με το μήκος εισόδου.

60
00:02:30,950 --> 00:02:33,500
>> Τώρα, φανταστείτε αν αποφασίσετε ότι γραμμικό χρόνο,

61
00:02:33,500 --> 00:02:36,390
O (n), απλά δεν ήταν αρκετά γρήγορο για σένα;

62
00:02:36,390 --> 00:02:38,750
Ίσως είστε αποθήκευση τεράστιων χορδές,

63
00:02:38,750 --> 00:02:40,450
και δεν μπορείτε να δώσει το επιπλέον χρόνο που θα χρειαζόταν

64
00:02:40,450 --> 00:02:44,000
να διασχίσει όλα τους χαρακτήρες μετρώντας ένα-ένα.

65
00:02:44,000 --> 00:02:46,650
Έτσι, αν αποφασίσετε να δοκιμάσετε κάτι διαφορετικό.

66
00:02:46,650 --> 00:02:49,270
Τι θα συμβεί αν θα συμβεί ήδη να αποθηκεύσετε τον αριθμό των χαρακτήρων

67
00:02:49,270 --> 00:02:52,690
στη σειρά, ας πούμε, σε μια μεταβλητή που ονομάζεται 'λεν, "

68
00:02:52,690 --> 00:02:54,210
νωρίς στο πρόγραμμα,

69
00:02:54,210 --> 00:02:57,800
πριν αποθηκεύονται ακόμη και την πρώτη σε σειρά χαρακτήρα σας;

70
00:02:57,800 --> 00:02:59,980
Στη συνέχεια, το μόνο που θα έχετε να κάνετε τώρα για να μάθετε το μήκος συμβολοσειράς,

71
00:02:59,980 --> 00:03:02,570
είναι να ελέγξετε ποια είναι η τιμή της μεταβλητής είναι.

72
00:03:02,570 --> 00:03:05,530
Δεν θα πρέπει να εξετάσουμε την ίδια σειρά σε όλα,

73
00:03:05,530 --> 00:03:08,160
και την πρόσβαση στην τιμή μιας μεταβλητής, όπως λεν θεωρείται

74
00:03:08,160 --> 00:03:11,100
ασυμπτωτικά μια σταθερή λειτουργία του χρόνου,

75
00:03:11,100 --> 00:03:13,070
ή Ο (1).

76
00:03:13,070 --> 00:03:17,110
Γιατί συμβαίνει αυτό; Λοιπόν, θυμάστε τι ασυμπτωτική πολυπλοκότητα σημαίνει.

77
00:03:17,110 --> 00:03:19,100
Πώς λειτουργεί η αλλαγή χρόνου εκτέλεσης, όπως το μέγεθος

78
00:03:19,100 --> 00:03:21,400
εισόδους σας μεγαλώνει;

79
00:03:21,400 --> 00:03:24,630
>> Πείτε προσπαθούσατε να πάρετε τον αριθμό των χαρακτήρων σε μια μεγαλύτερη συμβολοσειρά.

80
00:03:24,630 --> 00:03:26,960
Λοιπόν, δεν θα έχει σημασία πόσο μεγάλο θα κάνει το string,

81
00:03:26,960 --> 00:03:28,690
ακόμη και ένα εκατομμύριο χαρακτήρες,

82
00:03:28,690 --> 00:03:31,150
το μόνο που θα έχετε να κάνετε για να βρείτε το μήκος της στοιχειοσειράς με αυτή την προσέγγιση,

83
00:03:31,150 --> 00:03:33,790
είναι να διαβάσει την τιμή της μεταβλητής len,

84
00:03:33,790 --> 00:03:35,440
την οποία έχετε ήδη κάνει.

85
00:03:35,440 --> 00:03:38,200
Το μήκος εισόδου, δηλαδή, το μήκος του string που προσπαθείτε να βρείτε,

86
00:03:38,200 --> 00:03:41,510
δεν επηρεάζει καθόλου το πόσο γρήγορα τρέχει το πρόγραμμά σας.

87
00:03:41,510 --> 00:03:44,550
Αυτό το μέρος του προγράμματός σας θα τρέχει εξίσου γρήγορα σε μια σειρά ενός χαρακτήρα

88
00:03:44,550 --> 00:03:46,170
και χίλια-συμβολοσειρά,

89
00:03:46,170 --> 00:03:49,140
και γι 'αυτό το πρόγραμμα θα πρέπει να αναφέρεται το τρέξιμο σε συνεχή χρόνο

90
00:03:49,140 --> 00:03:51,520
σε σχέση με το μέγεθος εισόδου.

91
00:03:51,520 --> 00:03:53,920
>> Φυσικά, υπάρχει ένα μειονέκτημα.

92
00:03:53,920 --> 00:03:55,710
Μπορείτε δαπανήσει επιπλέον χώρο μνήμης στον υπολογιστή σας

93
00:03:55,710 --> 00:03:57,380
αποθήκευση της μεταβλητής

94
00:03:57,380 --> 00:03:59,270
και ο επιπλέον χρόνος που σας παίρνει

95
00:03:59,270 --> 00:04:01,490
να κάνουν την πραγματική αποθήκευση της μεταβλητής,

96
00:04:01,490 --> 00:04:03,390
αλλά το πρόβλημα παραμένει,

97
00:04:03,390 --> 00:04:05,060
να ανακαλύψει πόσο μακριά σειρά σας ήταν

98
00:04:05,060 --> 00:04:07,600
δεν εξαρτάται από το μήκος της συμβολοσειράς σε όλα.

99
00:04:07,600 --> 00:04:10,720
Έτσι, τρέχει σε χρόνο O (1) ή σταθερό χρόνο.

100
00:04:10,720 --> 00:04:13,070
Αυτό, βέβαια, δεν σημαίνει ότι πρέπει να

101
00:04:13,070 --> 00:04:15,610
ότι ο κωδικός σας τρέχει σε 1 βήμα,

102
00:04:15,610 --> 00:04:17,470
αλλά δεν έχει σημασία πόσο πολλά είναι τα βήματα,

103
00:04:17,470 --> 00:04:20,019
αν δεν αλλάζει με το μέγεθος των εισροών,

104
00:04:20,019 --> 00:04:23,420
είναι ακόμα ασυμπτωτικά σταθερό οποία εμείς εκπροσωπούμε ως O (1).

105
00:04:23,420 --> 00:04:25,120
>> Όπως μπορείτε να μαντέψετε,

106
00:04:25,120 --> 00:04:27,940
υπάρχουν πολλές διαφορετικές μεγάλες O runtimes για τη μέτρηση αλγορίθμων με.

107
00:04:27,940 --> 00:04:32,980
O (n) ² αλγόριθμοι είναι ασυμπτωτικά πιο αργή από αλγορίθμους O (n).

108
00:04:32,980 --> 00:04:35,910
Δηλαδή, καθώς ο αριθμός των στοιχείων (n) μεγαλώνει,

109
00:04:35,910 --> 00:04:39,280
τελικά O (n) ² αλγόριθμοι θα χρειαστεί περισσότερο χρόνο

110
00:04:39,280 --> 00:04:41,000
από O (n) αλγορίθμων για να τρέξει.

111
00:04:41,000 --> 00:04:43,960
Αυτό δεν σημαίνει O (n) αλγόριθμοι πάντα τρέχουν πιο γρήγορα

112
00:04:43,960 --> 00:04:46,410
από O (n) ² αλγορίθμων, ακόμη και στο ίδιο περιβάλλον,

113
00:04:46,410 --> 00:04:48,080
για το ίδιο υλικό.

114
00:04:48,080 --> 00:04:50,180
Ίσως για μικρά μεγέθη εισόδου,

115
00:04:50,180 --> 00:04:52,900
 ο O (n) ² αλγόριθμος μπορεί στην πραγματικότητα να λειτουργήσει πιο γρήγορα,

116
00:04:52,900 --> 00:04:55,450
αλλά, τελικά, όπως του μεγέθους της εισόδου αυξάνει

117
00:04:55,450 --> 00:04:58,760
προς το άπειρο, το O (n) χρόνο εκτέλεσης ² αλγορίθμου

118
00:04:58,760 --> 00:05:02,000
θα επισκιάσει τελικά το runtime του O (n) αλγόριθμο.

119
00:05:02,000 --> 00:05:04,230
Ακριβώς όπως και κάθε τετραγωνική μαθηματική συνάρτηση

120
00:05:04,230 --> 00:05:06,510
 θα ξεπεράσει τελικά κάθε γραμμική συνάρτηση,

121
00:05:06,510 --> 00:05:09,200
δεν έχει σημασία πόσο μεγάλο μέρος ενός κεφαλιού ξεκινήσει η γραμμική συνάρτηση ξεκινά με.

122
00:05:10,010 --> 00:05:12,000
Αν εργάζεστε με μεγάλες ποσότητες δεδομένων,

123
00:05:12,000 --> 00:05:15,510
αλγόριθμους που τρέχουν σε χρόνο O (n) ² χρόνο μπορεί πραγματικά να καταλήξετε επιβραδύνουν το πρόγραμμά σας,

124
00:05:15,510 --> 00:05:17,770
αλλά για μικρά μεγέθη εισόδου,

125
00:05:17,770 --> 00:05:19,420
τότε μάλλον δεν θα παρατηρήσετε ακόμη.

126
00:05:19,420 --> 00:05:21,280
>> Μια άλλη ασυμπτωτική πολυπλοκότητα είναι,

127
00:05:21,280 --> 00:05:24,420
λογαριθμική φορά, O (log n).

128
00:05:24,420 --> 00:05:26,340
Ένα παράδειγμα ενός αλγορίθμου που εκτελείται αυτό γρήγορα

129
00:05:26,340 --> 00:05:29,060
είναι το κλασικό αλγόριθμο δυαδικής αναζήτησης,

130
00:05:29,060 --> 00:05:31,850
για την εύρεση ενός στοιχείου σε ήδη ταξινομημένο κατάλογο στοιχείων.

131
00:05:31,850 --> 00:05:33,400
>> Αν δεν ξέρετε τι κάνει δυαδική αναζήτηση,

132
00:05:33,400 --> 00:05:35,170
Θα το εξηγήσω για σας πραγματικά γρήγορα.

133
00:05:35,170 --> 00:05:37,020
Ας πούμε ότι ψάχνετε για τον αριθμό 3

134
00:05:37,020 --> 00:05:40,200
σε αυτή την συστοιχία των ακεραίων.

135
00:05:40,200 --> 00:05:42,140
Φαίνεται ότι στο μεσαίο στοιχείο του πίνακα

136
00:05:42,140 --> 00:05:46,830
και ρωτά, "Είναι το στοιχείο που θέλω μεγαλύτερη, ίση ή μικρότερη από αυτό;"

137
00:05:46,830 --> 00:05:49,150
Αν είναι ίσες, τότε μεγάλη. Βρήκατε το στοιχείο, και είστε έτοιμοι.

138
00:05:49,150 --> 00:05:51,300
Αν είναι μεγαλύτερη, τότε ξέρετε το στοιχείο

139
00:05:51,300 --> 00:05:53,440
πρέπει να είναι στην δεξιά πλευρά της συστοιχίας,

140
00:05:53,440 --> 00:05:55,200
και μπορείτε μόνο να δείτε ότι στο μέλλον,

141
00:05:55,200 --> 00:05:57,690
και αν είναι μικρότερο, τότε ξέρετε ότι πρέπει να είναι στην αριστερή πλευρά.

142
00:05:57,690 --> 00:06:00,980
Αυτή η διαδικασία επαναλαμβάνεται τότε με τη συστοιχία μικρότερο μέγεθος

143
00:06:00,980 --> 00:06:02,870
έως ότου η σωστή στοιχείο βρίσκεται.

144
00:06:08,080 --> 00:06:11,670
>> Αυτό το ισχυρό αλγόριθμο κόβει το μέγεθος του πίνακα στο μισό με κάθε λειτουργία.

145
00:06:11,670 --> 00:06:14,080
Έτσι, για να βρείτε ένα στοιχείο σε ένα ταξινομημένο πίνακα μεγέθους 8,

146
00:06:14,080 --> 00:06:16,170
το πολύ (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
ή 3 από τις πράξεις αυτές,

148
00:06:18,450 --> 00:06:22,260
ελέγχοντας το μεσαίο στοιχείο, στη συνέχεια κοπή τη συστοιχία στο μισό θα απαιτείται,

149
00:06:22,260 --> 00:06:25,670
ενώ μια σειρά από μέγεθος 16 παίρνει (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
ή 4 ​​λειτουργίες.

151
00:06:27,480 --> 00:06:30,570
Αυτό είναι μόνο 1 επιπλέον λειτουργία για μια σειρά διπλασιαστεί σε μέγεθος.

152
00:06:30,570 --> 00:06:32,220
Διπλασιάζοντας το μέγεθος της συστοιχίας

153
00:06:32,220 --> 00:06:35,160
αυξάνει το χρόνο λειτουργίας του μόνο 1 κομμάτι αυτού του κώδικα.

154
00:06:35,160 --> 00:06:37,770
Πάλι, ελέγχοντας το μεσαίο στοιχείο του πίνακα, τότε σχισίματος.

155
00:06:37,770 --> 00:06:40,440
Έτσι, λέγεται για να λειτουργήσει σε λογαριθμική χρόνο,

156
00:06:40,440 --> 00:06:42,440
O (log n).

157
00:06:42,440 --> 00:06:44,270
Αλλά περιμένετε, λέτε,

158
00:06:44,270 --> 00:06:47,510
αυτό δεν εξαρτάται από όπου στη λίστα το στοιχείο που αναζητάτε είναι;

159
00:06:47,510 --> 00:06:50,090
Τι θα συμβεί αν το πρώτο στοιχείο κοιτάς συμβαίνει να είναι η σωστή;

160
00:06:50,090 --> 00:06:52,040
Στη συνέχεια, παίρνει μόνο 1 λειτουργία,

161
00:06:52,040 --> 00:06:54,310
Δεν έχει σημασία πόσο μεγάλη είναι η λίστα είναι.

162
00:06:54,310 --> 00:06:56,310
>> Λοιπόν, γι 'αυτό οι επιστήμονες υπολογιστών έχουν περισσότερους όρους

163
00:06:56,310 --> 00:06:58,770
για ασυμπτωτική πολυπλοκότητα που αντικατοπτρίζουν την καλύτερη περίπτωση-

164
00:06:58,770 --> 00:07:01,050
και στη χειρότερη περίπτωση παραστάσεις ενός αλγορίθμου.

165
00:07:01,050 --> 00:07:03,320
Πιο σωστά, τα άνω και κάτω όρια

166
00:07:03,320 --> 00:07:05,090
στο χρόνο εκτέλεσης.

167
00:07:05,090 --> 00:07:07,660
Στην καλύτερη περίπτωση για δυαδική αναζήτηση, στοιχείο μας είναι

168
00:07:07,660 --> 00:07:09,330
εκεί στη μέση,

169
00:07:09,330 --> 00:07:11,770
και μπορείτε να το πάρετε σε συνεχή χρόνο,

170
00:07:11,770 --> 00:07:14,240
ανεξάρτητα από το πόσο μεγάλη είναι η υπόλοιπη της συστοιχίας είναι.

171
00:07:15,360 --> 00:07:17,650
Το σύμβολο που χρησιμοποιείται για το σκοπό αυτό είναι Ω.

172
00:07:17,650 --> 00:07:19,930
Έτσι, ο αλγόριθμος αυτός λέγεται να τρέχει στο Ω (1).

173
00:07:19,930 --> 00:07:21,990
Στην καλύτερη περίπτωση, βρίσκει το στοιχείο γρήγορα,

174
00:07:21,990 --> 00:07:24,200
Δεν έχει σημασία πόσο μεγάλη είναι η σειρά είναι,

175
00:07:24,200 --> 00:07:26,050
αλλά στην χειρότερη περίπτωση,

176
00:07:26,050 --> 00:07:28,690
που πρέπει να επιτελεί (log n) έλεγχοι διάσπαση

177
00:07:28,690 --> 00:07:31,030
του πίνακα για να βρείτε το σωστό στοιχείο.

178
00:07:31,030 --> 00:07:34,270
Τα χειρότερη περίπτωση άνω φράγματα που προβλέπονται με το μεγάλο "O" που ήδη γνωρίζετε.

179
00:07:34,270 --> 00:07:38,080
Έτσι, είναι O (log n), αλλά Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Μια γραμμική αναζήτηση, αντιθέτως,

181
00:07:40,680 --> 00:07:43,220
στην οποία τα πόδια σας μέσα από κάθε στοιχείο του πίνακα

182
00:07:43,220 --> 00:07:45,170
να βρείτε αυτό που θέλετε,

183
00:07:45,170 --> 00:07:47,420
είναι στην καλύτερη Ω (1).

184
00:07:47,420 --> 00:07:49,430
Και πάλι, το πρώτο στοιχείο που θέλετε.

185
00:07:49,430 --> 00:07:51,930
Έτσι, δεν έχει σημασία πόσο μεγάλη είναι η σειρά είναι.

186
00:07:51,930 --> 00:07:54,840
Στη χειρότερη περίπτωση, αυτό είναι το τελευταίο στοιχείο του πίνακα.

187
00:07:54,840 --> 00:07:58,560
Έτσι, μπορείτε να περπατήσετε μέσα από όλα τα n στοιχεία του πίνακα για να το βρείτε,

188
00:07:58,560 --> 00:08:02,170
όπως και αν ψάχνατε για ένα 3.

189
00:08:04,320 --> 00:08:06,030
Έτσι, τρέχει σε χρόνο O (n)

190
00:08:06,030 --> 00:08:09,330
επειδή είναι ανάλογη με τον αριθμό των στοιχείων στη συστοιχία.

191
00:08:10,800 --> 00:08:12,830
>> Ένα ακόμη σύμβολο που χρησιμοποιείται είναι Θ.

192
00:08:12,830 --> 00:08:15,820
Αυτό μπορεί να χρησιμοποιηθεί για να περιγράψει αλγορίθμων όπου οι καλύτερες και τις χειρότερες περιπτώσεις

193
00:08:15,820 --> 00:08:17,440
είναι τα ίδια.

194
00:08:17,440 --> 00:08:20,390
Αυτή είναι η υπόθεση της συμβολοσειράς μήκους αλγόριθμοι μιλήσαμε για νωρίτερα.

195
00:08:20,390 --> 00:08:22,780
Δηλαδή, αν θα το αποθηκεύσει σε μια μεταβλητή πριν

196
00:08:22,780 --> 00:08:25,160
αποθηκεύουμε το string και η πρόσβαση αργότερα σε σταθερό χρόνο.

197
00:08:25,160 --> 00:08:27,920
Δεν έχει σημασία ποιος είναι ο αριθμός

198
00:08:27,920 --> 00:08:30,130
είμαστε αποθήκευση σε αυτή τη μεταβλητή, θα πρέπει να το δει κανείς.

199
00:08:33,110 --> 00:08:35,110
Η καλύτερη περίπτωση είναι, κοιτάμε

200
00:08:35,110 --> 00:08:37,120
και βρείτε το μήκος του string.

201
00:08:37,120 --> 00:08:39,799
Έτσι Ω (1) ή καλύτερη περίπτωση σταθερό χρόνο.

202
00:08:39,799 --> 00:08:41,059
Η χειρότερη περίπτωση είναι,

203
00:08:41,059 --> 00:08:43,400
το δούμε και να βρούμε το μήκος του string.

204
00:08:43,400 --> 00:08:47,300
Έτσι, O (1) ή σταθερό χρόνο στη χειρότερη περίπτωση.

205
00:08:47,300 --> 00:08:49,180
Έτσι, δεδομένου ότι η καλύτερη περίπτωση και χειρότερες περιπτώσεις είναι τα ίδια,

206
00:08:49,180 --> 00:08:52,520
αυτό μπορεί να λεχθεί για να τρέξει σε Θ (1) ώρα.

207
00:08:54,550 --> 00:08:57,010
>> Εν ολίγοις, έχουμε καλές τρόπους για να λόγος για την αποτελεσματικότητα τους κωδικούς

208
00:08:57,010 --> 00:09:00,110
χωρίς να γνωρίζει τίποτα για το πραγματικό κόσμο παίρνουν χρόνο για να τρέξει,

209
00:09:00,110 --> 00:09:02,270
η οποία επηρεάζεται από πολλούς εξωτερικούς παράγοντες,

210
00:09:02,270 --> 00:09:04,190
συμπεριλαμβανομένων των διαφορετικών hardware, λογισμικό,

211
00:09:04,190 --> 00:09:06,040
ή οι ιδιαιτερότητες του κωδικού σας.

212
00:09:06,040 --> 00:09:08,380
Επίσης, μας επιτρέπει να διαλογιστούν και για το τι θα συμβεί

213
00:09:08,380 --> 00:09:10,180
όταν το μέγεθος των αυξήσεων εισόδων.

214
00:09:10,180 --> 00:09:12,490
>> Αν τρέχετε σε χρόνο O (n) αλγόριθμο ²,

215
00:09:12,490 --> 00:09:15,240
ή, ακόμη χειρότερα, ένας O (2 ⁿ) αλγόριθμος,

216
00:09:15,240 --> 00:09:17,170
ένας από τους ταχύτερα αναπτυσσόμενους τύπους,

217
00:09:17,170 --> 00:09:19,140
πραγματικά θα αρχίσετε να παρατηρείτε την επιβράδυνση

218
00:09:19,140 --> 00:09:21,220
όταν αρχίσετε να εργάζεστε με μεγαλύτερα ποσά των δεδομένων.

219
00:09:21,220 --> 00:09:23,590
>> Αυτό είναι ασυμπτωτική πολυπλοκότητα. Ευχαριστώ.