Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Πρόλογος

Εάν θέλετε να μάθετε τι είναι η χωροχρονική πολυπλοκότητα, πρέπει να ξέρετε τι είναι μια δομή δεδομένων.

Αυτό μπορεί να γίνει κατανοητό σε δύο επίπεδα. Δεδομένα υπάρχουν παντού στη ζωή μας, όπως διεθνείς εκδηλώσεις που είναι καυτά θέματα για το Douyin, η αφαίρεση πανοπλίας του Yongzheng κ.λπ. Αυτό που μπορούν να δουν οι χρήστες μας είναι τα δεδομένα που αποθηκεύει η Douyin στον διακομιστή υποστήριξης. Αλλά όλα αυτά τα δεδομένα έχουν ένα χαρακτηριστικό, δηλαδή, βρίσκονται όλα στη λίστα καυτών αναζητήσεων του Douyin και αυτή η λίστα είναι δομημένη έτσι ώστε να διασφαλίζει ότι τα δεδομένα βρίσκονται σε μια σταθερή τοποθεσία για περιήγηση από τους χρήστες.

Επιπλέον, με τις δομές δεδομένων, οι αλγόριθμοι είναι αδιαχώριστοι. Λοιπόν, όπως μόλις είπαμε, μια δομή δεδομένων αποθηκεύει δεδομένα τακτικά σε μια δομή, οπότε ο τρόπος αποτελεσματικής πρόσβασης στα δεδομένα από τη δομή είναι ένας αλγόριθμος.

χρονική πολυπλοκότητα

Με τους αλγόριθμους, υπάρχει πολυπλοκότητα χρόνου και χωρικής πολυπλοκότητας. Επειδή η μνήμη των υπολογιστών γίνεται ολοένα και μεγαλύτερη, η πολυπλοκότητα του χρόνου είναι πιο σημαντική από την πολυπλοκότητα του χώρου.Ας καταλάβουμε λοιπόν πρώτα τη χρονική πολυπλοκότητα

έννοια

Χρονική πολυπλοκότητα, η πιο σημαντική λέξη είναι ο χρόνος, ο χρόνος εδώ αναφέρεται στον χρόνο που εκτελείται ένα πρόγραμμα Εάν η χρονική πολυπλοκότητα είναι μικρότερη, τότε ο αλγόριθμος αποδεικνύεται καλύτερος.Ο υπολογισμός της χρονικής πολυπλοκότητας εκφράζεται με τον συναρτητικό τύπο T(N)

Γιατί λοιπόν δεν υπολογίζουμε εκ των προτέρων τη χρονική πολυπλοκότητα αυτού του προγράμματος και δεν γράφουμε τον κώδικα για τη βέλτιστη λύση; Αυτό περιλαμβάνει ζητήματα υπολογιστή.

1. Επειδή ο χρόνος εκτέλεσης του προγράμματος σχετίζεται με το περιβάλλον μεταγλώττισης και τη διαμόρφωση της μηχανής που εκτελείται, για παράδειγμα, ένα πρόγραμμα αλγορίθμου χρησιμοποιεί έναν παλιό μεταγλωττιστή
   Η μεταγλώττιση με έναν νέο μεταγλωττιστή και η μεταγλώττιση με έναν νέο μεταγλωττιστή έχουν διαφορετικούς χρόνους εκτέλεσης στον ίδιο υπολογιστή.
2. Το ίδιο πρόγραμμα αλγορίθμου έχει διαφορετικούς χρόνους εκτέλεσης χρησιμοποιώντας ένα παλιό μηχάνημα χαμηλής διαμόρφωσης και ένα νέο μηχάνημα υψηλής διαμόρφωσης.
3. Και ο χρόνος μπορεί να ελεγχθεί μόνο αφού γραφτεί το πρόγραμμα, όχι να υπολογιστεί και να αξιολογηθεί μέσω θεωρητικής σκέψης πριν από τη συγγραφή του προγράμματος.

Ας δούμε ένα κομμάτι κώδικα:

// 请计算⼀下Func1中count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Εάν κοιτάξετε αυτόν τον κώδικα με βάση τον αριθμό των εκτελέσεων μέτρησης, θα πρέπει να είναι:
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

Αυτή τη στιγμή, κάποιος είπε, δεν μετράει αυτό το int count=0;

Εδώ υποτιμάμε υπερβολικά τον υπολογιστή μας Η CPU του υπολογιστή μας μπορεί να εκτελεί εκατοντάδες εκατομμύρια φορές το δευτερόλεπτο. Επομένως, η χρονική πολυπλοκότητα που υπολογίσαμε δεν είναι ακριβής, είναι απλώς μια πρόχειρη εκτίμηση Αυτή τη στιγμή, χρησιμοποιούμε ένα νέο σύμβολο για να την αναπαραστήσουμε.

Ασυμπτωτική αναπαράσταση του Big O

Σημείωση Big O: Είναι ένα μαθηματικό σύμβολο που χρησιμοποιείται για να περιγράψει την ασυμπτωτική συμπεριφορά μιας συνάρτησης και χρησιμοποιείται εδώ για να αναπαραστήσει την εκτιμώμενη χρονική πολυπλοκότητα.

Επομένως, εξακολουθεί να μετράει σαν T(N) εδώ, αν ναι, δεν χρειάζεται να χρησιμοποιήσουμε άλλο σύμβολο για να το αναπαραστήσουμε. Αυτό περιλαμβάνει τους κανόνες για την καταμέτρηση O:

