数据结构与算法自学笔记（19）- 根据数据量猜解法的核心技巧

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class043的内容，介绍了算法竞赛和面试中极其重要的一个技巧——根据数据量猜解法。这是”天字第一号重要技巧”，能够帮助我们在看到题目后迅速判断应该使用什么复杂度的算法。

前置知识

在学习本技巧之前，需要掌握以下基础知识：

• 时间复杂度的概念（讲解007）
• 全排列递归代码的执行细节（讲解038）

---

核心原理

基本事实

无论在什么测试平台、什么CPU上，都有一个基本的性能标准：

• C/C++：运行时间1秒，对应常数指令操作量约为 10^7 ~ 10^8
• Java/Python/Go等其他语言：运行时间1-2秒，对应常数指令操作量约为 10^7 ~ 10^8

这个数量级是固定的，是我们进行算法复杂度估算的重要依据。

运用条件

要成功运用这个技巧，需要满足两个条件：

1. 题目给定各个参数的范围最大值

   • 正式笔试、比赛的题目一定会给出
   • 面试中需要和面试官确认

2. 对自己设计的算法有准确的时间复杂度估计

   • 这需要扎实的算法基础
   • 对各种算法模式的复杂度要熟悉

---

问题规模与可用算法对照表

数据规模n	logn	n	n*logn	n*√n	n²	2^n	n!
n ≤ 11	✓	✓	✓	✓	✓	✓	✓
n ≤ 25	✓	✓	✓	✓	✓	✓	✗
n ≤ 5000	✓	✓	✓	✓	✓	✗	✗
n ≤ 10^5	✓	✓	✓	✓	✗	✗	✗
n ≤ 10^6	✓	✓	✓	✗	✗	✗	✗
n ≤ 10^7	✓	✓	✗	✗	✗	✗	✗
n ≥ 10^8	✓	✗	✗	✗	✗	✗	✗

说明

• n√n 复杂度*：常出现在”莫队算法”相关题目中
• 这张表提供参考，但实际应用中要考虑多个参数的组合影响
• 关键是记住常数指令操作量 10^7 ~ 10^8这个基准

---

043【必备】根据数据量猜解法的技巧-天字第一号重要技巧

实战案例

案例一：最优的技能释放顺序

问题描述

现在有一个打怪类型的游戏：

• 你有n个技能，每个技能最多只能释放一次
• 每个技能有基础伤害值
• 当怪物血量小于等于某个阈值时，该技能可能造成双倍伤害
• 已知怪物有m点血量
• 求最少用几个技能能消灭怪物

约束条件：

• 1 ≤ n ≤ 10
• 1 ≤ m、x[i]、y[i] ≤ 10^6

测试链接： https://www.nowcoder.com/practice/d88ef50f8dab4850be8cd4b95514bbbd

复杂度分析

由于 n ≤ 10，我们可以尝试所有技能的排列组合：

• 排列数：n! ≤ 10! = 3,628,800
• 远小于 10^7，所以回溯算法完全可行

算法实现

import sys
import math

class Solution:
    def __init__(self):
        self.kill = []      # 技能伤害值
        self.blood = []     # 触发双倍伤害的血量阈值
        self.n = 0

    def _f(self, i: int, r: int) -> int:
        """
        回溯算法核心函数
        i: 当前使用的技能数量
        r: 怪物剩余血量
        返回: 从当前状态到击败怪物还需要的最少技能数
        """
        # base case: 怪物已被击败
        if r <= 0:
            return 0
        
        # base case: 技能用完但怪物未死
        if i == self.n:
            return math.inf

        ans = math.inf
        # 尝试所有未使用的技能
        for j in range(i, self.n):
            # 将第j个技能换到位置i尝试
            self._swap(i, j)
            
            # 计算伤害（是否触发双倍）
            damage = self.kill[i] if r > self.blood[i] else self.kill[i] * 2
            
            # 递归求解
            res = self._f(i + 1, r - damage)
            if res != math.inf:
                ans = min(ans, 1 + res)
            
            # 回溯
            self._swap(i, j)
            
        return ans

    def _swap(self, i: int, j: int):
        """交换第i个和第j个技能"""
        self.kill[i], self.kill[j] = self.kill[j], self.kill[i]
        self.blood[i], self.blood[j] = self.blood[j], self.blood[i]

