算法合集之淺析非完美算法在信息學競賽中的應用(編輯修改稿)
2025-11-12 20:33 本頁面
【文章內容簡介】 測試 ? 當 a不是 n的整數(shù)倍時，質數(shù) n必然是以 a為底的強偽質數(shù)。 ? 在所有可能的 a中，一個合數(shù)至多有 的機會為強偽質數(shù)。 ? 抽樣測試：隨機抽取 k個不同的 a進行測試。 ? 正確率大于 1－ 4－ k ? 時間復雜度為 O(klog2n)。 14—— 抽樣測試 ?質數(shù)測試 —— 抽樣測試 ? 特殊抽樣：讓 a取最小的若干個質數(shù)。 ? 只用 2測試：最小的強偽質數(shù)為 2047，在小于 1010中有 4842個強偽質數(shù)。 ? 只用 2,3測試：最小強偽質數(shù)大于 106。 ? 只用 2,3,5測試：最小強偽質數(shù)大于 107。 ? 只用 2,3,5,7測試：最小強偽質數(shù)大于 109。 ?質數(shù)測試 —— 抽樣測試 ? 一般情況下，只要用 2,3,5,7進行測試就能正確的判斷一個數(shù)是否為質數(shù)。 ? 時間復雜度： O(log2n) ?抽樣測試法 明顯降低時間復雜度！ 抽樣測試法 ?部分忽略法 ? 在信息學中，可能會遇到這樣情況：一個題的分類非常多，同時某些情況的處理非常復雜，但這些情況往往不是主要情況 (即出現(xiàn)的概率很小或
教學課件相關推薦
鄂ICP備17016276號-1