倍增算法及其应用_未知作者.pptx

倍增算法及其应用倍增算法及其应用 前言倍增算法及其应用倍增与其说是一种算法不如说是一种思想倍增这一思想在OI中也占有不小的地位它既直接被设计为解决某些问题的特定算法又可以与其它的算法结合优化时间复杂度进而解决问题今天要讲的主要是在NOIP中常用的有关倍增的算法简单概念 什么是倍增倍增算法及其应用倍增的字面意思就是成倍地增加假设某一问题有一个指标变量k我们可以从k=1的解推出k=2的解再进而推出k