Berbagi teknologi

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

1. Efisiensi Algoritma

Ada banyak cara dan metode dalam proses menyelesaikan masalah algoritma yang sama. Hasil akhirnya sama dan benar, tetapi efisiensinya mungkin berbeda-beda.
Ibarat memulai dari tempat yang sama dan tiba di tempat lain, cara mencapai tempat tersebut antara lain dengan pesawat, kereta api, mobil pribadi... namun waktu yang dibutuhkan berbeda dan perekonomian juga berbeda.

1. Konsep kompleksitas

Setelah algoritma ditulis ke dalam program yang dapat dieksekusi, memerlukan sumber daya waktu dan sumber daya ruang (memori) untuk dijalankan. Oleh karena itu, kualitas suatu algoritma umumnya diukur dari dua dimensi: waktu dan ruang, yaitu kompleksitas waktu dan kompleksitas ruang.
Kompleksitas waktu terutama mengukur seberapa cepat suatu algoritma berjalan, sedangkan kompleksitas ruang terutama mengukur ruang ekstra yang diperlukan untuk menjalankan suatu algoritma.
Pada masa awal perkembangan komputer, komputer mempunyai kapasitas penyimpanan yang sangat kecil. Jadi kami sangat peduli dengan kompleksitas ruang. Namun setelah pesatnya perkembangan industri komputer, kapasitas penyimpanan komputer telah mencapai tingkat yang sangat tinggi. Jadi sekarang kita tidak perlu lagi memberikan perhatian khusus pada kompleksitas ruang suatu algoritma.

2. Pentingnya kompleksitas

Saat saya memainkan beberapa game, ponsel saya akan menjadi sangat panas saat saya memainkan beberapa game, dan beberapa game tidak akan panas jika saya memainkannya, hal ini tidak terlepas dari kerumitannya Algoritmanya rumit untuk dijalankan, untuk memastikan waktu yang digunakan lebih sedikit, daya penuh harus diaktifkan, sehingga akan menjadi panas.

2. Kompleksitas waktu

Definisi: Dalam ilmu komputer, kompleksitas waktu suatu algoritma adalah rumus fungsional T(N), yang secara kuantitatif menggambarkan waktu berjalannya suatu algoritma. Kompleksitas waktu mengukur efisiensi waktu suatu program, jadi mengapa tidak menghitung waktu berjalannya program?

• Karena waktu berjalan program berkaitan dengan konfigurasi lingkungan kompilasi dan mesin yang sedang berjalan, misalnya jika suatu program algoritma dikompilasi dengan kompiler lama atau dikompilasi dengan kompiler baru, maka waktu berjalan akan berbeda pada mesin yang sama.
• Program algoritma yang sama memiliki waktu berjalan yang berbeda menggunakan mesin lama dengan konfigurasi rendah dan mesin baru dengan konfigurasi tinggi.
• Dan waktu hanya dapat diuji setelah program ditulis, tidak dihitung dan dievaluasi melalui pemikiran teoritis sebelum program ditulis.

Oleh karena itu, ketika menilai derajat penugasan waktu suatu algoritma, waktu untuk mengeksekusi algoritma tidak dipertimbangkan, hanya jumlah instruksi yang dieksekusi.

Kasus:

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

Melalui observasi:
Jumlah operasi dasar yang dilakukan oleh Func1:
T(N) = Tidak²+ 2*N + 10

Dalam praktiknya, ketika kita menghitung kompleksitas waktu, kita tidak menghitung jumlah pasti eksekusi suatu program. Menghitung jumlah pasti eksekusi masih sangat merepotkan (kalimat kode program yang berbeda akan memiliki jumlah instruksi yang dikompilasi berbeda (seperti ini), menghitung jumlah pasti eksekusi tidak terlalu penting, karena kita hanya ingin membandingkan tingkat pertumbuhan program algoritma dalam menghitung kompleksitas waktu, yaitu selisih T(N) ketika N terus meningkat Telah dilihat di atas bahwa konstanta dan suku-suku orde rendah mempunyai pengaruh yang kecil terhadap hasil ketika N terus bertambah, jadi kita hanya perlu menghitung perkiraan jumlah eksekusi yang dapat diwakili oleh program untuk meningkatkan urutan besarnya biasanya digunakan Gunakan notasi asimtotik Big O.

3. Kompleksitas ruang

Kompleksitas ruang juga merupakan ekspresi matematika, yaitu ruang tambahan yang dialokasikan sementara karena kebutuhan algoritma selama pengoperasian suatu algoritma.
Kompleksitas ruang bukanlah berapa byte ruang yang ditempati program. Karena dalam keadaan normal, ukuran setiap objek tidak akan berbeda jauh, sehingga kompleksitas ruang dihitung berdasarkan jumlah variabel.
Aturan penghitungan kompleksitas ruang pada dasarnya mirip dengan kompleksitas praktis, dan notasi asimtotik Big O juga digunakan.
Catatan: Ruang tumpukan yang diperlukan saat fungsi berjalan (penyimpanan parameter, variabel lokal, beberapa informasi register, dll.) telah ditentukan selama kompilasi, sehingga kompleksitas ruang terutama ditentukan oleh ruang tambahan yang secara eksplisit diterapkan oleh fungsi selama runtime . Tentu
Ruang bukanlah pertimbangan utama dalam pengembangan komputer saat ini, namun pemborosan yang berlebihan harus dihindari.

4. Representasi asimtotik Big O

Notasi O Besar: Ini adalah simbol matematika yang digunakan untuk menggambarkan perilaku fungsi asimtotik.
Aturan untuk mendorong ke notasi asimtotik Big O:

• 1. Dalam rumus fungsional kompleksitas waktu T(N), hanya suku-suku orde tertinggi yang dipertahankan dan suku-suku orde rendah dihilangkan, karena ketika N terus bertambah,
  Dampak suku-suku orde rendah pada hasil semakin kecil, dan jika N tak terhingga, maka dapat diabaikan.
• 2. Jika suku orde tertinggi ada dan bukan 1, hilangkan koefisien konstan suku ini, karena seiring bertambahnya N, koefisien ini
  Dampaknya pada hasil semakin kecil, dan jika N tidak terbatas, maka dapat diabaikan.
• 3. Jika tidak ada N item yang berhubungan di T(N) tetapi hanya item yang konstan, ganti semua konstanta penjumlahan dengan konstanta 1.

Kasus terburuk: jumlah maksimum proses (batas atas) untuk ukuran input apa pun
Kasus rata-rata: jumlah proses yang diharapkan untuk ukuran input apa pun
Kasus terbaik: jumlah minimum proses (batas bawah) untuk ukuran input apa pun
Dalam praktiknya, representasi asimtotik Big O umumnya berfokus pada batas atas algoritme, yang merupakan situasi pengoperasian terburuk.

5. Kasus Kompleksitas Komputasi

1. Hitung kompleksitas fungsi 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

kompleksitas waktu:

Hilangkan kode yang dijalankan satu kali, misalnya count=0, kode ini.
Pertahankan jumlah eksekusi kode yang berdampak besar pada waktu berjalan
Banyaknya eksekusi loop pertama adalah eksekusi double loop sebesar NN
Loop kedua adalah lapisan eksekusi loop kali 2N
Siklus ketiga sebanyak 10 kali
Jumlah jumlah eksekusi adalah T(N)=N²+2*N+10
Big O mewakili kompleksitas waktu, buang dampak kecil dan ambil batasannya
PADA²)

