python【数据结构与算法】倍增思想

    科技2024-11-07  12

    文章目录

    1 概述 2 例题

    1 概述

    倍增是一种思想,每次将考虑的范围扩大或减少一倍从而达到加速的效果,将某一步的O(n)优化到O(logn)

    也就是一种自底向上的二分 如快速幂 顾名思义就是一倍一倍的增加。举个例子你每次可以跳2的k次方步。现在你要跳到距离7步的地方。

    跳8步 跳过了(不跳)

    跳4步 没跳到(跳)

    跳2步 没跳到 (跳)

    跳1步 跳到 (停)

    这里就只跳了3次 比普通的7次跳发优化了4次;

    如果数据很大就是O(n) 和 O(logn)的区别了;

    2 例题

    题目描述 小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以跑2^k千米(k是任意自然数)。当然,这个机器是用longint存的,所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图,小A家为点1,公司为点n,每条边长度均为一千米。小A想每天能醒地尽量晚,所以让你帮他算算,他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

    输入格式 第一行两个整数n,m

    李响Superb 认证博客专家 机器学习 TensorFlow 图像处理 成为一名优秀的算法工程师⬆️ ,目前还在读软件工程,AI攻防、算法和深度学习方向,微博同名❤️ :李响Superb,(记得关注,有问题微博私信!)我们一起努力呀!
    Processed: 0.011, SQL: 8