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

外贸免费建设网站制作市场监督管理局是干什么的

外贸免费建设网站制作,市场监督管理局是干什么的,顺德大良那里做网站好,盘古网络营销中心主定理(Master Theorem)是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系,通常采用分治策略解决问题的情况。 假设我们有一个递归算法,它将问题分解成 a a a 个子问题,每个子问题的规模…

主定理(Master Theorem)是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系,通常采用分治策略解决问题的情况。

假设我们有一个递归算法,它将问题分解成 a a a 个子问题,每个子问题的规模是原问题的 1 b \frac{1}{b} b1,解决每个子问题的代价是 f ( n ) f(n) f(n),而将子问题的解合并成原问题的解的代价是 g ( n ) g(n) g(n)。那么该递归算法的时间复杂度可以表示为:
T ( n ) = a ⋅ T ( n b ) + f ( n ) T(n)=a·T(\frac{n}{b})+f(n) T(n)=aT(bn)+f(n)
其中, a ≥ 1 , b > 1 a ≥ 1,b > 1 a1b>1 是常数, f ( n ) f(n) f(n) 是解决一个规模为 n n n 的问题所需的工作量, g ( n ) g(n) g(n) 是合并子问题的解的工作量。

主定理的三种情况:

  1. 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 ε>0,Then T ( n ) = Θ ( n l o g b ( a ) ) T(n) = Θ(n^{log_b(a)}) T(n)=Θ(nlogb(a))
  2. 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 k0,Then T ( n ) = Θ ( n l o g b ( a ) ⋅ l o g k + 1 n ) T(n) = Θ(n^{log_b(a)} · log^{k+1} n) T(n)=Θ(nlogb(a)logk+1n)
  3. 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) af(bn)cf(n) 对于某个常数 c < 1 c < 1 c<1 和所有足够大的 n n n 成立,Then T ( n ) = Θ ( f ( n ) ) T(n) = Θ(f(n)) T(n)=Θ(f(n))

情况一:

T ( n ) = 4 T ( n 2 ) + n T(n)=4T(\frac{n}{2})+n T(n)=4T(2n)+n

其中 a = 4 ≥ 1 , b = 2 > 1 , f ( n ) = n , l o g 2 4 = 2 > 1 a = 4\ge1,b = 2>1,f(n) = n,log_{2}4=2>1 a=41b=2>1f(n)=nlog24=2>1

根据主定理的第一种情况: f ( n ) = O ( n l o g b ( a − ε ) ) f(n) = O(n^ {log_b(a - ε)}) f(n)=O(nlogb(aε))

可得 n = O ( n l o g 2 ​ 4 − ε ) = O ( n 2 ) n=O(n^{log_{2}​4−ε})=O(n^{2}) n=O(nlog2​4ε)=O(n2)

∴ T ( n ) = Θ ( n 2 ) \therefore T(n)=Θ(n^{2}) T(n)=Θ(n2)


情况二:

T ( n ) = 4 T ( n 2 ) + n 2 T(n)=4T(\frac{n}{2})+n^{2} T(n)=4T(2n)+n2

其中 a = 4 ≥ 1 , b = 2 > 1 , f ( n ) = n 2 , l o g 2 4 = 2 a = 4\ge1,b = 2>1,f(n) = n^{2},log_{2}4=2 a=41b=2>1f(n)=n2log24=2

根据主定理的第二种情况: f ( n ) = O ( n l o g b ( a ) l o g k n ) f(n) = O(n^ {log_b(a )}log^{k}n) f(n)=O(nlogb(a)logkn)

可得 n 2 = Θ ( n l o g 2 ​ 4 l o g 0 n ) = Θ ( n 2 ) n^{2}=Θ(n^{log_{2}​4}log^{0}n)=Θ(n^{2}) n2=Θ(nlog2​4log0n)=Θ(n2)

∴ T ( n ) = Θ ( n 2 l o g n ) \therefore T(n)=Θ(n^{2}logn) T(n)=Θ(n2logn)


情况三:

T ( n ) = 2 T ( n 2 ) + n 2 T(n)=2T(\frac{n}{2})+n^{2} T(n)=2T(2n)+n2

其中 a = 2 ≥ 1 , b = 2 > 1 , f ( n ) = n 2 , l o g 2 2 = 1 < 2 a = 2\ge1,b = 2>1,f(n) = n^{2},log_{2}2=1<2 a=21b=2>1f(n)=n2log22=1<2

根据主定理的第三种情况: f ( n ) = Ω ( n l o g b ( a ) + ε ) f(n) = Ω(n^ {log_b(a )+ε }) f(n)=Ω(nlogb(a)+ε)

可得 n 2 = Ω ( n l o g 2 ​ 2 + ε ) = Ω ( n 1 + ε ) n^{2}=Ω(n^{log_{2}​2+ε})=Ω(n^{1+ε}) n2=Ω(nlog2​2+ε)=Ω(n1+ε)

但我们还需要检查是否满足 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) af(bn)cf(n) 的条件:

2 ⋅ ( n / 2 ) 2 ≤ c ⋅ n 2 n 2 / 2 ≤ c ⋅ n 2 1 / 2 ≤ c 2·(n/2)^{2}≤c·n^{2}\\ n^{2}/{2}≤c·n^{2}\\ 1/2≤c 2(n/2)2cn2n2/2cn21/2c

对于任何小于 1/2 的常数 c c c,上述不等式都成立

∴ T ( n ) = Θ ( n 2 ) \therefore T(n)=Θ(n^{2}) T(n)=Θ(n2)


http://www.ritt.cn/news/22498.html

相关文章:

  • 设计好用的网站如何自己开发一个平台
  • 湖南做网站的公司排名种子搜索神器网页版
  • 做国内电影网站赚钱不2022今日最新军事新闻
  • 《原始传奇》官方网站上海广告公司排名
  • 昆明网站建设费用广东网站seo策划
  • 做网站大概需要几个人网站建设的六个步骤
  • 云南做商城网站多少钱权重查询站长工具
  • asp.net课程网站模板下载西安关键词优化服务
  • 做中小型网站最好的架构武汉seo搜索引擎
  • 免费网站主机推广策略都有哪些
  • 2016做网站深圳网站建设资讯
  • 龙岩市住房与城乡建设局网站图片优化网站
  • 网站建设优化服务报价最近一周的新闻
  • 如何做点对点视频网站天津seo博客
  • 西安网站网络营销上海网络营销有限公司
  • 企业网站的基本要素seo优化技术教程
  • 桂林生活网二手市场seo网站关键词优化哪家好
  • 做直播网站赚钱吗1688如何搜索关键词排名
  • 建设网站视频教程广告行业怎么找客户
  • wordpress做论坛seo综合查询是啥意思
  • 如何编辑网站内容东莞快速排名
  • 做时时的网站qq群推广链接
  • 阿里云网站建设视频成都网站关键词排名
  • 微信上做任务让你注册彩票网站seo的优点有哪些
  • 做网站用什么cms网站模板哪里好
  • 网络营销案例分析范文游戏行业seo整站优化
  • 网上商城都有哪些平台河南seo优化
  • 旅游网站做模板素材凡科建站后属于自己的网站吗
  • 在哪做网站专业网络舆情分析师
  • 网站咨询窗口怎么做广东seo网站设计