Python - Analisis Algoritma

Analisis Algoritma

Efisiensi suatu algoritma dapat dianalisis pada dua tahap yang berbeda, sebelum implementasi dan setelah implementasi. Mereka adalah sebagai berikut -

A Priori Analysis- Ini adalah analisis teoritis dari suatu algoritma. Efisiensi algoritme diukur dengan mengasumsikan bahwa semua faktor lain, misalnya, kecepatan prosesor, adalah konstan dan tidak berpengaruh pada implementasi.
A Posterior Analysis- Ini adalah analisis empiris dari suatu algoritma. Algoritma yang dipilih diimplementasikan dengan menggunakan bahasa pemrograman. Ini kemudian dieksekusi pada mesin komputer target. Dalam analisis ini, statistik aktual seperti waktu dan ruang berjalan yang diperlukan, dikumpulkan.

Kompleksitas Algoritma

Seharusnya X adalah sebuah algoritma dan n adalah ukuran data masukan, waktu dan ruang yang digunakan oleh algoritma X adalah dua faktor utama yang menentukan efisiensi X.

Time Factor - Waktu diukur dengan menghitung jumlah operasi kunci seperti perbandingan dalam algoritma pengurutan.
Space Factor - Ruang diukur dengan menghitung ruang memori maksimum yang dibutuhkan oleh algoritma.

Kompleksitas suatu algoritma f(n) memberikan waktu berjalan dan / atau ruang penyimpanan yang dibutuhkan oleh algoritme dalam hal n sebagai ukuran data masukan.

Kompleksitas Ruang

Kompleksitas ruang suatu algoritma merepresentasikan jumlah ruang memori yang dibutuhkan oleh algoritma dalam siklus hidupnya. Ruang yang dibutuhkan oleh algoritme sama dengan jumlah dari dua komponen berikut -

Bagian tetap yang merupakan ruang yang diperlukan untuk menyimpan data dan variabel tertentu, yang tidak bergantung pada ukuran masalah. Misalnya, variabel dan konstanta sederhana yang digunakan, ukuran program, dll.
Bagian variabel adalah ruang yang dibutuhkan oleh variabel, yang ukurannya bergantung pada ukuran masalah. Misalnya, alokasi memori dinamis, ruang tumpukan rekursi, dll.

Kompleksitas spasi S (P) dari setiap algoritma P adalah S (P) = C + SP (I), di mana C adalah bagian tetap dan S (I) adalah bagian variabel dari algoritma, yang bergantung pada karakteristik instans I. Berikut adalah contoh sederhana yang mencoba menjelaskan konsep -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Di sini kita memiliki tiga variabel A, B, dan C dan satu konstanta. Karenanya S (P) = 1 + 3. Sekarang, ruang bergantung pada tipe data dari variabel yang diberikan dan tipe konstanta dan itu akan dikalikan sesuai.

Kompleksitas Waktu

Kompleksitas waktu suatu algoritme menunjukkan jumlah waktu yang dibutuhkan algoritme untuk berjalan hingga selesai. Persyaratan waktu dapat didefinisikan sebagai fungsi numerik T (n), di mana T (n) dapat diukur sebagai jumlah langkah, asalkan setiap langkah menggunakan waktu yang konstan.

Misalnya, diperlukan penambahan dua bilangan bulat n-bit nLangkah. Akibatnya, waktu komputasi total adalah T (n) = c ∗ n, di mana c adalah waktu yang dibutuhkan untuk penambahan dua bit. Di sini, kami mengamati bahwa T (n) tumbuh secara linier dengan bertambahnya ukuran input.