Menemukan semua siklus

Saya memiliki satu set terbatas , fungsi f : S → S , dan total order < pada S . Saya ingin mencari jumlah siklus yang berbeda di S .$S$$f:S\to S$$<$$S$$S$

Untuk elemen tertentu saya dapat menggunakan algoritma Floyd (atau Brent, dll.) Untuk menemukan panjang siklus yang diulangi aplikasi f mengirimkan s ke; dengan sedikit usaha saya dapat mengidentifikasi siklus ini (misalnya dengan < -minimal elemen). Metode buruk untuk menyelesaikan masalah adalah mengulangi setiap elemen ini, mengurutkan elemen minimal yang dihasilkan dari duplikat, dan mengembalikan hitungan. Tapi ini berpotensi melibatkan banyak melewati elemen yang sama dan persyaratan ruang yang besar.$s\in S$$f$$s$$<$

Metode apa yang memiliki waktu dan ruang kinerja yang lebih baik? Saya bahkan tidak yakin apa cara terbaik untuk mengukur ruang yang dibutuhkan — jika adalah fungsi identitas maka metode apa pun yang menyimpan semua siklus akan menggunakan Ω ( n ) ruang.$f$$\Omega(n)$

Jika semua yang ingin Anda lakukan adalah menghitung jumlah siklus, Anda dapat melakukan ini dengan 2 | S | ruang bernilai bit (plus perubahan). Tampaknya tidak mungkin bahwa Anda akan dapat melakukan jauh lebih baik kecuali S atau f memiliki beberapa sifat yang sangat nyaman.

Mulai dengan array A integer penyimpanan {0,1,2} - satu per elemen S - diinisialisasi ke nol; kami akan menunjukkan ini sebagai (unexplored), (partially explored), dan (fully explored). Inisialisasi penghitung siklus ke nol. Untuk setiap elemen s  ∈  S secara berurutan, lakukan hal berikut:

1. Jika A [ s ] =  (fully explored), lewati ke langkah 6.
2. Set A [ s ] ←  (partially explored), dan atur iterator j  ←  f (s) .
3. Sementara A [ j ] =  (unexplored), atur A [ j ] ←  (partially explored), dan atur j  ←  f (j) .
4. Jika A [ j ] =  (partially explored), kami telah menutup siklus baru; kenaikan c oleh 1. (Jika Anda ingin menyimpan catatan beberapa perwakilan dari siklus ini, nilai saat ini dari j akan dilakukan sebagai pilihan sewenang-wenang; tentu saja, ini tidak akan selalu menjadi elemen minimal dalam siklus di bawah yang Anda inginkan order <.) Jika tidak, kita memiliki A [ j ] =  (fully explored), yang berarti bahwa kita telah menemukan orbit yang telah dieksplorasi yang berakhir pada siklus yang sudah dihitung; jangan naik c .
5. Untuk menunjukkan bahwa orbit mulai dari s sekarang telah sepenuhnya dieksplorasi, atur j  ←  s .
   Sementara A [ j ] =  (partially explored), atur A [ j ] ←  (fully explored)dan atur j  ←  f (j) .
6. Lanjutkan ke elemen berikutnya s  ∈  S .

Dengan demikian, setiap siklus di antara orbit yang disebabkan oleh f akan dihitung satu kali; dan elemen apa pun yang Anda rekam sebagai perwakilan akan menjadi elemen siklus berbeda. Persyaratan memori adalah 2 | S | untuk larik A, O (log | S |) untuk jumlah siklus, dan peluang dan tujuan lainnya.

Setiap elemen s  ∈  S akan dikunjungi setidaknya dua kali: sekali ketika nilai A [ s ] diubah dari (unexplored)menjadi (partially explored), dan satu kali untuk perubahan ke (fully explored). Jumlah total kali setiap node ditinjau kembali setelah (fully explored)dibatasi oleh jumlah upaya untuk menemukan siklus baru yang gagal melakukannya, yang paling banyak | S | - timbul dari loop iterasi utama melalui semua elemen S . Dengan demikian, kita dapat mengharapkan proses ini melibatkan paling banyak 3 | S | node-traversals, menghitung semua waktu node dikunjungi atau ditinjau kembali.

Jika Anda ingin melacak elemen yang representatif dari siklus, dan Anda benar-benar ingin mereka menjadi elemen minimal, Anda dapat mengikat jumlah kunjungan node ke 4 | S |, jika Anda menambahkan "putaran di sekitar siklus" tambahan pada langkah 4 untuk menemukan perwakilan yang lebih kecil dari yang Anda tutup. (Jika orbit di bawah f hanya terdiri dari siklus, pekerjaan tambahan ini dapat dihindari, tetapi itu tidak berlaku untuk arbitrer f .)

Jika Anda memiliki sangat sedikit siklus, inilah algoritma yang akan menggunakan lebih sedikit ruang, tetapi membutuhkan waktu lebih lama untuk berhenti.

[Sunting.] Analisis run-time saya sebelumnya melewatkan biaya penting untuk menentukan apakah node yang kami kunjungi adalah di antara yang sebelumnya diambil sampel; jawaban ini agak direvisi untuk memperbaikinya.

Kita lagi iterate melalui semua elemen S . Saat kami menjelajahi orbit elemen s  ∈  S , kami mengambil sampel dari node yang telah kami kunjungi, agar dapat memeriksa apakah kami menemukan mereka lagi. Kami juga memelihara daftar sampel dari 'komponen' - serikat orbit yang berakhir dalam siklus umum (dan karenanya sama dengan siklus) - yang sebelumnya telah dikunjungi.