1. Στον συναρτησιακό τύπο πολυπλοκότητας χρόνου T(N), διατηρούνται μόνο οι όροι υψηλότερης τάξης και οι όροι χαμηλής τάξης αφαιρούνται, επειδή όταν το N συνεχίζει να αυξάνεται, η επίδραση των όρων χαμηλής τάξης στο αποτέλεσμα γίνεται όλο και μικρότερη. Όταν το N είναι άπειρο, μπορεί να αγνοηθεί.
2. Εάν ο όρος υψηλότερης τάξης υπάρχει και δεν είναι 1, αφαιρέστε τον σταθερό συντελεστή αυτού του όρου, επειδή καθώς το N συνεχίζει να αυξάνεται, αυτός ο συντελεστής θα έχει όλο και μικρότερη επιρροή στο αποτέλεσμα Όταν το N είναι άπειρο, μπορεί να αγνοηθεί.
3. Εάν δεν υπάρχουν στοιχεία που να σχετίζονται με Ν στο T(N) αλλά μόνο σταθερά στοιχεία, αντικαταστήστε όλες τις προσθετικές σταθερές με τη σταθερά 1.

Στη συνέχεια, κοιτάξτε το παραπάνω T(N)=N^ 2 + 2 ∗ N + 10. Η υψηλότερη τάξη εδώ είναι N2, οπότε αφαιρώντας άλλες χαμηλές τάξεις, η πολυπλοκότητα είναι (ON^2)

Κόφτης μικρής κλίμακας

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Εδώ T(N)=M+N, τότε ας υπολογίσουμε ξανά το O(N) και το N εδώ είναι και τα δύο της ίδιας σειράς, επομένως δεν συμμορφώνονται με τον πρώτο κανόνα και δεν αντιστοιχούν στον δεύτερο και τον τρίτο κανόνα. , οπότε o(N+M), τότε κάποιος ρώτησε, τι εάν το N είναι μεγαλύτερο από το M, θα πρέπει να είναι O(N). Τι γίνεται αν το M είναι μεγαλύτερο από το N, οπότε μένουμε εδώ για να είμαστε ασφαλείς.

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Εδώ ψάχνουμε για τη θέση του χαρακτήρα στο str. Εδώ θα προσθέσω ένα σημείο γνώσης:

• Ο υπολογισμός μας O είναι γενικά η πολυπλοκότητα στη χειρότερη περίπτωση ενός αλγορίθμου.
  Εδώ μπορεί να χωριστεί σε τρία επίπεδα πολυπλοκότητας:
  1. Το καλύτερο σενάριο
  Για να βρείτε τον χαρακτήρα στην πρώτη θέση της συμβολοσειράς, τότε:
  F (N) = 1, η πολυπλοκότητα είναι o(1)

2. Μέση κατάσταση:
Για να βρείτε τον χαρακτήρα στη μέση της συμβολοσειράς, τότε:
F (N) = N/2,O(N/2)

3. Το χειρότερο σενάριο
Για να βρείτε τον χαρακτήρα στην τελευταία θέση της συμβολοσειράς, τότε:
F (N) = N,O(N)

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Στη χειρότερη περίπτωση, επειδή η υψηλή σειρά διατηρείται και το n/2 αφαιρείται (το πρώτο στοιχείο) και ο συντελεστής (το δεύτερο στοιχείο) αγνοείται, είναι ON^2

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
1
2
3
4
5
6
7
8

Όταν n=2, ο αριθμός των εκτελέσεων είναι 1
Όταν n=4, ο αριθμός των εκτελέσεων είναι 2
Όταν n=16, ο αριθμός των εκτελέσεων είναι 4
Υποθέτοντας ότι ο αριθμός των εκτελέσεων είναι x, τότε 2
x = n
Επομένως ο αριθμός των εκτελέσεων: x = log n
Επομένως: η χειρότερη χρονική πολυπλοκότητα του func5 είναι:
O(log2 ^n)

Διαφορετικά βιβλία έχουν διαφορετικές μεθόδους έκφρασης Οι παραπάνω μέθοδοι γραφής δεν είναι πολύ διαφορετικές

πολυπλοκότητα χώρου

Αυτό που πρέπει να σημειωθεί σχετικά με την πολυπλοκότητα του χώρου είναι ότι η αναπαράσταση υπολογισμού του αντιπροσωπεύεται επίσης με Ο και οι κανόνες του ακολουθούν τους ίδιους τρεις κανόνες με τη χρονική πολυπλοκότητα.

Ειδοποίηση

Ο χώρος στοίβας που απαιτείται όταν εκτελείται η συνάρτηση (αποθήκευση παραμέτρων, τοπικές μεταβλητές, ορισμένες πληροφορίες καταχωρητή, κ.λπ.) έχει καθοριστεί κατά τη μεταγλώττιση, επομένως η πολυπλοκότητα του χώρου καθορίζεται κυρίως από τον πρόσθετο χώρο που απαιτείται ρητά από τη συνάρτηση όταν εκτελείται .

παράδειγμα 1:

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Το πλαίσιο στοίβας συναρτήσεων έχει καθοριστεί κατά τη μεταγλώττιση.
Χρειάζεται μόνο να δώσετε προσοχή στον πρόσθετο χώρο που ζητείται από τη λειτουργία κατά τη διάρκεια του χρόνου εκτέλεσης.
Πρόσθετος χώρος εφαρμογής για το BubbleSort είναι
Υπάρχει περιορισμένος αριθμός τοπικών μεταβλητών, όπως η ανταλλαγή, η οποία χρησιμοποιεί σταθερό επιπλέον χώρο.
Άρα η πολυπλοκότητα του χώρου είναι O(1)