Bagaimanakah Kocok Fisher-Yates Mencapai Kocok Rawak Masa Linear?

Algoritma shuffling Fisher-Yates: algoritma shuffling masa linear

Kecekapan adalah penting apabila mengisih senarai integer secara rawak. Walaupun kaedah asal dalam soalan cuba mencapai rawak, ia mungkin menghadapi masalah kecekapan semasa pemprosesan, terutamanya menjelang akhir.

Penyelesaian yang lebih cekap ialah algoritma shuffling Fisher-Yates, algoritma masa linear yang memastikan penyusunan semula senarai input yang benar-benar rawak. Tidak seperti pendekatan asal, yang bergantung pada tatasusunan Boolean untuk menjejaki elemen yang ditukar, algoritma shuffling Fisher-Yates mengambil pendekatan yang lebih mudah.

for (int i = iItemCount - 1; i >= 1; i--)
{
    int j = random.Next(i + 1);
    int temp = values[j];
    values[j] = values[i];
    values[i] = temp;
}

Algoritma berfungsi dengan menukar elemen semasa berulang kali dengan elemen yang dipilih secara rawak sebelum ini dalam senarai. Semasa algoritma diteruskan, ia mengecilkan julat elemen yang tidak diisih, dengan berkesan mengocok keseluruhan senarai dalam masa O(n).

Menggunakan algoritma shuffling Fisher-Yates, anda boleh menyusun semula senarai integer dengan cekap dan rawak, mengelakkan kemungkinan perangkap algoritma asal.

Atas ialah kandungan terperinci Bagaimanakah Kocok Fisher-Yates Mencapai Kocok Rawak Masa Linear?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!