Perbezaan antara algoritma rawak dan rekursif

Algoritma rekursif rawak

Algoritma rawak menggabungkan rasa rawak dalam logiknya dengan membuat pilihan rawak semasa pelaksanaan algoritma. Oleh kerana rawak ini, tingkah laku algoritma boleh berubah walaupun untuk input tetap. Untuk banyak masalah, algoritma rawak menyediakan penyelesaian yang paling mudah dan cekap. Algoritma rekursif berdasarkan idea bahawa penyelesaian kepada masalah dapat dijumpai dengan mencari penyelesaian kepada masalah sub yang lebih kecil dari masalah yang sama. Rekursi digunakan secara meluas untuk mencari penyelesaian kepada masalah dalam sains komputer dan banyak bahasa pengaturcaraan peringkat tinggi menyokong rekursi.

Apakah algoritma rawak?

Algoritma rawak menggabungkan rasa rawak dengan membuat pilihan rawak yang membimbing pelaksanaan algoritma. Ini biasanya dilakukan dengan mengambil satu set nombor rawak yang dihasilkan oleh penjana nombor pseudorandom sebagai input tambahan. Oleh kerana itu, tingkah laku algoritma mungkin berubah walaupun untuk input tetap. QuickSort adalah algoritma yang diketahui secara meluas yang menggunakan konsep rawak dan ia mempunyai masa berjalan O (n log n) tanpa mengira sifat input. Selanjutnya, kaedah pembinaan tambahan rawak digunakan untuk struktur bangunan seperti badan cembung dalam geometri perhitungan. Dalam kaedah ini, titik input secara rawak diarahkan dan kemudian dimasukkan satu demi satu ke struktur. Melaksanakan algoritma rawak agak mudah daripada melaksanakan algoritma deterministik untuk masalah yang sama. Cabaran terbesar dalam merancang algoritma rawak terletak pada melakukan analisis asimtotik untuk kerumitan masa dan ruang.

Apakah algoritma rekursif?

Algoritma rekursif berdasarkan idea bahawa penyelesaian kepada masalah dapat dijumpai dengan mencari penyelesaian kepada masalah sub yang lebih kecil dari masalah yang sama. Dalam algoritma rekursif, fungsi ditakrifkan dari segi versi terdahulu sendiri. Penting untuk diperhatikan bahawa rujukan diri ini harus mempunyai syarat penamatan untuk mengelakkan merujuk dirinya selama -lamanya. Keadaan penamatan diperiksa sebelum merujuk sendiri. Langkah awal algoritma rekursif berkaitan dengan klausa asas definisi rekursif masalah. Langkah -langkah yang mengikuti langkah awal berkaitan dengan klausa induktif masalah. Algoritma rekursif memberikan penyelesaian yang lebih mudah dalam banyak situasi dan lebih dekat dengan cara pemikiran semula jadi daripada algoritma berulang untuk masalah yang sama. Tetapi pada umumnya, algoritma rekursif memerlukan lebih banyak ingatan dan mereka mahal secara komputasi.

Apakah perbezaan antara algoritma rawak dan rekursif?

Algoritma rawak adalah algoritma yang menggunakan rasa rawak dengan membuat pilihan rawak yang boleh menjejaskan pelaksanaan algoritma, sementara algoritma rekursif adalah algoritma yang berdasarkan idea bahawa penyelesaian kepada masalah dapat ditemui dengan mencari penyelesaian kepada sub masalah yang lebih kecil masalah yang sama. Oleh kerana rawak dalam algoritma rawak, tingkah laku algoritma boleh berubah walaupun untuk input yang sama (dalam eksekusi algoritma yang berbeza). Tetapi ini tidak mungkin dalam algoritma rekursif dan tingkah laku algoritma rekursif akan sama untuk input tetap.