MasterTheorem

Master Therem,翻译成:主定理、主方法、主项定理、大师定理。我个人觉得翻译成大师定理不错,酷酷的。

一般情况下

先简单看先O(lg(k)),

在二分查找、堆的操作中,一次操作就可以减少一半的工作量,一次循环就少一半,效率不就是 lg(k) 嘛。

递归的时间复杂度

问题在于,对于递归求解的时间复杂度分析。

下面的内容转自 架构师之路公众号

案例一:计算 1到n的和

时间复杂度分析。

int sum(int n){
    if (n==1) return 1;
    return n+sum(n-1);
}

如何来进行时间复杂度分析呢?

用f(n)来表示数据量为n时,算法的计算次数,很容易知道:

  • 当n=1时,sum函数只计算1次

画外音:if (n==1) return 1;

即:

f(1)=1【式子A】

不难发现,当n不等于1时:

  • f(n)的计算次数,等于f(n-1)的计算次数,再加1次计算

画外音:return n+sum(n-1);

即:

f(n)=f(n-1)+1【式子B】

【式子B】不断的展开,再配合【式子A】:

画外音:这一句话,是分析这个算法的关键。

f(n)    =f(n-1)+1

f(n-1)    =f(n-2)+1

…

f(2)    =f(1)+1

f(1)    =1

上面共n个等式,左侧和右侧分别相加:

f(n)+f(n-1)+…+f(2)+f(1)

=

[f(n-1)+1]+[f(n-2)+1]+…+[f(1)+1]+[1]

即得到

f(n)=n

已经有那么点意思了哈,再来个复杂点的算法。

案例二:二分查找binary_search,

时间复杂度分析。

int BS(int[] arr, int low, int high, int target){

         if (low>high) return -1;

         mid = (low+high)/2;

         if (arr[mid]== target) return mid;

         if (arr[mid]> target)

                  return BS(arr, low, mid-1, target);

         else

                  return BS(arr, mid+1, high, target);

}

二分查找,单纯从递归算法来分析,怎能知道其时间复杂度是O(lg(n))呢?

仍用f(n)来表示数据量为n时,算法的计算次数,很容易知道:

  • 当n=1时,bs函数只计算1次

画外音:不用纠结是1次还是1.5次,还是2.7次,是一个常数次。

即:

f(1)=1【式子A】

在n很大时,二分会进行一次比较,然后进行左侧或者右侧的递归,以减少一半的数据量:

  • f(n)的计算次数,等于f(n/2)的计算次数,再加1次计算

画外音:计算arr[mid]>target,再减少一半数据量迭代

即:

f(n)=f(n/2)+1【式子B】

【式子B】不断的展开,

f(n)    =f(n/2)+1
f(n/2)    =f(n/4)+1
f(n/4)    =f(n/8)+1
…
f(n/2^(m-1))=f(n/2^m)+1

上面共m个等式,左侧和右侧分别相加:

f(n)+f(n/2)+…+f(n/2^(m-1))

=

[f(n/2)+1]+[f(n/4)+1]+…+[f(n/2^m)]+[1]

即得到

f(n)=f(n/2^m)+m

再配合【式子A】:

f(1)=1

即,n/2^m=1时, f(n/2^m)=1, 此时m=lg(n), 这一步,这是分析这个算法的关键。

将m=lg(n)带入,得到

f(n)=1+lg(n)

神奇不神奇?

最后,大boss,快速排序递归算法,时间复杂度的分析过程。

案例三:快速排序quick_sort

时间复杂度分析。

void quick_sort(int[]arr, int low, inthigh){
    if (low==high) return;
    int i = partition(arr, low, high);
    quick_sort(arr, low, i-1);
    quick_sort(arr, i+1, high);
}

仍用f(n)来表示数据量为n时,算法的计算次数,很容易知道:

  • 当n=1时,quick_sort函数只计算1次

f(1)=1【式子A】

在n很大时:

第一步,先做一次partition;

第二步,左半区递归;

第三步,右半区递归;

即:

f(n)=n+f(n/2)+f(n/2)=n+2*f(n/2)【式子B】

画外音:

(1)partition本质是一个for,计算次数是n;

(2)二分查找只需要递归一个半区,而快速排序左半区和右半区都要递归,这一点在分治法减治法一章节已经详细讲述过;

【式子B】不断的展开,

f(n)    =n+2*f(n/2)
f(n/2)    =n/2+2*f(n/4)
f(n/4)    =n/4+2*f(n/8)
…
f(n/2^(m-1))=n/2^(m-1)+2f(n/2^m) 

上面共m个等式,逐步带入,于是得到:

f(n) =n+2*f(n/2)

​ =n+2[n/2+2f(n/4)]=2n+4*f(n/4)

​ =2n+4[n/4+2f(n/8)]=3n+8f(n/8)

​ =…

​ =mn+2^mf(n/2^m)

再配合【式子A】:

f(1)=1

即,n/2^m=1时, f(n/2^m)=1, 此时m=lg(n), 这一步,这是分析这个算法的关键。

将m=lg(n)带入,得到:

f(n)=lg(n)n+2^(lg(n))f(1)=n*lg(n)+n

故,快速排序的时间复杂度是n*lg(n)。

wacalei,有点意思哈!

画外音:额,估计83%的同学没有细究看,花5分钟细思上述过程,一定有收获。

总结

  • for循环的时间复杂度往往是O(n)
  • 树的高度的时间复杂度往往是O(lg(n))
  • 二分查找的时间复杂度是O(lg(n)),快速排序的时间复杂度n*(lg(n))

转载请注明: 炫杉 MasterTheorem

上一篇
Hexo使用问题总结 Hexo使用问题总结
汇总一下Hexo遇到的问题,以及以后出现问题都会更新到这里 独立贴 插图问题 在Git仓库设置一个分支推送源码,主分支负责展示 有时候想传一个静态的HTML页面直接放在Source文件夹,不想被Hexo g的时候渲染,怎么办呢? He
2018-11-28
下一篇
LeetCode51-100 LeetCode51-100
int的范围、牛顿迭代法[69] copy(1.begin,1.end,2.begin)、rbegin\rend[88] 51N皇后52N皇后 II53. 最大子序和暴力写出来了。人家怎么就想到这么写呢: int res = I
2018-11-21