时间复杂度与空间复杂度_空间复杂度和时间复杂度的关系

算法效率主要看两方面：

1.时间复杂度；

时间复杂度是一个函数，它定性描述该算法的运行时间用大写O表示

需要熟悉

 

 

 则时间复杂度用该是T（N）= N^2 +N + 10 而根据“大O的渐进表示法“（实际计算时间复杂度时，我们其实并不一定要精确的计算我们的执行次数，只需要一个大概的执行次数）

大O的渐进表示法：

①用常数1来表达运行时间中的所有加法常数
②在修改后的运行次数函数中，只保留最高阶
③若最高阶存在且其项数不为1，那么项数化为1

 

int BinarySearch(int* a, int n, int x)//折中查找
{
	assert(a);//传递数组
	int begin = 0;//首标
	int end = n - 1;//尾标
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

 

 

 

long long Func2(int N)//递归函数
{
	if (N == 1)
		return 1;
 
	return Func2(N - 1)*N;
}

斐波那契数列 

long long Fib(int N)//斐波那契数列
{
	if (N < 3)
		return 1;
 
	return Fib(N - 1) + Fib(N - 2);
}

当我们第一次进入Fib函数时，会第一次支出代码块中的内容，此时会产生Fib（N-1）和Fib（N-2），然后通过递归，进入第二次Fib函数，此时在面对第一次产生的两个Fib函数，各自再一次进行代码块的内容，产生对应的Fib函数，直到Fib函数中的"N"< 3，结束递归，开始逐一返回，结束程序

 

 

2.空间复杂度；

1.空间复杂度

即该算法所消耗的储存空间，是对一个算法在运行过程中临时占用存储空间大小的量度 。也可以说是，记录在栈区中，每创建一个栈帧，在该栈帧中需要额外创建的空间大小，即就是记录变量的个数。

void Func1(int N)
{
	for (int i = 0; i < N; i++)
	{
		printf("hahaha");
	}
 
	for (int j = 0; j < N; j++)
	{
		pirntf("lalala");
	}
 
	while (N--)
	{
		printf("xixixi");
	}
 
}

在栈区Func1栈帧中 金创建了两个变量， 空间复杂度：O（1）；

 

斐波那契数列：

long long Fib(int N)//斐波那契数列
{
	if (N < 3)
		return 1;
 
	return Fib(N - 1) + Fib(N - 2);
}

时间复杂度和空间复杂度的关系：时间是可以累积的，空间是可重复利用的（

时间复杂度，每在一个循环条件或者递归条件中，执行一次操作，就记录一次；

空间复杂度，如递归问题中，当某一个栈帧执行结束时，这个栈帧的空间就会被释放，这个地方的空间就暂时无人使用，但其他递归函数再一次运行时，这一处的空间，可能会再一次用来执行刚刚被释放的递归函数内的代码块，所以空间是可以充分利用的

）