当前位置: 首页 > news >正文

时间复杂度

I.主定理适用范围:

\(T(1)=\mathcal{O}(1)\) \(\space \space \space \space \space n=1\)

\(T(n)=a*T(\frac{n}{b})+\mathcal{O}(n^d)\) \(\space \space \space \space \space \space n\geq1\)

II.主定理内容:

\(d<\log_b a\) 时,递归时间复杂度为:\(\mathcal{O}(n^{\log_b a})\)

\(d=\log_ba\) 时,递归时间复杂度为:\(\mathcal{O}(n^d * \log n)\)

\(d>\log_b a\) 时,递归时间复杂度为:\(\mathcal{O}(n^d)\)

III.Akra-Bazzi定理

$Definition: $设 \(g(x)\) 为一定义在非负实数上的函数, \(\{b_k\}\) 为一个含有 \(k\) 项的数列且满足 \(0 < b_i< 1\) ,若存在正常数 \(c_1, c_2\) 使得对任意 \(x \geq 1, 1 \leq i \leq k, u \in [b_i x , x]\) ,均有 \(c_1 g(x) \leq g(u) \leq c_2 g(x)\),则称 \(g(x)\) 满足多项式增长条件

由定义可知,若存在 \(c > 0\) ,使得 \(|g'(x)| \in \mathcal{O}(x^c)\) ,则 \(g(x)\) 满足多项式增长条件。例如,对任意 \(\alpha, \beta \in \mathbb{R} , g(x) = x^{\alpha} \lg^{\beta} x\) 均满足多项式增长条件。

\(Theorem:\)\(g(x)\)为一非负函数, $T(x) = $ \(\left\{ \begin{aligned}&\Theta(1)&,&1 \leq x \leq X_0 \\ &\sum_{i = 1}^k a_i T(b_i x) +g(x)&, &n>X_0 \end{aligned}\right.\)

(其中 \(k \geq 1, a_i > 0, 0 < b_i < 1 , X_0\) 满足对任意 \(1 \leq i \leq k\)\(X_0\) \(>\) \(\frac{1}{b_i}\) 且$ X_0> \frac{1}{1-b_i}$ )

\(g(x)\) 满足多项式增长条件, $p $为方程 \(\sum_{i = 1}^k a_i b_i^p = 1\) 的实数解,则

\(\begin{aligned} T(x) &= \Theta \left(x^p \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} du\right)\right) \end{aligned}\)

http://www.hskmm.com/?act=detail&tid=12585

相关文章:

  • 基于WOA鲸鱼优化的XGBoost序列预测算法matlab仿真
  • 软件工程第二次作业——个人项目
  • 微信扫码二维码,关注绑定公众号提醒,利用微信公众号的模板消息进行消息通知的推送
  • Arch下实现人脸识别登录:howdy的配置与使用
  • Salephpscripts Web_Directory_Free SQL注入漏洞利用分析(CVE-2024-3552)
  • 12306高并发架构设计:基于区间计数器的网关层拒单方案
  • 各位同学,大家好!我想请大家回忆一段我们在刘集中学的故事,和我单独联系。我想把这些故事写出来保存。欢迎与我分享!谢谢!
  • 实用指南:centos sshd:xxx.xxx.xxx.xxx:allow 如何设置
  • vite7-vue3-os网页os管理|vue3+vite7+arco.design网页pc版webos系统
  • 高并发高吞吐量
  • 服务降级
  • 镜像制作
  • 20231427田泽航第二周预习报告
  • 近期 CF 题不怎么做
  • Day24_【深度学习—广播机制】 - 详解
  • IAR Embedded Workbench中的MCU启动过程分析
  • CSP-S 2025
  • 别样的CSP-S初赛大战(又名:我和油一的那些年)
  • 在ubuntu系统的c语言程序
  • springboot2整合dynamic-datasource-spring-boot-starter多数据源
  • 赛前训练2 extra 思维与构造
  • 详细介绍:基于java的奶茶店管理系统的设计与实现37038-计算机毕设原创(免费领源码+部署教程)
  • 详细介绍:算法题(203):矩阵最小路径和
  • 使用jdbcTemplate查询数据库
  • 线性结构之链表预备知识typedef[基于郝斌课程]
  • Excel滚动表格表头不见了,来回翻动很麻烦,Excel如何固定显示表头?
  • asfp导入framework搭建环境
  • 赛前训练2 连通性问题
  • 用 【C# + WinUI3 + 图像动画】 来理解:高数 - 函数 - 初等函数 - 行人-
  • ansible语句