Berbagi teknologi

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

Kata pengantar

Jika Anda ingin mengetahui apa itu kompleksitas ruang/waktu, Anda harus mengetahui apa itu struktur data.

Hal ini dapat dipahami pada dua tingkatan. Data ada di mana-mana dalam hidup kita, seperti acara internasional yang menjadi topik hangat di Douyin, pelepasan baju besi Yongzheng, dll. Yang dapat dilihat pengguna kami adalah data yang disimpan Douyin di server backend. Namun semua data ini memiliki satu karakteristik, yaitu semuanya ada dalam daftar pencarian terpopuler Douyin, dan daftar ini disusun untuk memastikan bahwa data berada di lokasi tetap untuk dijelajahi pengguna.

Selain itu, dengan struktur data, algoritma tidak dapat dipisahkan. Seperti yang baru saja kami katakan, struktur data menyimpan data secara teratur dalam suatu struktur, jadi cara mengakses data secara efisien dari struktur tersebut adalah dengan algoritma.

kompleksitas waktu

Dengan algoritma, terdapat kompleksitas waktu dan kompleksitas ruang. Karena memori komputer semakin besar, kompleksitas waktu lebih penting daripada kompleksitas ruang.Jadi, pertama-tama mari kita pahami kompleksitas waktu

konsep

Kompleksitas waktu, yang paling penting adalah waktu, waktu disini mengacu pada waktu ketika suatu program sedang berjalan. Jika kompleksitas waktu lebih kecil maka algoritma terbukti lebih baik.Perhitungan kompleksitas waktu dinyatakan dengan rumus fungsional T(N)

Jadi mengapa kita tidak menghitung kompleksitas waktu program ini terlebih dahulu dan menulis kode untuk solusi optimal? Ini melibatkan masalah komputer.

1. Karena waktu berjalan program berkaitan dengan lingkungan kompilasi dan konfigurasi mesin yang sedang berjalan, misalnya program algoritma menggunakan kompiler lama
   Kompilasi dengan kompiler baru dan kompilasi dengan kompiler baru memiliki waktu berjalan yang berbeda pada mesin yang sama.
2. Program algoritma yang sama memiliki waktu berjalan yang berbeda menggunakan mesin lama dengan konfigurasi rendah dan mesin baru dengan konfigurasi tinggi.
3. Dan waktu hanya dapat diuji setelah program ditulis, tidak dihitung dan dievaluasi melalui pemikiran teoritis sebelum program ditulis.

Mari kita lihat sepotong kode:

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

Jika Anda melihat kode ini berdasarkan jumlah eksekusi hitungan, seharusnya:
Rumus untuk T(N) adalah N2 + 2 ∗ N + 10.
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

Saat ini, seseorang berkata, apakah int count=0 tidak dihitung;

Di sini kita terlalu meremehkan komputer kita. CPU komputer kita dapat mengeksekusi ratusan juta kali per detik. Tentu saja, waktu kecil ini dapat diabaikan. Oleh karena itu, kompleksitas waktu yang kami hitung tidak akurat, ini hanya perkiraan kasar. Saat ini, kami menggunakan simbol baru untuk mewakilinya.

Representasi asimtotik dari Big O

Notasi O Besar: Ini adalah simbol matematika yang digunakan untuk menggambarkan perilaku asimtotik suatu fungsi; di sini digunakan untuk mewakili perkiraan kompleksitas waktu.

Jadi apakah di sini masih dihitung seperti T(N)? Jika demikian, kita tidak perlu menggunakan simbol lain untuk mewakilinya. Ini melibatkan aturan untuk menghitung O:

1. Dalam rumus fungsional kompleksitas waktu T(N), hanya suku tingkat tertinggi yang dipertahankan dan suku tingkat rendah dihilangkan, karena ketika N terus meningkat, dampak suku tingkat rendah terhadap hasil menjadi semakin kecil. Ketika N menjadi tak terhingga, maka N dapat diabaikan.
2. Jika suku orde tertinggi ada dan bukan 1, hilangkan koefisien konstan suku ini, karena seiring dengan bertambahnya N, pengaruh koefisien ini terhadap hasil akan semakin kecil. Ketika N tak terhingga, 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.

Kemudian lihat T(N)=N^ 2 + 2 ∗ N + 10 di atas. Orde tertinggi di sini adalah N2, jadi menghilangkan orde rendah lainnya, kompleksitasnya adalah (ON^2)

Helikopter skala kecil

// 计算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

Di sini T(N)=M+N, lalu mari kita hitung lagi O(N) dan M dan N di sini keduanya berorde sama, sehingga tidak memenuhi aturan pertama, dan tidak sesuai dengan aturan kedua dan ketiga. , jadi o(N+M), lalu ada yang bertanya, bagaimana jika N lebih besar dari M, haruskah O(N). Bagaimana jika M lebih besar dari N, jadi kita tetap di sini untuk berjaga-jaga.

// 计算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

Disini kita mencari posisi karakter di str. Disini saya akan menambahkan poin pengetahuan:

• Perhitungan O kami umumnya merupakan kompleksitas algoritma yang terburuk.
  Di sini dapat dibagi menjadi tiga tingkat kerumitan:
  1. Skenario kasus terbaik
  Untuk mencari karakter pada posisi pertama string, maka:
  F (N) = 1, kompleksitasnya o(1)

2. Situasi rata-rata:
Untuk mencari karakter di tengah string, maka:
F(N) = N/2,O(N/2)

3. Skenario terburuk
Untuk mencari karakter pada posisi terakhir string, maka:
F (N) = Tidak, 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

Dalam kasus terburuk, karena urutan tinggi dipertahankan dan n/2 dihilangkan (item pertama), dan koefisien (item kedua) diabaikan, maka ON^2

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

Ketika n=2, jumlah eksekusi adalah 1
Ketika n=4, jumlah eksekusi adalah 2
Ketika n=16, jumlah eksekusi adalah 4
Dengan asumsi jumlah eksekusi adalah x, maka 2
x = n
Oleh karena itu jumlah eksekusi: x = log n
Oleh karena itu: kompleksitas waktu kasus terburuk dari fungsi5 adalah:
O(log2^n)

Buku yang berbeda memiliki metode ekspresi yang berbeda. Metode penulisan di atas tidak jauh berbeda

kompleksitas ruang

Yang perlu diperhatikan tentang kompleksitas ruang adalah representasi perhitungannya juga diwakili oleh O, dan aturannya mengikuti tiga aturan yang sama dengan kompleksitas waktu.

Melihat

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.

Contoh 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

Bingkai tumpukan fungsi telah ditentukan selama kompilasi.
Anda hanya perlu memperhatikan ruang tambahan yang diminta oleh fungsi tersebut saat runtime.
Ruang aplikasi tambahan untuk BubbleSort adalah
Ada sejumlah variabel lokal seperti pertukaran, yang menggunakan jumlah ruang ekstra yang konstan.
Jadi kompleksitas ruangnya adalah O(1)