Artikel untuk membincangkan tentang kerumitan masa dan kerumitan ruang bagi algoritma

Artikel ini akan mempelajari tentang algoritma dan memperkenalkan kerumitan masa dan kerumitan ruang bagi algoritma ini.

Algoritma merujuk kepada satu set kaedah yang digunakan untuk memanipulasi data dan menyelesaikan masalah program. Untuk masalah yang sama, menggunakan algoritma yang berbeza, hasil akhir mungkin sama, tetapi sumber dan masa yang digunakan dalam proses akan sangat berbeza.

Jadi bagaimana kita harus mengukur kebaikan dan keburukan algoritma yang berbeza?

Pertimbangkan terutamanya daripada dua dimensi "masa" dan "ruang" yang diduduki oleh algoritma.

• Dimensi masa: merujuk kepada masa yang digunakan dalam melaksanakan algoritma semasa Kami biasanya menggunakan "kerumitan masa" untuk menerangkannya.

• Dimensi ruang: merujuk kepada jumlah ruang memori yang diperlukan untuk melaksanakan algoritma semasa Kami biasanya menggunakan "kerumitan ruang" untuk menerangkannya.

Oleh itu, menilai kecekapan algoritma bergantung terutamanya pada kerumitan masa dan kerumitan ruangnya. Walau bagaimanapun, kadangkala masa dan ruang ialah "sediakan kek anda dan makan juga," dan anda tidak boleh memiliki kedua-duanya, jadi kami perlu mencari titik keseimbangan.

Izinkan saya memperkenalkan kaedah pengiraan "kerumitan masa" dan "kerumitan ruang" masing-masing.

1. Kerumitan masa

Kami ingin mengetahui "kerumitan masa" sesuatu algoritma Cara pertama yang difikirkan oleh ramai orang ialah menjalankan program algoritma sekali Masa akan datang secara semula jadi.

Adakah ini mungkin? Sudah tentu anda boleh, tetapi ia juga mempunyai banyak kelemahan.

Kaedah ini sangat terdedah kepada pengaruh persekitaran operasi Hasil yang dijalankan pada mesin berprestasi tinggi akan sangat berbeza daripada hasil yang dijalankan pada mesin berprestasi rendah. Dan ia juga mempunyai banyak kaitan dengan skala data yang digunakan dalam ujian. Tambahan pula, apabila kami menulis algoritma, kami masih tidak mempunyai cara untuk menjalankannya sepenuhnya.

Oleh itu, satu lagi kaedah yang lebih umum telah keluar: " Tatatanda O Besar ", iaitu, T(n) = O(f(n))

Mari kita lihat pada contoh dahulu:

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

Menggunakan "notasi O Besar", kerumitan masa kod ini ialah: O(n), kenapa ?

Dalam Notasi O Besar, formula untuk kerumitan masa ialah: T(n) = O( f(n) ), di mana f(n) mewakili jumlah bilangan pelaksanaan setiap baris kod, dan O mewakili hubungan berkadar. Nama penuh formula ini ialah: Kerumitan masa asimptotik algoritma.

Mari kita teruskan melihat contoh di atas Andaikan bahawa masa pelaksanaan setiap baris kod adalah sama Kami menggunakan 1 masa partikel untuk menyatakannya. dan baris ketiga kod mengambil masa 1 zarah Masa pelaksanaan baris ialah n masa berbutir, dan masa pelaksanaan baris keempat juga adalah masa berbutir (baris kedua dan kelima ialah simbol, abaikan mereka buat masa ini), maka jumlah masa ialah 1 masa berbutir n masa berbutir n masa berbutir, iaitu (1 2n) masa zarah, iaitu: T(n) = (1 2n)*masa zarah penggunaan algoritma ini berubah dengan perubahan n Oleh itu, kita boleh memudahkan Ungkapkan kerumitan masa algoritma ini sebagai: T(n) = O(n)

Mengapa ia boleh dipermudahkan dengan cara ini? notasi O besar tidak digunakan untuk benar-benar mewakili masa pelaksanaan algoritma , yang digunakan untuk mewakili trend pertumbuhan masa pelaksanaan kod.

Jadi dalam contoh di atas, jika n adalah tak terhingga, pemalar 1 dalam T(n) = masa(1 2n) adalah tidak bermakna, dan gandaan 2 juga tidak bermakna. Oleh itu ia boleh dipermudahkan kepada T(n) = O(n).

Metrik kerumitan masa biasa ialah:

• Tertib malar O(1)

• Tertib logaritma O(logN )

• Tertib linear O(n)

• Tertib logaritma linear O(nlogN)

• Tertib segi empat sama O (n²)

• Pesanan kubik O(n³)

• K order O(n^k)

• Tertib eksponen (2^n)

Kerumitan masa dari atas ke bawah semakin lama semakin besar, dan kecekapan pelaksanaan semakin rendah .

Yang berikut memilih beberapa yang lebih biasa digunakan untuk diterangkan (tidak mengikut urutan yang ketat):

• Pesanan tetap O(1)

Tidak kira berapa banyak baris kod yang dilaksanakan, selagi tiada struktur kompleks seperti gelung, kerumitan masa kod ini akan menjadi O(1 ), seperti:

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

Apabila kod di atas dilaksanakan, penggunaannya tidak meningkat dengan pertumbuhan pembolehubah tertentu, jadi tidak kira berapa lama jenis kod ini, walaupun ia berpuluh-puluh. daripada beribu-ribu atau ratusan ribu baris, O(boleh digunakan 1) untuk menyatakan kerumitan masanya.

• Linear order O(n)

Ini adalah dalam contoh kod awal I telah menjelaskannya, seperti:

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

Kod ini, kod dalam gelung for akan dilaksanakan sebanyak n kali, jadi masa yang digunakan berubah dengan perubahan n, jadi kod jenis ini Its kerumitan masa boleh dinyatakan sebagai O(n).

• Tertib logaritma O(logN)

Mari lihat kod dahulu:

int i = 1;
while(i<n)
{
    i = i * 2;
}

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n

也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

• 线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

就拿上面的代码加一点修改来举例：

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

• 平方阶O(n²)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

举例：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)

如果将其中一层循环的n改成m，即：

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

那它的时间复杂度就变成了 O(m*n)

• 立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。

二、空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

• 空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

• 空间复杂度 O(n)

我们先看一个代码：

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

以上，就是对算法的时间复杂度与空间复杂度基础的分析，欢迎大家一起交流。

更多算法相关知识，请访问：编程入门！！

Atas ialah kandungan terperinci Artikel untuk membincangkan tentang kerumitan masa dan kerumitan ruang bagi algoritma. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!