AI智能摘要
智能提炼核心观点与价值
RHZ-Claude
围绕算法设计与分析习题5.4，归纳了十进制n位数相乘的位数范围为2n-1到2n位，演示用分治法计算2101×1130=2374130，并证明a^log_b c=c^log_b a，说明n^log₂3更适合作为复杂度闭式。还解释大整数乘法中乘以10^n按位移计入线性开销，建立递推时默认将n位数均分为两个n/2位数。
type
Post
status
Published
date
Feb 27, 2026
slug
algrithomxiti5-4
summary
围绕算法设计与分析习题5.4，归纳了十进制n位数相乘的位数范围为2n-1到2n位，演示用分治法计算2101×1130=2374130，并证明a^log_b c=c^log_b a，说明n^log₂3更适合作为复杂度闭式。还解释大整数乘法中乘以10^n按位移计入线性开销，建立递推时默认将n位数均分为两个n/2位数。
tags
算法笔记
category
笔记
icon
password
ai_summary
ai_summary
1.两个十进制n位数的积的位数范围
2.用分治算法计算 2101×1130
3.a.证明等式
3.b.为什么比 更适合作为M(n)的闭合公式？
4.a 为什么在大整数乘法算法的乘法次数 M(n)中，不把乘以 的乘法包括进去？
4.b 建立 M(n)递推关系时，另一个“微妙但不影响最终答案”的假设是什么？
5.在用笔算算法计算两个n位数乘法时，需要做多少次一位数的加法？可以忽略进位导致的加法
6.验证Strassen算法在计算 2×2矩阵乘法时所用到的公式
7.应用Strassen算法计算两个 4×4矩阵的乘积
8. 对于Strassen算法，其加法次数（包括减法）的递推关系式求解
正文到这里
Author
RHZ
License
CC BY-NC-ND 4.0
Notice
BY-NC-SA 协议
Continue Reading
继续阅读下一篇内容