优化版本（剪枝）

def solve_optimized():
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        skills = []
        for _ in range(n):
            skills.append(tuple(map(int, input().split())))
        
        ans = -1
        
        def dfs(blood, used=set()):
            nonlocal ans
            
            # 剪枝1: 假设剩余技能全部打出双倍伤害
            rest_max_damage = sum([2 * skills[i][0] for i in range(n) if i not in used])
            if blood > rest_max_damage:
                return
            
            # 剪枝2: 如果当前已使用技能数不优于已知答案
            if ans != -1 and len(used) >= ans:
                return
            
            # 成功条件
            if blood <= 0:
                ans = min(ans, len(used)) if ans >= 0 else len(used)
                return
            
            # 失败条件
            if len(used) == n and blood > 0:
                return
            
            # 尝试每个未使用的技能
            for i, (damage, threshold) in enumerate(skills):
                if i not in used:
                    used.add(i)
                    actual_damage = 2 * damage if blood <= threshold else damage
                    dfs(blood - actual_damage, used)
                    used.remove(i)
        
        dfs(m)
        print(ans)

案例二：超级回文数的数目

问题描述

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。

给定两个正整数L和R，返回包含在范围[L, R]中的超级回文数的数目。

约束条件：

• 1 ≤ len(L) ≤ 18
• 1 ≤ len(R) ≤ 18
• L和R表示[1, 10^18)范围的整数

测试链接： https://leetcode.cn/problems/super-palindromes/

复杂度分析

设超级回文数为S = x²，其中S和x都是回文数：

• S最大为10^18，所以x最大为10^9
• 回文数的数量远少于普通数
• 可以通过”种子”生成回文数，种子范围约为10^5
• 时间复杂度约为O(√10^9) = O(10^5)，完全可行

算法实现

方法一：枚举回文数的根

import math

class Solution:
    def superpalindromesInRange1(self, left: str, right: str) -> int:
        """
        核心思想：枚举所有可能的回文数x，检查x²是否也是回文且在范围内
        """
        l, r = int(left), int(right)
        limit = int(math.sqrt(r))
        
        ans = 0
        seed = 1
        
        while True:
            # 生成偶数长度回文数
            num_even = self._even_enlarge(seed)
            if num_even > limit:
                break
            square = num_even * num_even
            if self._check(square, l, r):
                ans += 1
            
            # 生成奇数长度回文数
            num_odd = self._odd_enlarge(seed)
            if num_odd <= limit:
                square = num_odd * num_odd
                if self._check(square, l, r):
                    ans += 1

            seed += 1
            
        return ans

    def _even_enlarge(self, seed: int) -> int:
        """将种子扩展为偶数长度回文数，如123→123321"""
        ans = seed
        temp = seed
        while temp != 0:
            ans = ans * 10 + temp % 10
            temp //= 10
        return ans

    def _odd_enlarge(self, seed: int) -> int:
        """将种子扩展为奇数长度回文数，如123→12321"""
        ans = seed
        temp = seed // 10
        while temp != 0:
            ans = ans * 10 + temp % 10
            temp //= 10
        return ans

    def _check(self, num: int, l: int, r: int) -> bool:
        """检查数字是否在范围内且为回文数"""
        return l <= num <= r and self._is_palindrome_num(num)

    def _is_palindrome_num(self, num: int) -> bool:
        """判断数字是否为回文数"""
        if num < 0:
            return False
        if num == 0:
            return True
        
        # 双指针思想：同时从最高位和最低位比较
        offset = 1
        while num // offset >= 10:
            offset *= 10
        
        while num != 0:
            if num // offset != num % 10:
                return False
            num = (num % offset) // 10
            offset //= 100
        return True

方法二：打表法

class Solution:
    # 预计算所有超级回文数
    _record = [
        1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944,
        1002001, 1234321, 4008004, 100020001, 102030201, 104060401,
        # ... 更多预计算的值
        1234323468643234321, 4000000008000000004
    ]

    def superpalindromesInRange2(self, left: str, right: str) -> int:
        """
        打表法：预先计算好所有超级回文数，查询时直接范围查找
        """
        l, r = int(left), int(right)
        
        # 二分查找或线性扫描
        count = 0
        for num in self._record:
            if l <= num <= r:
                count += 1
            elif num > r:
                break
        
        return count

