❤️💕💕算法学习笔记和LeetCode的刷题笔记与记录。Myblog:http://nsddd.top
[TOC]
master公式（也称主方法）是用来利用分治策略来解决问题经常使用的时间复杂度的分析方法，（补充：分治策略的递归解法还有两个常用的方法叫做代入法和递归树法），分治策略中使用递归来求解问题分为三步走，分别为分解、解决和合并，所以主方法的表现形式： $$ T [n] = aT[\frac{n}{b}] + f (n) $$ 或直接记为 $$ T [n] = aT[\frac{n}{b}] + T (N^d) $$ 其中
- a >= 1 and b > 1 是常量
- n表示问题的规模
- a表示递归的次数也就是生成的子问题数
- b表示每次递归是原来的1/b之一个规模
- f（n）表示分解和合并所要花费的代价之和
解法： ①当d<log(b,a)时，时间复杂度为O(n^(logb a)) ②当d=log(b,a)时，时间复杂度为O((n^d)*logn) ③当d>log(b,a)时，时间复杂度为O(n^d)
package class01
public class Max {
public static int getMax(int[] arr ){
return process(arr,0,arr.length-1)
}
//求arr[L...R]的范围中的最大值
public static int process(int[] arr,int L,int R){
if(L == R){
return arr[L]; //arr[R]
}
int mid = L + ((R - L) >> 1); //🕐1
int leftMax = process(arr,L,mid);
int reghtMax = process(arr,mid + 1,R);
return Math.max(leftMax,reghtMax);
}
}🕐1求中间的一个数值我们很容易想到的是用： $$ mid = \frac{R + L}{2} $$ 可能造成的后果是mid本身定义的是int类型，可能造成越界变成负数，所以同样的我们采用移位操作
- a = 2
- b = 2
- d = 0 (其他的代码都是O(1))
子问题的规模树需要一样的，比如上面的求最大值，可以拆分为1/2,也可以拆分为1/3。
但是需要保证的是规模是一样的，就算是2/3有重复的部分也可以使用master公式。
但是当一边是1/3规模，一边是2/3规模的情况，就不适合用master公式了。
1s 内能解决问题的数据规模：10^6 ~ 10^7
- O(n^2) 算法可以处理 10^4 级别的数据规模(保守估计，处理 1000 级别的问题肯定没问题)
- O(n) 算法可以处理 10^8 级别的数据规模(保守估计，处理 10^7 级别的问题肯定没问题)
- O(nlog n) 算法可以处理 10^7 级别的数据规模(保守估计，处理 10^6 级别的问题肯定没问题)
| 数据规模 | 时间复杂度 | 算法举例 | |
|---|---|---|---|
| 1 | 10 | O(n!) | permutation 排列 |
| 2 | 20~30 | O(2^n) | combination 组合 |
| 3 | 50 | O(n^4) | DFS 搜索、DP 动态规划 |
| 4 | 100 | O(n^3) | 任意两点最短路径、DP 动态规划 |
| 5 | 1000 | O(n^2) | 稠密图、DP 动态规划 |
| 6 | 10^6 | O(nlog n) | 排序，堆，递归与分治 |
| 7 | 10^7 | O(n) | DP 动态规划、图遍历、拓扑排序、树遍历 |
| 8 | 10^9 | O(sqrt(n)) | 筛素数、求平方根 |
| 9 | 10^10 | O(log n) | 二分搜索 |
| 10 | +∞ | O(1) | 数学相关算法 |
| — | ———— | ————————— | —————————————————————— |
一些具有迷惑性的例子：
void hello (int n){
for( int sz = 1 ; sz < n ; sz += sz )
for( int i = 1 ; i < n ; i ++ )
cout << "Hello" << endl;
}上面这段代码的时间复杂度是 O(nlog n) 而不是 O(n^2)
bool isPrime (int n){
for( int x = 2 ; x * x <= n ; x ++ )
if( n % x == 0 )
return false;
return true;
}上面这段代码的时间复杂度是 O(sqrt(n)) 而不是 O(n)。
再举一个例子，有一个字符串数组，将数组中的每一个字符串按照字母序排序，之后再将整个字符串数组按照字典序排序。两步操作的整体时间复杂度是多少呢？
如果回答是 O(n*nlog n + nlog n) = O(n^2log n)，这个答案是错误的。字符串的长度和数组的长度是没有关系的，所以这两个变量应该单独计算。假设最长的字符串长度为 s，数组中有 n 个字符串。对每个字符串排序的时间复杂度是 O(slog s)，将数组中每个字符串都按照字母序排序的时间复杂度是 O(n * slog s)。
将整个字符串数组按照字典序排序的时间复杂度是 O(s * nlog n)。排序算法中的 O(nlog n) 是比较的次数，由于比较的是整型数字，所以每次比较是 O(1)。但是字符串按照字典序比较，时间复杂度是 O(s)。所以字符串数组按照字典序排序的时间复杂度是 O(s * nlog n)。所以整体复杂度是 $$ O(n * slog s) + O(s * nlog n) = O(nslog s + snlogn) = O(ns(log s + log n)) = O(nslog(n*s)) $$
递归调用是有空间代价的，递归算法需要保存递归栈信息，所以花费的空间复杂度会比非递归算法要高。
int sum( int n ){
assert( n >= 0 )
int ret = 0;
for ( int i = 0 ; i <= n ; i ++ )
ret += i;
return ret;
}上面算法的时间复杂度为 O(n)，空间复杂度 O(1)。
int sum( int n ){
assert( n >= 0 )
if ( n == 0 )
return 0;
return n + sum( n - 1 );
}上面算法的时间复杂度为 O(n)，空间复杂度 O(n)。
如果递归函数中，只进行了一次递归调用，且递归深度为 depth，在每个递归函数中，时间复杂度为 T，那么总体的时间复杂度为 O(T * depth)
举个例子：
int binarySearch(int arr[], int l, int r, int target){
if( l > r )
return -1;
int mid = l + ( r - l ) / 2; // 防溢出
if(arr[mid] == target)
return mid;
else if (arr[mid] > target)
return binarySearch(arr,l,mid-1,target);
else
return binarySearch(arr,mid+1,r,target);
}在二分查找的递归实现中，只递归调用了自身。递归深度是 log n ，每次递归里面的复杂度是 O(1) 的，所以二分查找的递归实现的时间复杂度为 O(log n) 的。
针对多次递归调用的情况，就需要看它的计算调用的次数了。通常可以画一颗递归树来看。举例：
int f(int n){
assert( n >= 0 );
if( n == 0 )
return 1;
return f( n - 1 ) + f ( n - 1 );
}上述这次递归调用的次数为 2^0^ + 2^1^ + 2^2^ + …… + 2^n^ = 2^n+1^ - 1 = O(2^n)
关于更加复杂的递归的复杂度分析，请参考主定理。主定理中针对各种复杂情况都给出了正确的结论。