Ringkasan kerumitan pengiraan lapan algoritma pembelajaran mesin biasa

Kerumitan pengiraan ialah ukuran sumber pengiraan (masa dan ruang) yang digunakan oleh algoritma tertentu semasa berjalan.

Kerumitan pengiraan terbahagi kepada dua kategori:

1 Kerumitan masa

Kerumitan masa bukanlah ukuran algoritma atau sekeping kod yang dijalankan di bawah mesin atau mesin tertentu. keadaan. Kerumitan masa secara amnya merujuk kepada kerumitan masa, iaitu fungsi yang secara kualitatif menerangkan masa berjalan algoritma dan membolehkan kami membandingkan algoritma yang berbeza tanpa menjalankannya. Sebagai contoh, algoritma dengan O(n) akan sentiasa berprestasi lebih baik daripada O(n²) kerana kadar pertumbuhannya kurang daripada O(n²).

2. Kerumitan ruang

Sama seperti kerumitan masa ialah fungsi, begitu juga kerumitan ruang. Secara konsepnya ia sama dengan kerumitan masa, cuma gantikan masa dengan ruang. Wikipedia mentakrifkan kerumitan ruang sebagai:

Kerumitan ruang bagi algoritma atau program komputer ialah jumlah ruang storan yang diperlukan untuk menyelesaikan kejadian masalah pengiraan sebagai fungsi bilangan ciri sebagai input.

Di bawah ini kami telah menyusun kerumitan pengiraan beberapa algoritma pembelajaran mesin biasa.

1. Regresi linear

• n= bilangan sampel latihan, f = bilangan ciri
• Kerumitan masa latihan: O(f²n+f³)
• Kerumitan masa ramalan: O(f)
• Kerumitan ruang masa: O(f)

2. Regresi logistik:

• n= Bilangan sampel latihan, f=Bilangan ciri
• Kerumitan masa latihan: O(f*n)
• Kerumitan masa ramalan: O(f)
• Kerumitan Ruang Masa Jalan: O(f)

3. Mesin vektor sokongan:

• n= bilangan sampel latihan, f = bilangan ciri, s= bilangan vektor sokongan
• Kerumitan masa latihan: O(n²) hingga O(n³), kerumitan masa latihan berbeza-beza dengan kernel yang berbeza.
• Kerumitan masa ramalan: O(f) hingga O(s*f): kernel linear ialah O(f), RBF dan polinomial ialah O(s*f)
• Kerumitan ruang masa jalan: O(s)

4. Naive Bayes:

• n=bilangan sampel latihan, f=bilangan ciri, c=bilangan kategori untuk pengelasan
• Kerumitan masa latihan: O(n*f*c)
• Kerumitan masa ramalan: O(c*f)
• Kerumitan ruang masa jalan: O(c *f)

5. Pokok keputusan:

• n= bilangan sampel latihan, f = bilangan ciri, d = kedalaman pokok, p = bilangan nod
• Kerumitan masa latihan: O(n*log(n)*f)
• Kerumitan masa ramalan: O(d)
• Kerumitan ruang masa jalan: O(p)

6. Hutan Rawak:

• n= bilangan sampel latihan, f = bilangan ciri, k = bilangan pokok, p = bilangan nod dalam pokok, d = Kedalaman pokok
• Kerumitan masa latihan: O(n*log(n)*f*k)
• Kerumitan masa ramalan: O(d*k)
• Kerumitan ruang masa jalan: O( p*k)

7. K jiran terdekat:

n= bilangan sampel latihan, f = bilangan ciri, k= bilangan jiran terdekat

Brute:

• Kerumitan masa latihan: O(1)
• Kerumitan masa ramalan: O(n*f+k*f)
• Kerumitan ruang masa jalan: O (n*f)

kd-tree:

• Kerumitan masa latihan: O(f*n*log(n))
• Masa ramalan kerumitan: O(k*log(n))
• Kerumitan ruang masa: O(n*f)

8, K -bermaksud pengelompokan:

• n= bilangan sampel latihan, f = bilangan ciri, k= bilangan kelompok, i = bilangan lelaran
• Kerumitan masa latihan: O(n*f *k*i)
• Kerumitan ruang masa jalan: O(n*f+k*f)

Atas ialah kandungan terperinci Ringkasan kerumitan pengiraan lapan algoritma pembelajaran mesin biasa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!