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

吉林省住房和建设厅网站廊坊网站备案

吉林省住房和建设厅网站,廊坊网站备案,有没有和小孩做的网站,传媒公司网站源码php主定理#xff08;Master Theorem#xff09;是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系#xff0c;通常采用分治策略解决问题的情况。 目录 主定理简化版的局限主定理一般形式情况1#xff1a; n l o g b a n^{log_{b}{a}} nlogb​a … 主定理Master Theorem是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系通常采用分治策略解决问题的情况。 目录 主定理简化版的局限主定理一般形式情况1 n l o g b a n^{log_{b}{a}} nlogb​a 比 f ( n ) f(n) f(n) 增长的快情况2 n l o g b a n^{log_{b}{a}} nlogb​a 与 f ( n ) f(n) f(n) 增长率类似情况3 n l o g b a n^{log_{b}{a}} nlogb​a 比 f ( n ) f(n) f(n) 增长的慢 主定理不适用的情况 主定理简化版的局限 主定理简化版的三种情况 I F IF IF f ( n ) O ( n l o g b ( a − ε ) ) f(n) O(n^ {log_b(a - ε)}) f(n)O(nlogb​(a−ε))and ε 0 ε 0 ε0Then T ( n ) Θ ( n l o g b ( a ) ) T(n) Θ(n^{log_b(a)}) T(n)Θ(nlogb​(a)) I F IF IF f ( n ) Θ ( n l o g b ( a ) ⋅ l o g k n ) f(n) Θ(n^{log_b(a)} ·log^k n) f(n)Θ(nlogb​(a)⋅logkn)and k ≥ 0 k ≥ 0 k≥0Then T ( n ) Θ ( n l o g b ( a ) ⋅ l o g k 1 n ) T(n) Θ(n^{log_b(a)} · log^{k1} n) T(n)Θ(nlogb​(a)⋅logk1n) I F IF IF f ( n ) Ω ( n l o g b ( a ε ) ) f(n) Ω(n^{log_b(a ε)}) f(n)Ω(nlogb​(aε))and ε 0 ε 0 ε0 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) a⋅f(bn​)≤c⋅f(n) 对于某个常数 c 1 c 1 c1 和所有足够大的 n n n 成立Then T ( n ) Θ ( f ( n ) ) T(n) Θ(f(n)) T(n)Θ(f(n)) 简化形式具有一定的限制条件比如形式上必须是 T ( n ) a ⋅ T ( n b ) f ( n ) T(n)a·T(\frac{n}{b})f(n) T(n)a⋅T(bn​)f(n) 并且 f ( n ) n c f(n) n^{c} f(n)nc 三个反例 子问题数量不是常数 T ( n ) n ⋅ T ( n 2 ) n 2 T(n)n \cdot T(\frac{n}{2})n^{2} T(n)n⋅T(2n​)n2 子问题数量小于1 T ( n ) 1 2 T ( n 2 ) n 2 T(n)\frac{1}{2}T(\frac{n}{2})n^{2} T(n)21​T(2n​)n2 分解问题和合并解的时间不是 n c n^{c} nc T ( n ) 2 T ( n 2 ) n l o g n T(n)2T(\frac{n}{2})nlogn T(n)2T(2n​)nlogn 主定理一般形式 T ( n ) a ⋅ T ( n b ) f ( n ) , a 0 , b 1 T(n)a·T(\frac{n}{b})f(n),a0,b1 T(n)a⋅T(bn​)f(n),a0,b1 I F IF IF ∃ ε 0 \exists ε 0 ∃ε0 使得 f ( n ) O ( n l o g b ( a − ε ) ) f(n) O(n^ {log_b(a - ε)}) f(n)O(nlogb​(a−ε)) Then T ( n ) Θ ( n l o g b ( a ) ) T(n) Θ(n^{log_b(a)}) T(n)Θ(nlogb​(a)) I F IF IF ∃ k ≥ 0 \exists k ≥ 0 ∃k≥0 使得 f ( n ) Θ ( n l o g b ( a ) ⋅ l o g k n ) f(n) Θ(n^{log_b(a)} ·log^k n) f(n)Θ(nlogb​(a)⋅logkn)Then T ( n ) Θ ( n l o g b ( a ) ⋅ l o g k 1 n ) T(n) Θ(n^{log_b(a)} · log^{k1} n) T(n)Θ(nlogb​(a)⋅logk1n) I F IF IF ∃ ε 0 \exists ε 0 ∃ε0 使得 f ( n ) Ω ( n l o g b ( a ε ) ) f(n) Ω(n^{log_b(a ε)}) f(n)Ω(nlogb​(aε)) 且对于某个常数 c 1 c 1 c1 和所有足够大的 n n n 有 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) a⋅f(bn​)≤c⋅f(n) Then T ( n ) Θ ( f ( n ) ) T(n) Θ(f(n)) T(n)Θ(f(n)) 主要考虑 函数 n l o g b a n^{log_{b}{a}} nlogb​a 与 f ( n ) f(n) f(n) 的增长率关系 情况1 n l o g b a n^{log_{b}{a}} nlogb​a 比 f ( n ) f(n) f(n) 增长的快 T ( n ) 9 T ( n 3 ) n T(n)9T(\frac{n}{3})n T(n)9T(3n​)n n l o g b a n 2 n^{log_{b}{a}}n^{2} nlogb​an2, f ( n ) n O ( n 2 − ϵ ) , ϵ ≤ 1 f(n)nO(n^{2-\epsilon }),\epsilon \le1 f(n)nO(n2−ϵ),ϵ≤1 ⇒ T ( n ) O ( n 2 ) \Rightarrow T(n)O(n^{2}) ⇒T(n)O(n2) 情况2 n l o g b a n^{log_{b}{a}} nlogb​a 与 f ( n ) f(n) f(n) 增长率类似 T ( n ) T ( 2 n 3 ) 1 T(n)T(\frac{2n}{3})1 T(n)T(32n​)1 n l o g b a n l o g 3 / 2 1 n 0 1 n^{log_{b}{a}}n^{log_{3/2}1}n^{0}1 nlogb​anlog3/2​1n01, f ( n ) 1 Θ ( n l o g b a l o g 0 n ) f(n)1Θ(n^{log_{b}{a}}log^{0}n) f(n)1Θ(nlogb​alog0n) ⇒ T ( n ) O ( l o g n ) \Rightarrow T(n)O(log n) ⇒T(n)O(logn) 情况3 n l o g b a n^{log_{b}{a}} nlogb​a 比 f ( n ) f(n) f(n) 增长的慢 f ( n ) f(n) f(n)比 n l o g b a n^{log_{b}{a}} nlogb​a 增长的更快至少要快 Θ ( n ϵ ) Θ(n^{\epsilon}) Θ(nϵ) 倍且 a f ( n b ) ≤ c f ( n ) af(\frac{n}{b}) \le cf(n) af(bn​)≤cf(n) T ( n ) 3 T ( n 4 ) n l o g n T(n)3T(\frac{n}{4})nlogn T(n)3T(4n​)nlogn n l o g b a n l o g 4 3 n 0.793 n^{log_{b}{a}}n^{log_{4}3n^{0.793}} nlogb​anlog4​3n0.793, f ( n ) n l o g n Ω ( n l o g 4 3 ϵ ) , ϵ ≤ 0.207 f(n)nlognΩ(n^{log_{4}3\epsilon }),\epsilon \le0.207 f(n)nlognΩ(nlog4​3ϵ),ϵ≤0.207 a f ( n b ) 3 ( n 4 ) l o g ( n 4 ) ≤ 3 4 n l o g n c f ( n ) , c 3 4 af(\frac{n}{b})3(\frac{n}{4})log(\frac{n}{4}) \le \frac{3}{4}nlogncf(n),c\frac{3}{4} af(bn​)3(4n​)log(4n​)≤43​nlogncf(n),c43​ ⇒ T ( n ) O ( n l o g n ) \Rightarrow T(n)O(nlogn) ⇒T(n)O(nlogn) 主定理不适用的情况 n l o g b a n^{log_{b}{a}} nlogb​a 与 f ( n ) f(n) f(n) 的增长率不可比 n l o g b a n^{log_{b}{a}} nlogb​a 比 f ( n ) f(n) f(n) 增长的快但没有快 O ( n ϵ ) O(n^{\epsilon}) O(nϵ) 倍 n l o g b a n^{log_{b}{a}} nlogb​a 比 f ( n ) f(n) f(n) 增长的慢但没有慢 O ( n ϵ ) O(n^{\epsilon}) O(nϵ) 倍
http://www.huolong8.cn/news/90675/

