算法合集之淺析非完美算法在信息學(xué)競賽中的應(yīng)用-wenkub
2022-10-31 20:33:40 本頁面
【正文】 中，一個(gè)合數(shù)至多有 的機(jī)會(huì)為強(qiáng)偽質(zhì)數(shù)。 O() ? 抽樣測試法： ? 在 2~ 中抽取 k個(gè)試除。 ? 時(shí)間使用較少 ? 空間使用較少 ? 實(shí)現(xiàn)較容易 ? 容易被接受 ?非完美算法的一些常見方法 ? 隨機(jī)貪心 ? 抽樣測試 ? 部分忽略 ? …… —— 周詠基 《 論隨機(jī)化算法的 原理與設(shè)計(jì) 》 (*) (*) ?抽樣測試法 ? 抽樣：從統(tǒng)計(jì)總體中，任意抽出一部分單位作為樣本，并以其結(jié)果推算總體的相應(yīng)指標(biāo)。 ?抽樣測試法 s 滿足條件 A 具有性質(zhì) P ?抽樣測試法 10000個(gè)元素 100個(gè)滿足條件 只要少量抽樣就能取 得較高的正確率 ?抽樣測試法 ? 在抽樣測試時(shí)，有時(shí)總體中存在一些特殊的元素，這些元素滿足條件的概率往往與其他元素滿足條件的概率相差較大。 nn?Strong Pseudoprime ? 對(duì)于奇數(shù) n和正整數(shù) a，設(shè) n1=d ? 抽樣測試：隨機(jī)抽取 k個(gè)不同的 a進(jìn)行測試。 ? 只用 2,3測試：最小強(qiáng)偽質(zhì)數(shù)大于
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1