新闻中心> 文章详情

Java中算法复杂度分析方法

2016年03月11日

  最近在Java课程时看stanford的算法导论公开课,讲到分治法的时候提到了主方法,可以很快速的分析算法的时间复杂度。南京Java培训

 

  对于一个递归实现的分治算法,其时间复杂度表示为:

 

  T(n) = aT(n/b)+h(n)

 

  其中,a>=1; b>1; h(n)是不参与递归部分的时间复杂度。

 

  比较n^log b (a)与Θ(h(n)) 的大小(Θ的含义和“等于”类似,而大O的含义和“小于等于”类似,感觉好像这里都可以用):南京Java培训

 

  若n^log b (a)= Θ(h(n)) :该方法的复杂度为 Θ(h(n)*log(n))

 

  若n^log b (a)< Θ(h(n)) :该方法的复杂度为 Θ(h(n))

 

  若n^log b (a)> Θ(h(n)) :该方法的复杂度为 Θ(n^log b (a))

 

  例如: 南京Java培训

 

  T(n) = T(n/2)+1:Θ(log(n))(二分查找)

 

  T(n) = 2T(n/2)+n :Θ(n*log(n))(归并排序)

 

  以上都属于“等于”的情况。


上一篇下一篇
按时发顺丰

技术交流群

Java大数据交流群560819979    加入
Python技术交流群595083299    加入
Oracle技术交流群595119011    加入
Web前端技术交流群604697610    加入
Huawei技术交流群482919361    加入
Redhat技术交流群587875348    加入
UI设计技术交流群511649801    加入
Cisco技术交流群596886705    加入
IT运维技术交流群605888381    加入