蓝桥杯学习记录（4）——基础算法

时间复杂度

时间复杂度一般关注的是最坏时间复杂度，用O(f(n))表示，

而时间复杂度中如果同时存在多项，仅考虑最高项

例如，如果基本操作执行次数是3n^2 + 2n + 1，那么时间复杂度就是O(n^2)

枚举

模拟

递归

进制转换

前缀和

差分

离散化

贪心

双指针

二分

二分法

定义：每次将搜索范围缩小一半，可以在O(logn)时间复杂度内找到正确答案。

使用二分法的前提条件：单调性

思路：通过利用单调性不断缩小二分查找的区间，来逼近目标值。

二分法步骤：

1. 候选区间[left,right]
2. 不断循环，直至区间满足特定条件
   • 计算中点mid = (left+right)/2
   • 判断中点是否合法，根据中点的计算结果调整[left,right] ，例如，如果mid比目标值大，则将区间调整为[left,mid]；而如果mid比目标值小，则调整区间为[mid,right]；如果mid与目标值相等，则输出mid

浮点二分

具体二分数学运算过程如下图：

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

left,right = 1,2
eps = 1e-4
#当区间长度大于eps，说明前3位小数不同
#否则，前三位小数已确定
while right - left >= eps:
    print("[{},{}]".format(left, right))
    #求中点
    mid = (left + right) / 2
    #分类讨论:当mid^2>2，则下一次为[left,mid]
    if mid * mid > 2:
        right = mid
    #此时mid^2<2，下一次为[mid,right]
    else:
    	left = mid

二分答案

题目所求答案(一般为整数) 具有单调性质，采用猜答案+二分

• 确定初始范围[left,right]
• 当left < right时:
  • mid = (left + right)//2
  • check(mid):断mid是否合法:(定义check函数，什么时候是合法，根据题目的单调性来确定)
  • 如果合法:更新ans=mid
  • 根据合法调整左右区间，调整策略为二选一: left =mid + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#二分答案
def check(x):
    #判断x是否合法，合法返回True，否则返回False
    pass

left, right, ans = 初始值

while left <= right:
    mid = (left + right) // 2
    if check(mid):
        ans = mid
        left = mid+1 #二选一
    else:
        right =mid - 1 #二选一
print(ans)

倍增

倍增算法是一种优化算法，通常应用于某些需要高效计算指数幂的场景。它基于分治的思想，通过反复求平方来实现快速计算指数幂的目的。在实际应用中，倍增算法经常用于解决最近公共祖先问题、二分查找等。

构造

位运算