递归时间复杂度演算T (n)=aT (n/b)+f (n)-东方仙盟-北京尧图网络

主定理公式T (n)aT (n/b)f (n)参数含义T (n)规模 n 的问题耗时a递归产生的子问题数量b每个子问题规模缩小为原来 1/bf (n)拆分、合并子问题的非递归开销重要前提主定理只适用于除以常数的分治递归 T (n)aT (n/b)f (n)如果是 T (n)aT (n-c)f (n)是减号不能用主定理要用迭代展开第一步计算基准 n^(log_b a)拿这个和 f (n) 对比分 3 种情况情况 1f (n) 远小于 n^(log_b a)条件存在 ε0f (n)O (n^(log_b a - ε))结论T (n)Θ(n^(log_b a))例子T (n)2T (n/2)√na2,b2log2 (2)1基准 n^1nf (n)√n n^0.5 n^1满足情况 1T(n)Θ(n)情况 2f (n) 等于基准附带对数项【自考最高频】条件f (n)Θ(n^(log_b a) * lg^k n) k≥0结论T (n)Θ(n^(log_b a) * lg^(k1) n)口诀f 里面对数是 k 次方结果对数 1 次方真题例子 1T (n)2T (n/2)na2,b2log2 (2)1基准 nf(n)n n^1 * lg^0 nk0T(n)Θ(n lg n)真题例子 2T (n)2T (n/2)n lg n 【你刷的选择题原题】a2,b2log2 (2)1基准 nf(n)n lg n n^1 * lg^1 nk1T(n)Θ(n lg² n)真题例子 3T (n)2T (n/2)n lg² nf(n)n^1 * lg² nk2T(n)Θ(n lg³ n)情况 3f (n) 远大于 n^(log_b a)满足正则条件条件存在 ε0f (n)Ω(n^(log_b a ε))且 af(n/b) ≤ cf(n)结论T (n)Θ(f (n))例子T (n)2T (n/2)n²log2 (2)1n² n^1满足情况 3T(n)Θ(n²)【自考大题标准答题模板直接抄写】题目T (n)2T (n/2)n lg nT (1)O (1)解1、确定参数 a2b2f (n)n lg n2、计算 log_b a log₂2 1基准函数 n^(log_b a)n^1 n3、对比 f (n)f (n)n lg n Θ(n¹ lg¹ n)属于主定理第二种情况k14、代入公式T (n)Θ(n^(log_b a) * lg^(k1) n)Θ(n lg² n)坑点背诵1、lg²n (lg n)²不是 lg (lg n)2、只有 T (n)aT (n/b) 能用主定理T (n)4T (n-1)n减号不能用主定理复杂度 Θ(4ⁿ)3、Θ 是渐近复杂度只看 n 很大时增长速度不是求精确数字自测两道题题 1T (n)3T (n/3)n解a3,b3,log3 (3)1f (n)nn¹lg⁰nk0T(n)Θ(n lg n)题 2T (n)4T (n/2)n²解a4,b2log2 (4)2f (n)n²n²lg⁰nk0T(n)Θ(n² lg n)递归树推导题目要求写原理才写T(n)2T(n/2)n lg n根节点规模 n开销 n lg n第二层2 个子节点每个规模 n/2总开销 n lg (n/2)第三层4 个子节点总开销 n lg (n/4)一共 lg n 层全部求和sumi0 到 lg n-1 n * lg (n / 2^i)求和结果Θ(n lg² n)人人皆为创造者共创方能共成长每个人都是使用者也是创造者是数字世界的消费者更是价值的生产者与分享者。在智能时代的浪潮里单打独斗的发展模式早已落幕唯有开放连接、创意共创、利益共享才能让个体价值汇聚成生态合力让技术与创意双向奔赴实现平台与伙伴的快速成长、共赢致远。原创永久分成共赴星辰大海原创创意共创、永久收益分成是东方仙盟始终坚守的核心理念。我们坚信每一份原创智慧都值得被尊重与回馈以永久分成锚定共创初心让创意者长期享有价值红利携手万千伙伴向着科技星辰大海笃定前行拥抱硅基生命与数字智能交融的未来共筑跨越时代的数字文明共同体。东方仙盟拥抱知识开源共筑数字新生态在全球化与数字化浪潮中东方仙盟始终秉持开放协作、知识共享的理念积极拥抱开源技术与开放标准。我们相信唯有打破技术壁垒、汇聚全球智慧才能真正推动行业的可持续发展。开源赋能中小商户通过将前端异常检测、跨系统数据互联等核心能力开源化东方仙盟为全球中小商户提供了低成本、高可靠的技术解决方案让更多商家能够平等享受数字转型的红利。共建行业标准我们积极参与国际技术社区与全球开发者、合作伙伴共同制定开放协议与技术规范推动跨境零售、文旅、餐饮等多业态的系统互联互通构建更加公平、高效的数字生态。知识普惠共促发展通过开源社区、技术文档与培训体系东方仙盟致力于将前沿技术转化为可落地的行业实践赋能全球合作伙伴共同培育创新人才推动数字经济的普惠式增长阿雪技术观在科技发展浪潮中我们不妨积极投身技术共享。不满足于做受益者更要主动担当贡献者。无论是分享代码、撰写技术博客还是参与开源项目维护改进每一个微小举动都可能蕴含推动技术进步的巨大能量。东方仙盟是汇聚力量的天地我们携手在此探索硅基生命为科技进步添砖加瓦。Hey folks, in this wild tech - driven world, why not dive headfirst into the whole tech - sharing scene? Dont just be the one reaping all the benefits; step up and be a contributor too. Whether youre tossing out your code snippets , hammering out some tech blogs, or getting your hands dirty with maintaining and sprucing up open - source projects, every little thing you do might just end up being a massive force that pushes tech forward. And guess what? The Eastern FairyAlliance is this awesome place where we all come together. Were gonna team up and explore the whole silicon - based life thing, and in the process, well be fueling the growth of technology

递归时间复杂度演算T (n)=aT (n/b)+f (n)-东方仙盟

相关推荐

2026年携程职级薪资：2—8级年包多少？附测试开发社招面试题

激光除锈钝化机器人：从物理原理到参数调试的完整指南

基于STM32与ESP8266的仓库环境监测系统设计与实现

更多资讯

Java SSM与Flask混合架构社区管理系统开发与部署全解析

Ubuntu 22.04上VCS与Verdi安装踩坑记录：从依赖修补到波形闭环

MATLAB实现多微网电能互补与需求响应的双层优化模型

考虑多微网电能互补与需求响应的双层优化模型及MATLAB实现

结构体字节对齐实战：从HardFault到总线Fault的排查与预防

I2C总线死锁实战：从模式状态机、时钟延展与九脉冲恢复全解析

今日更新

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？