递归时间复杂度

时间复杂度

递归求斐波那契数列时间复杂度:O(2^n)

递归树分析

节点单一子问题代价：函数执行过程中，除去递归调用以外的代价

比如：

int fib(int n){
	if(n==1 || n==2){//前2项直接返回
		return 1;
	}
	return fib(n-1)+fib(n-2);//第3项=前两项之和
}

1 n=1 或 n=1时，return 1 时间复杂度为O(1)

2 n>2时 执行： fib(n-1)+fib(n-2) 除去递归，只有加法运算 时间复杂度为O(1)

3 需要计算整个过程多少个O(1)

4 如果是完美二叉树，即：所有都填满的情况下为O(2^n)

因此时间复杂度粗略计算为O(2^n)

实际再(sqrt(2))^n ~2^n之间，粗略计算 O(2^n)

精确计算其时间复杂度为：((1+sqrt(5))/2)^n

归并排序

分析

使用归并排序，

1 从中间把数列分成左右两部分

2 把分成的左右2部分中每部分再分成左右2部分

3 一直分下去，直到分拆成1个数

4 再按刚才拆的顺序合并

参考程序

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,a[N],tmp[N];

void merge(int L,int R,int mid){
	int i=L,j=mid+1,k=L;
	while(i<=mid && j<=R){
		if(a[i]<a[j]){
			tmp[k++]=a[i++]; 
		}else{
			tmp[k++]=a[j++];
		}
	}
	while(i<=mid) tmp[k++]=a[i++];
	while(j<=R)   tmp[k++]=a[j++];
	for(int i=L;i<=R;i++){
		a[i]=tmp[i];
	}
}

void mergeSort(int L,int R){
	if(L>=R) return;
	int mid=L+(R-L)/2;
	mergeSort(L,mid);//左半部分排序
	mergeSort(mid+1,R);//右半部分排序
	merge(L,R,mid);//合并
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	mergeSort(0,n-1);
	
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

时间复杂度

归并排序时间复杂度为：O(n*logn)

节点单一子问题代价：函数执行过程中，除去递归调用以外的代价

归并排序被拆分了 logn层，每层合并代价为n，所以总代价为n*logn