案例三：回文数判断

问题描述

判断一个整数是否是回文数，不使用字符串转换。

测试链接： https://leetcode.cn/problems/palindrome-number/

核心思想

1. 负数不是回文数。
2. 计算出一个 offset，使其与 num 的位数相同（例如，num=12321, offset=10000）。
   这个 offset 可以用来取出最高位的数字 (num // offset)。
3. 循环比较最高位 (num // offset) 和最低位 (num % 10)。
4. 如果不相等，则不是回文数。
5. 如果相等，则去掉最高位和最低位，继续比较。
   • 去掉最低位: num % 10
   • 去掉最高位: num % offset
   • 组合起来: (num % offset) // 10
6. 同时，offset 需要除以 100，因为我们一次处理了两位数。

算法实现

class Solution:
    def isPalindrome(self, num: int) -> bool:
        """
        不使用字符串转换判断回文数
        核心思想：双指针，同时比较最高位和最低位
        """
        if num < 0:
            return False
        
        # 计算与num位数相同的offset
        offset = 1
        while num // offset >= 10:
            offset *= 10
            
        # 同时比较首尾数字
        while num != 0:
            # 比较最高位和最低位
            if num // offset != num % 10:
                return False
            
            # 去掉首尾两位数字
            num = (num % offset) // 10
            offset //= 100
            
        return True

---

技巧应用步骤

1. 分析数据规模

# 示例：看到题目约束
# n ≤ 10, m ≤ 10^6
# 立即想到：n很小，可以用指数级算法；m较大，需要高效处理

2. 估算操作次数

# 示例：全排列问题
# n ≤ 10 → n! ≤ 10! ≈ 3.6 × 10^6 < 10^7 ✓ 可行
# n ≤ 15 → n! ≤ 15! ≈ 1.3 × 10^12 > 10^8 ✗ 不可行

3. 选择合适算法

# 根据复杂度选择算法类型：
# O(1), O(logn) → 数学公式、二分查找
# O(n) → 线性扫描、简单遍历  
# O(n logn) → 排序、分治算法
# O(n²) → 双重循环、动态规划
# O(2^n) → 回溯、状态压缩DP
# O(n!) → 全排列、旅行商问题

4. 考虑常数优化

# 即使复杂度合适，也要考虑：
# - 剪枝优化
# - 缓存计算结果
# - 避免重复计算
# - 选择高效的数据结构

---

常见复杂度模式

1. 递归分治

# T(n) = a × T(n/b) + O(n^c)
# 主定理：比较a与b^c的大小关系

2. 动态规划

# 状态数 × 转移复杂度
# 一维DP: O(n)
# 二维DP: O(n²)  
# 区间DP: O(n³)

3. 图算法

# BFS/DFS: O(V + E)
# 最短路径: O(V²) 或 O(E logV)
# 最小生成树: O(E logE)

4. 字符串算法

# 暴力匹配: O(n×m)
# KMP: O(n + m)
# 字典树: O(总长度)

---

学习建议

1. 熟记基准值

• 核心记忆：10^7 ~ 10^8 操作/秒
• 常见数据规模的复杂度上限
• 不同语言的性能差异

2. 积累经验

• 多做题，培养对复杂度的直觉
• 记录不同类型题目的常见数据规模
• 总结复杂度估算的常见陷阱

3. 实践验证

• 实际提交验证时间复杂度估算
• 对比不同算法的实际运行时间
• 学会分析超时的原因

4. 深入理解

• 不仅要会算复杂度，还要理解为什么
• 掌握各种算法的适用场景
• 学会在时间和空间之间做权衡

---

总结

“根据数据量猜解法”是算法竞赛和技术面试中极其重要的技巧：

1. 核心原理：基于10^7~10^8操作/秒的基准进行复杂度估算
2. 应用场景：快速判断算法可行性，指导解题方向
3. 关键要素：准确的复杂度分析 + 对数据规模的敏感度
4. 实战价值：避免选择错误的算法方向，提高解题效率

通过掌握这个技巧，我们可以在看到题目的第一时间就大致确定解题的复杂度范围，从而选择合适的算法策略，这对于在有限时间内解决算法问题具有重要意义。