Apakah Kerumitan Masa `tambah` dalam Go?

Tambah Kerumitan dalam Go

Masalah:

Apakah kerumitan pengiraan bagi gelung berikut dalam Go?

var a []int
for i := 0 ; i < n ; i++ {
  a = append(a, i)
}

Adakah tambahan beroperasi dalam masa linear, atau dalam pemalar terlunas masa?

Jawapan:

Spesifikasi Bahasa Pengaturcaraan Go menyatakan bahawa tambah melakukan pengagihan semula jika perlu:

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

Walau bagaimanapun, algoritma khusus untuk kembangkan kepingan sasaran apabila perlu adalah bergantung kepada pelaksanaan. Untuk pengkompil gc semasa, algoritma dilunaskan masa malar.

Penjelasan Masa Malar Dilunaskan:

Kapasiti hirisan ditingkatkan dengan cara yang tamak:

• Jika kapasiti lama lebih besar daripada dua kali ganda kapasiti lama, kapasiti baharu ditetapkan kepada kapasiti lama kapasiti.
• Jika tidak, jika panjang lama kurang daripada 1024, kapasiti baharu ditetapkan untuk menggandakan kapasiti lama.
• Jika tidak, kapasiti baharu dinaikkan sebanyak satu perempat sehingga ia berada pada sekurang-kurangnya saiz kapasiti lama.

Pendekatan ini memastikan bahawa jumlah masa yang dibelanjakan untuk memperuntukkan semula dilunaskan kepada O(n), di mana n ialah panjang kepingan yang terhasil.

Pertimbangan Pelaksanaan:

Spesifikasi bahasa Go membolehkan pelaksanaan lampiran yang berbeza. Sebagai contoh, pelaksanaannya mungkin murah hati (memperuntukkan lebih daripada jumlah minimum yang diperlukan) atau parsimonious (memperuntukkan jumlah minimum yang diperlukan). Pengkompil Go gc menggunakan algoritma masa malar terlunas tatasusunan dinamik yang besar.

Ringkasan:

Kerumitan penambahan dalam Go bergantung pada pelaksanaan. Walau bagaimanapun, pelaksanaan biasa seperti pengkompil Go gc dan gccgo menggunakan algoritma masa malar terlunas.

Atas ialah kandungan terperinci Apakah Kerumitan Masa `tambah` dalam Go?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!