Kompleksitas ruang:

Fungsi Func1 berlaku untuk ukuran spasi. Misalnya int count = 0, berlaku untuk ukuran spasi bertipe int. Int M=10, juga berlaku untuk spasi bertipe int.
Kedua spasi ini juga digunakan dalam loop tanpa ruang aplikasi tambahan.
Ukuran ruang aplikasi konstan
Kompleksitas ruang yang dinyatakan dalam Big O adalah:
O(1)

2. Hitung kompleksitas waktu 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

kompleksitas waktu:

Berapa kali kode dijalankan lebih besar dari loop pertama, yaitu N*2.
Putaran kedua dijalankan sebanyak 10 kali
Gunakan O besar untuk mewakili kompleksitas waktu. Dampak terbesar adalah 2*N. Suku koefisien sebelumnya dihilangkan:
PADA)

3. Hitung kompleksitas waktu 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

kompleksitas waktu

Ada dua hal yang tidak diketahui, dan dampak yang lebih besar terjadi pada kedua putaran tersebut
Loop pertama dijalankan sebanyak M kali
Loop kedua dijalankan sebanyak N kali
Itu pasti nomor yang tidak diketahui. Saya tidak yakin mana yang lebih besar dan mana yang lebih kecil.
O(M+N)

4. Hitung kompleksitas waktu 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

kompleksitas waktu:

Dampak terbesar di sini adalah sebuah siklus
Berapa kali loop dijalankan adalah 100
adalah konstanta tetap
O(1)

5. Hitung kompleksitas waktu 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

Fungsi yang dilakukan oleh fungsi ini adalah untuk menemukan subskrip karakter dalam array.
Jumlah lari di sini tidak pasti
Dimungkinkan untuk menemukan F(N)=1 sekaligus
Dimungkinkan untuk menemukan F(N)=N/2 di tengah
Ini mungkin ditemukan di akhir, atau NULL dikembalikan jika tidak ditemukan, F(N)=N
Big O mengambil skenario terburuk:
Kompleksitas waktunya adalah O(N)

6. Hitung kompleksitas waktu Func5

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

Jumlah proses ini terkait dengan ukuran n, tetapi tidak melakukan loop sebanyak n kali. Seharusnya karena variabel loop akan dikalikan dengan 2 selama loop, dan loop akan keluar dengan cepat nilai variabel loop cnt akan mencapai 1024.
Asumsikan banyaknya siklus adalah x, maka 2^X=n
x=login
Jadi kompleksitas waktunya adalah: O(longn)

7. Hitung kompleksitas 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

Fungsi ini menyelesaikan penyortiran naik gelembung
Ada perulangan di sini. Perulangan ini adalah perulangan bertingkat dua.
Jumlah loop tidak ditentukan
Skenario terburuknya adalah loop luar dijalankan sebanyak n kali
Kemudian loop dalam akan berjalan (n-1)+(n-2)+(n-3)+……+2+1+0
adalah barisan aritmatika, dan jumlahnya adalah:

Kompleksitas waktu adalah: O(N)

Kompleksitas ruang:

Tidak ada ruang lamaran tambahan, dan ruang yang diterapkan adalah konstan.
O(1)

8. Kompleksitas perhitungan rekursi faktorial Fac

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

kompleksitas waktu:

Berulang N kali
Jadi kompleksitas waktunya adalah: O(N)

Kompleksitas ruang:

Setiap kali Anda kambuh, Anda perlu mengajukan permohonan ruang.
Berulang N kali dan diterapkan untuk N kali ruang.
Kompleksitas ruang adalah: O(N)