Algoritma - Klasifikasi Urutan Pertumbuhan Algoritma

Fungsi dan properti yang muncul digunakan untuk mengklasifikasikan algoritma terhadap ukuran tumbuh. Jadi inilah yang kita bahas selanjutnya. Ada beberapa fungsi yang muncul menandakan algoritma yang tepat. Kita bisa mengupas beberapa contoh fungsi untuk perhitungan ini. Tapi sebagian besar algoritma yang kami dijelaskan diplot di sini.

Contoh dari definisi diatas:

  • f(N) ~ a g(N). Pertumbuhan f(N) hanya tergantung dari g(N).
  • 3SUM: ~ 16 t1 N^3 . Orde pertumbuhan dari runtime 3SUM adalah N^3

Sering dikatakan bahwa urutan pertumbuhan 3SUM adalah singkatan untuk waktu proses.

Int count = 0
For (int
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++)
if (a[i] + a[j] +  a[k] == 0)	waktu untuk eksekusi T1
count++;`

Disini kita akan bahas tentang urutan pertumbuhan, namun kita tidak akan berbicara tentang konstanta pengali depan. Biasanya kita akan mengatakan running time atau waktu berjalannya algoritma ini sebanding dengan N log N. Apa artinya ? Itu berarti hipotesis kita adalah ~ C lg N, N lg N, di mana C adalah konstan.

  • Fungsi kecil : 1, log N, N, N log N, N, N2 sudah cukup untuk menggambarkan orde pertumbuhan.

Dan dalam ini plot (maaf tidak memakai skala), jika urutan pertumbuhan adalah logaritmik atau konstan, besar masalahnya tidak berpengaruh. Jika ini linear, pertumbuhan otomatis sebanding dengan N waktu proses, karena ukuran dari waktu proses, meningkat secara bersamaan.

images1

Hal yang sama juga berlaku, jika N log N. Maka algoritma, skala dengan ukuran input sebagai masukan tumbuh.

Algoritma kuadrat, proses waktunya jauh lebih cepat daripada ukuran input sehingga tidak cocok jika menggunakan algoritma dengan input besar.

Algoritma kubik bahkan lebih buruk. Jadi tugas pertama anda temukan algoritma yang benar-benar sederhana, pastikan itu bukan kuadrat atau qubit (N3).

Klasifikasi urutan pertumbuhan sebenarnya berasal dari jenis pola sederhana dalam hal kode yang kita tulis. Jadi kode kita tidak memiliki loop di dalamnya, maka urutan pertumbuhan akan menjadi konstan. Namun kalau kode anda memiliki loop di mana input terbagi menjadi dua dan proses nya akan lebih lambat.

Urutan Pertumbuhan Nama
1 Konstan
Log N logaritmik
N linear
N log N N log N
N2 Kuadrat
Nm Polinomiale
N! Faktorial

Log N merupakan urutan pertumbuhan bersifat logaritmik dan jika Anda melakukan tes penggandaan, waktu tumbuh hampir linier. Namun jika memiliki input besar dan Anda menggandakan ukurannya, hasilnya tidak akan tidak linear lagi.

Bisa kita beri deskripsi begini:

  • 1, konstan dengan tipe kode bentuknya: a = b[0] + b[1];
  • Log N, logaritmik dengan tipe kode bentuknya:

    While (N>1)
    { N = N / 2 ; ….}
    
  • N, linear, dengan tipe kode bentuknya:

    for (int i = 0; i < N; i++)
    { ... }
    
  • N2, kuadrat, tipe kode bentuknya:

    for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
    { ... }
    

    Beberapa masalah dari yang kami ikuti adalah adanya kategori yang sangat menarik yang disebut algoritma N lg N atau linear rhythmic algorithms. Itulah yang muncul dari yang teknik khusus perancangan algoritma yang sering disebut sebagai divide and conquer. Mungkin kedepannya kita bahas.

Jika Anda memiliki double loop seperti dua algoritma penjumlahan, waktu proses sebanding dengan N ^ 2 atau kuadrat. Triple loop seperti algoritma 3-sum disebut model kubik atau N ^ 3.

Untuk algoritma kuadrat atau algoritma kubik, faktor pengganda adalah empat atau delapan double ukuran input untuk algoritma kubik, waktu proses akan naik oleh faktor delapan, dan itulah jenis perhitungan yang dapat Anda lakukan di kepala Anda sambil menunggu program selesai.

  • N3, kubik, tipe kode bentuknya: for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) { ... }

Sekarang kita berbicara fakta, bahwa algoritma kuadrat mungkin berguna saat masa lalu tetapi Situasi bertambah buruk seiring waktu, jadi kita perlu algoritma yang lebih baik. Untuk mengilustrasikan proses pengembangan model matematika untuk menggambarkan kinerja melalui suatu algoritma, kita akan melihat algoritma yang biasa disebut biner pencarian (binary search).

Ini, tujuannya adalah Anda memiliki array of integers yang terurut, katakan Anda diberi kunci. Dan Anda ingin tahu, apakah itu kunci dalam array? Berapa indeksnya? Dan algoritma cepat untuk melakukan ini dikenal sebagai pencarian biner. Pencarian Biner meskipun itu adalah algoritma sederhana yang terkenal, sulit untuk mendapatkan setiap detail dengan benar.