相关文章:

  • 网站mssql 导出数据沃尔玛商城
  • 建个小型网站服务器wordpress 可视化编辑
  • 那些网站可以做公司的推广山东住房和城乡建设厅网站首页
  • 大庆做网站找谁网络营销产品价格策略
  • 专做蓝领招聘网站有哪些免费空间服务的网站
  • 专业自助建站图书馆网站建设的意义
  • 手机网站菜单设计模板html网站建设实例代码
  • 网站所有页面扬州互联网公司
  • 什么网站能看男女做暧公司注册代理中介
  • 网站建设经营服务合同范本用wordpress做广告收益
  • 豫建设标 网站重庆搜索排名提升
  • 莱西做网站国内重大新闻事件
  • 进度跟踪网站开发wordpress hq
  • 外贸电子网站上海贸易网站建设
  • 苏州产品网站建设怎么做网站镜像
  • 好用的ppt模板免费下载网站莱州网监局
  • 深圳建站公司外围网站字体加载不出来怎么办
  • 导航 网站 分析深圳南山做网站的公司
  • 台州市建设工程质量检测中心网站网站模板 使用
  • 安阳住房与城乡建设局官方网站西宁做网站最好的公司哪家好
  • 威海企业网站建设vs 2012网站开发
  • 网站关闭与域名备案网站开发公司合作协议书
  • 网站关键词优化的步骤和过程网站建设哪家好万维科技
  • 进度环wordpress无锡seo关键词排名
  • 阳江网站seo公司做网站设计网站建设推广
  • 备案的网站名称可以改吗电子商务公司网站模版
  • 做网站具体步骤成都sem优化
  • 广州市网站建设分站价格安陆网站建设
  • 线上职业技能培训平台吉林seo基础知识
  • 网站经营许可备案号网站建站收费