Kerumitan masa & Kerumitan ruang

Secara amnya, kerumitan masa dan kerumitan ruang ialah cara untuk mengukur kecekapan algoritma berdasarkan cara penggunaan sumbernya berskala dengan saiz inputnya. Mari kita bincangkan perkara asas dan beberapa contoh biasa.

Kerumitan Masa

Kerumitan masa menerangkan jumlah masa yang diambil oleh algoritma untuk diselesaikan berdasarkan saiz input (sering dilambangkan sebagai n).

1. Masa Malar – O(1):

   • Masa pelaksanaan algoritma tidak berubah dengan saiz input.
   • Contoh: Mengakses elemen dalam tatasusunan mengikut indeks, seperti dalam arr[5].

2. Masa Logaritma – O(log n):

   • Masa pelaksanaan algoritma berkembang secara logaritma apabila saiz input bertambah, bermakna ia membahagikan masalah kepada separuh dengan setiap langkah.
   • Contoh: Carian binari pada tatasusunan yang diisih.

3. Masa Linear – O(n):

   • Masa pelaksanaan algoritma berkembang secara linear dengan saiz input.
   • Contoh: Melintasi susunan n elemen sekali.

4. Masa Linearitma – O(n log n):

   • Lazim dalam algoritma pengisihan yang cekap di mana setiap elemen dikendalikan secara logaritma, biasanya disebabkan oleh pembahagian rekursif dan penggabungan atau pemprosesan linear.
   • Contoh: Cantum isihan, isihan pantas.

5. Masa Kuadratik – O(n²):

   • Masa pelaksanaan berkembang secara berkadar dengan segi empat sama saiz input.
   • Contoh: Gelung bersarang, seperti membandingkan setiap elemen dalam tatasusunan dengan setiap elemen lain.

6. Masa Kubik – O(n³):

   • Masa pelaksanaan bertambah dengan kiub saiz input. Jarang tetapi boleh berlaku dalam algoritma dengan tiga gelung bersarang.
   • Contoh: Menyelesaikan operasi matriks tertentu menggunakan algoritma brute-force.

7. Masa Eksponen – O(2^n):

   • Masa pelaksanaan berganda dengan setiap elemen tambahan dalam input, biasanya daripada algoritma rekursif yang menyelesaikan submasalah dalam semua kombinasi yang mungkin.
   • Contoh: Penyelesaian naif untuk jujukan Fibonacci, di mana setiap panggilan membawa kepada dua lagi panggilan.

8. Masa Faktorial – O(n!):

   • Masa pelaksanaan berkembang secara berfaktor dengan saiz input. Selalunya daripada algoritma yang melibatkan penjanaan semua pilih atur atau gabungan yang mungkin.
   • Contoh: Menyelesaikan masalah jurujual mengembara dengan kekerasan.

Kerumitan Ruang

Kerumitan ruang mengukur jumlah memori yang digunakan oleh algoritma berbanding saiz input.

1. Ruang Malar – O(1):

   • Algoritma menggunakan jumlah memori tetap tanpa mengira saiz input.
   • Contoh: Menyimpan beberapa pembolehubah, seperti integer atau pembilang.

2. Ruang Logaritma – O(log n):

   • Penggunaan memori berkembang secara logaritma, sering dilihat dengan algoritma rekursif yang mengurangkan separuh masalah setiap langkah.
   • Contoh: Carian binari rekursif (kerumitan ruang disebabkan timbunan panggilan).

3. Ruang Linear – O(n):

   • Penggunaan memori berkembang secara linear dengan saiz input, biasa apabila membuat tatasusunan tambahan atau struktur data untuk menyimpan input.
   • Contoh: Membuat salinan tatasusunan saiz n.

4. Ruang Kuadratik – O(n²):

   • Penggunaan memori berkembang dengan segi empat sama saiz input, seperti apabila menyimpan matriks 2D bersaiz n x n.
   • Contoh: Menyimpan matriks bersebelahan untuk graf dengan n nod.

5. Ruang Eksponen – O(2^n):

   • Penggunaan memori berkembang pesat dengan saiz input, selalunya dalam penyelesaian rekursif yang menyimpan data untuk setiap subset input yang mungkin.
   • Contoh: Memoisasi dalam algoritma rekursif dengan banyak submasalah yang bertindih.

Contoh Praktikal

• Masa Linear (O(n)) dan Ruang Linear (O(n)):

  • Fungsi yang berulang melalui tatasusunan dan menyimpan setiap elemen dalam tatasusunan baharu.

• Masa Kuadratik (O(n²)) dan Ruang Malar (O(1)):

  • Fungsi yang mempunyai dua gelung bersarang pada tatasusunan tetapi tidak memerlukan storan tambahan melebihi beberapa pembolehubah.

Menganalisis Kerumitan

Apabila menganalisis kod untuk kerumitan masa dan ruang:

1. Kenal pasti gelung: Gelung bersarang biasanya meningkatkan kerumitan (cth., satu gelung memberi ( O(n) ); dua gelung bersarang memberi ( O(n^2) )).
2. Cari rekursi: Panggilan rekursif boleh membawa kepada kerumitan masa dan ruang eksponen, bergantung pada faktor percabangan dan kedalaman rekursi.
3. Pertimbangkan struktur data: Menggunakan struktur data tambahan seperti tatasusunan, senarai atau peta cincang boleh menjejaskan kerumitan ruang.

Petua Umum

• Kerumitan Masa ialah tentang mengira operasi sebagai fungsi saiz input.
• Kerumitan Angkasa ialah tentang mengira jumlah memori tambahan yang diperlukan.

Dengan menilai faktor ini, anda boleh menganggarkan prestasi algoritma dan jumlah memori yang digunakan berdasarkan saiz input.

Atas ialah kandungan terperinci Kerumitan masa & Kerumitan ruang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!