Inisialisasi daftar komponen yang kosong complist,. Setiap komponen diwakili oleh kumpulan sampel dari komponen itu; kami juga memelihara pohon pencarian samplesyang menyimpan semua elemen yang telah dipilih sebagai sampel untuk beberapa komponen atau lainnya. Biarkan G menjadi urutan bilangan bulat hingga n , yang keanggotaannya ditentukan secara efisien dengan menghitung beberapa predikat boolean; misalnya, kekuatan dari 2 atau sempurna p ^th kekuatan untuk suatu bilangan bulat p . Untuk setiap s  ∈  S , lakukan hal berikut:

1. Jika s ada di samples, lewati ke langkah # 5.
2. Inisialisasi daftar kosong cursample, sebuah iterator j  ← f ( s ), dan penghitung t  ← 1.
3. Saat j tidak ada di samples:
   - Jika t  ∈  G , masukkan j ke dalam keduanya cursampledan samples.
   - Kenaikan t dan atur j  ←  f (j) .
4. Periksa untuk melihat apakah j ada di cursample. Jika tidak, kami telah menemukan komponen yang telah dieksplorasi sebelumnya: kami memeriksa komponen mana yang termasuk j , dan memasukkan semua elemen cursampleke dalam elemen yang sesuai complistuntuk menambahnya. Jika tidak, kami telah menemukan kembali elemen dari orbit saat ini, yang berarti bahwa kami telah melintasi siklus setidaknya sekali tanpa menemui perwakilan dari siklus yang sebelumnya ditemukan: kami memasukkan cursample, sebagai kumpulan sampel dari komponen yang baru ditemukan, ke complist.
5. Lanjutkan ke elemen berikutnya s  ∈  S .

Untuk n  = | S |, misalkan X (n) adalah fungsi peningkatan monoton yang menggambarkan jumlah siklus yang diharapkan ( mis.  X (n) =  n ^1/3 ), dan misalkan Y (n) = y (n)  log ( n ) ∈ Ω ( X (n)  log ( n )) adalah fungsi yang meningkatkan monoton menentukan target untuk penggunaan memori ( misalnya  y (n) =  n ^1/2 ). Kami memerlukan y (n)  ∈ Ω ( X (n) ) karena akan membutuhkan setidaknya X (n)  log ( n ) ruang untuk menyimpan satu sampel dari setiap komponen.

• Semakin banyak elemen dari orbit yang kita sampel, semakin besar kemungkinan kita untuk dengan cepat memilih sampel dalam siklus di akhir orbit, dan dengan demikian dengan cepat mendeteksi siklus itu. Dari sudut pandang asimptotik, masuk akal untuk mendapatkan sampel sebanyak yang diizinkan oleh ingatan kita: kita mungkin juga menetapkan G untuk memiliki elemen y (n) yang diharapkan yang kurang dari n .
  - Jika panjang maksimum orbit di S diharapkan L , kami dapat membiarkan G menjadi kelipatan bilangan bulat L  /  y (n) .
  - Jika tidak ada panjang yang diharapkan, kami cukup sampel satu kali setiap n  /  y (n)elemen; ini dalam hal apapun merupakan batas atas pada interval antar sampel.

• Jika, dalam mencari komponen baru, kita mulai melintasi elemen S yang sebelumnya telah kita kunjungi (baik dari komponen baru yang ditemukan atau yang lama yang siklus terminalnya telah ditemukan), itu akan memakan waktu paling banyak n  /  y ( n) iterasi untuk menemukan elemen yang sebelumnya diambil sampelnya; ini kemudian merupakan batas atas pada berapa kali, untuk setiap upaya untuk menemukan komponen baru, kami melintasi node yang berlebihan. Karena kita membuat n upaya tersebut, kita kemudian akan berlebihan mengunjungi unsur S paling n ²  /  y (n) kali secara total.

• Pekerjaan yang diperlukan untuk menguji keanggotaan samplesadalah O ( y (n)  log  y (n) ), yang kami ulangi pada setiap kunjungan: biaya kumulatif pemeriksaan ini adalah O ( n ²  log  y (n) ). Ada juga biaya untuk menambahkan sampel ke koleksi masing-masing, yang secara kumulatif adalah O ( y (n)  log  y (n) ). Akhirnya, setiap kali kita menemukan kembali komponen yang ditemukan sebelumnya, kita harus mengeluarkan hingga X (n)  log *  y (n) waktu untuk menentukan komponen mana yang kita temukan kembali; karena hal ini dapat terjadi hingga n kali, pekerjaan kumulatif yang terlibat dibatasi oleh n X (n)  log  y (n) .

Dengan demikian, pekerjaan kumulatif yang dilakukan dalam memeriksa apakah node yang kami kunjungi adalah di antara sampel yang mendominasi run-time: ini biaya O ( n ²  log  y (n) ). Maka kita harus membuat y (n) sekecil mungkin, yaitu O ( X (n) ).

Jadi, seseorang dapat menghitung jumlah siklus (yang sama dengan jumlah komponen yang berakhir pada siklus tersebut) dalam ruang O ( X (n)  log ( n )), mengambil O ( n ²  log  X (n) ) waktu untuk melakukannya, di mana X (n) adalah jumlah siklus yang diharapkan.

$s$$s$$f(s)$