什么是偽隨機(jī)算法？隨機(jī)算法：隨機(jī)算法是一種包含隨機(jī)數(shù)生成器的算法。根據(jù)《算法概論（中文第二版）》的描述，在算法分析過(guò)程中，有時(shí)在獲得一定的輸入分布信息后，可能會(huì)對(duì)輸入分布做出一定的假設(shè)。在此基礎(chǔ)上，通

什么是偽隨機(jī)算法？

隨機(jī)算法：隨機(jī)算法是一種包含隨機(jī)數(shù)生成器的算法。根據(jù)《算法概論（中文第二版）》的描述，在算法分析過(guò)程中，有時(shí)在獲得一定的輸入分布信息后，可能會(huì)對(duì)輸入分布做出一定的假設(shè)。在此基礎(chǔ)上，通過(guò)分析平均情況得到算法的時(shí)間復(fù)雜度。然而，有時(shí)我們無(wú)法得到投入分布的信息。此時(shí)，我們可以在算法本身加入一些隨機(jī)性，從而實(shí)現(xiàn)對(duì)算法的平均分析。通過(guò)隨機(jī)算法的設(shè)計(jì)，可以有效避免更多的不良輸入，從而提高算法的平均性能。概率算法：許多算法的每個(gè)計(jì)算步驟都是固定的，而概率算法允許算法在執(zhí)行過(guò)程中隨機(jī)選擇下一個(gè)計(jì)算步驟。在許多情況下，當(dāng)算法在執(zhí)行過(guò)程中遇到選擇時(shí)，隨機(jī)選擇往往比最優(yōu)選擇節(jié)省時(shí)間。因此，概率算法可以在很大程度上降低算法的復(fù)雜度。概率算法的一個(gè)基本特點(diǎn)是，用同一個(gè)概率算法對(duì)同一個(gè)問(wèn)題進(jìn)行兩次求解，可以得到完全不同的結(jié)果。這兩種解決方案在時(shí)間上甚至結(jié)果上可能有相當(dāng)大的差別。一般來(lái)說(shuō)，概率算法大致可以分為四類(lèi)：數(shù)值概率算法、蒙特卡羅算法、拉斯維加斯算法和舍伍德算法。數(shù)值概率算法是求解數(shù)值問(wèn)題的常用算法。這種算法往往得到近似解。近似解的精度隨計(jì)算時(shí)間的增加而提高。在許多情況下，不可能或不需要計(jì)算問(wèn)題的精確解，因此用數(shù)值概率算法可以得到滿(mǎn)意的解。