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

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

1. Αποδοτικότητα Αλγορίθμου

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

1. Η έννοια της πολυπλοκότητας

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

2. Η σημασία της πολυπλοκότητας

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

2. Χρονική πολυπλοκότητα

Ορισμός: Στην επιστήμη των υπολογιστών, η χρονική πολυπλοκότητα ενός αλγορίθμου είναι ένας λειτουργικός τύπος T(N), ο οποίος περιγράφει ποσοτικά τον χρόνο εκτέλεσης του αλγορίθμου. Η χρονική πολυπλοκότητα μετρά τη χρονική απόδοση ενός προγράμματος, οπότε γιατί να μην υπολογίσετε τον χρόνο εκτέλεσης του προγράμματος;

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

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

Υπόθεση:

// 请计算⼀下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

Μέσω της παρατήρησης:
Αριθμός βασικών λειτουργιών που εκτελούνται από το Func1:
T(N)=N²+ 2*N + 10

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

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

Η πολυπλοκότητα χώρου είναι επίσης μια μαθηματική έκφραση, η οποία είναι ο πρόσθετος χώρος που εκχωρείται προσωρινά λόγω των αναγκών του αλγορίθμου κατά τη λειτουργία ενός αλγορίθμου.
Η πολυπλοκότητα του χώρου δεν είναι πόσα byte χώρου καταλαμβάνει το πρόγραμμα, επειδή υπό κανονικές συνθήκες, το μέγεθος κάθε αντικειμένου δεν θα διαφέρει πολύ, επομένως η πολυπλοκότητα του χώρου υπολογίζεται από τον αριθμό των μεταβλητών.
Οι κανόνες υπολογισμού της πολυπλοκότητας του χώρου είναι βασικά παρόμοιοι με την πρακτική πολυπλοκότητα και χρησιμοποιείται επίσης ο ασυμπτωτικός συμβολισμός Big O.
Σημείωση: Ο χώρος στοίβας που απαιτείται όταν εκτελείται η συνάρτηση (αποθήκευση παραμέτρων, τοπικές μεταβλητές, ορισμένες πληροφορίες καταχωρητή, κ.λπ.) έχει καθοριστεί κατά τη μεταγλώττιση, επομένως η πολυπλοκότητα του χώρου καθορίζεται κυρίως από τον πρόσθετο χώρο που απαιτείται ρητά από τη συνάρτηση κατά τη διάρκεια του χρόνου εκτέλεσης . Σίγουρος
Ο χώρος δεν είναι βασικός παράγοντας στην τρέχουσα ανάπτυξη υπολογιστών, αλλά η υπερβολική σπατάλη θα πρέπει να αποφευχθεί.

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

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

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

Η χειρότερη περίπτωση: μέγιστος αριθμός διαδρομών (άνω όριο) για οποιοδήποτε μέγεθος εισόδου
Μέση περίπτωση: αναμενόμενος αριθμός εκτελέσεων για οποιοδήποτε μέγεθος εισόδου
Καλύτερη περίπτωση: ελάχιστος αριθμός εκτελέσεων (κάτω όριο) για οποιοδήποτε μέγεθος εισόδου
Στην πράξη, η ασυμπτωτική αναπαράσταση του Big O γενικά εστιάζει στο άνω όριο του αλγορίθμου, που είναι η χειρότερη κατάσταση λειτουργίας.

5. Περιπτώσεις Υπολογιστικής Πολυπλοκότητας

1. Υπολογίστε την πολυπλοκότητα της συνάρτησης Func1

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

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

Παραλείψτε τον κωδικό που εκτελείται μία φορά, όπως count=0, αυτόν τον κωδικό.
Διατηρήστε τον αριθμό των εκτελέσεων κώδικα που έχουν μεγάλο αντίκτυπο στο χρόνο εκτέλεσης
Ο αριθμός των εκτελέσεων του πρώτου βρόχου είναι μια εκτέλεση διπλού βρόχου του NΝ
Ο δεύτερος βρόχος είναι ένα επίπεδο εκτέλεσης βρόχου φορές 2Ν
Ο τρίτος κύκλος είναι 10 φορές
Το άθροισμα του αριθμού των εκτελέσεων είναι T(N)=N²+2*N+10
Το Big O αντιπροσωπεύει την πολυπλοκότητα του χρόνου, απορρίψτε το μικρό αντίκτυπο και πάρτε το όριο
ΕΠΙ²)

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

Η συνάρτηση Func1 ισχύει για το μέγεθος του χώρου Για παράδειγμα, int count = 0, ισχύει για το μέγεθος του χώρου του τύπου int M=10, ισχύει και για το διάστημα του τύπου int.
Αυτά τα δύο κενά χρησιμοποιούνται επίσης στον βρόχο χωρίς πρόσθετο χώρο εφαρμογής.
Το μέγεθος του χώρου εφαρμογής είναι σταθερό
Η πολυπλοκότητα του χώρου που εκφράζεται στο Big O είναι:
O(1)

2. Υπολογίστε τη χρονική πολυπλοκότητα του Fun2

void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	} 
	int M = 10;
	while (M--)
	{
		++count;
	} 
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

Ο αριθμός των φορών που εκτελείται ο κώδικας είναι μεγαλύτερος από τον πρώτο βρόχο, ο οποίος είναι N*2.
Ο δεύτερος βρόχος εκτελείται 10 φορές
Χρησιμοποιήστε το μεγάλο O για να αναπαραστήσετε την πολυπλοκότητα του χρόνου. Ο μεγαλύτερος αντίκτυπος είναι 2*N.
ΕΠΙ)

3. Υπολογίστε τη χρονική πολυπλοκότητα του 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

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

Υπάρχουν δύο άγνωστα, και ο μεγαλύτερος αντίκτυπος είναι στους δύο βρόχους
Ο πρώτος βρόχος εκτελείται M φορές
Ο δεύτερος βρόχος εκτελείται Ν φορές
Θα πρέπει να είναι ένας άγνωστος αριθμός, δεν είμαι σίγουρος ποιος είναι μεγαλύτερος και ποιος είναι μικρότερος.
O(M+N)

4. Υπολογίστε τη χρονική πολυπλοκότητα του Func4

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9

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

Ο μεγαλύτερος αντίκτυπος εδώ είναι ένας κύκλος
Ο αριθμός των φορών που τρέχει ο βρόχος είναι 100
είναι μια σταθερή σταθερά
O(1)

5. Υπολογίστε τη χρονική πολυπλοκότητα του strchr

const char* strchr(const char* str, int character)
{
	const char* p_begin = str;
	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

Η συνάρτηση που επιτυγχάνεται από αυτή τη συνάρτηση είναι να βρεθεί ο δείκτης ενός χαρακτήρα σε έναν πίνακα.
Ο αριθμός των διαδρομών εδώ είναι αβέβαιος
Είναι δυνατό να βρείτε F(N)=1 με μία κίνηση
Είναι δυνατό να βρεθεί F(N)=N/2 στη μέση
Μπορεί να βρεθεί στο τέλος ή NULL επιστρέφεται εάν δεν βρεθεί, F(N)=N
Το Big O παίρνει το χειρότερο σενάριο:
Η χρονική πολυπλοκότητα είναι O(N)

6. Υπολογίστε τη χρονική πολυπλοκότητα του Func5

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

Αυτός ο αριθμός των εκτελέσεων σχετίζεται με το μέγεθος του n, αλλά δεν επαναλαμβάνεται n φορές Η τιμή της μεταβλητής βρόχου cnt θα φτάσει το 1024.
Υποθέτοντας ότι ο αριθμός των κύκλων είναι x, τότε 2^Χ=n
x=logn
Άρα η χρονική πολυπλοκότητα είναι: O(longn)

7. Υπολογίστε την πολυπλοκότητα του BubbleSor

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

Αυτή η συνάρτηση ολοκληρώνει την αύξουσα ταξινόμηση με φυσαλίδες
Υπάρχει ένας βρόχος εδώ. Αυτός ο βρόχος είναι ένας ένθετος βρόχος δύο επιπέδων.
Ο αριθμός των βρόχων δεν έχει καθοριστεί
Το χειρότερο σενάριο είναι ότι ο εξωτερικός βρόχος εκτελείται n φορές
Τότε ο εσωτερικός βρόχος θα τρέξει (n-1)+(n-2)+(n-3)+……+2+1+0
είναι μια αριθμητική ακολουθία και το άθροισμα είναι:

Η χρονική πολυπλοκότητα είναι: O(N)

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

Δεν υπάρχει πρόσθετος χώρος εφαρμογής και ο εφαρμοσμένος χώρος είναι σταθερός.
O(1)

8. Η πολυπλοκότητα του υπολογισμού της παραγοντικής αναδρομής Fac

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}
1
2
3
4
5
6

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

Αναδρομικά N φορές
Άρα η χρονική πολυπλοκότητα είναι: O(N)

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

Κάθε φορά που επαναλαμβάνετε, πρέπει να κάνετε αίτηση για χώρο.
Αναστράφηκε N φορές και εφαρμόστηκε για N φορές του χώρου.
Η πολυπλοκότητα του χώρου είναι: O(N)