算法的时间复杂度和空间复杂度

目录

算法效率

算法的复杂度

 时间复杂度

时间复杂度的概念

大O的渐进表示法

常见的时间复杂度举例

空间复杂度

 常见复杂度对比

---

算法效率

算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

 时间复杂度

时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

在以下代码中，请计算一下Func1中++count语句总共执行了多少次？ 

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

Func1 执行的基本操作次数：

N = 10     F(N) = 130

N = 100   F(N) = 10210

N = 1000 F(N) = 1002010

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

大O的渐进表示法

大O符号：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1.如果程序运行常数次，那么认为时间复杂度为1，即O(1)。

2.在修改后的运行次数函数中，只保留最高阶项。

3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后，Func1的时间复杂度为：

N = 10     F(N) = 100

N = 100   F(N) = 10000

N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。

常见的时间复杂度举例

例1：

// 计算Func2的时间复杂度？
void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

在这段程序中，执行次数是2*N+10,根据上面所说的推导大O阶方法可知，该程序的时间复杂度是O(N)。

例2：

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

在这段程序中，执行次数是M+N，由于M和N都不是常数，因此时间复杂度是O(M+N)。

例3：

// 计算Func4的时间复杂度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

在这段程序中，由于代码执行了常数次（100次），因此代码的时间复杂度是O(1)，注意，这里的1不是指1次。而是指常数次。也就是说，哪怕代码执行了10000次、100000次，其时间复杂度仍然是O(1)。

例4：

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

这段程序就是我们之前说的存在最好、平均、最坏情况，在这种情况下，我们关注的是算法的最坏运行情况，因此，此算法的时间复杂度是O(N)。

例5：

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

该程序的执行次数为N-1 N-2 ...1这样的等差数列，求和(N-1)*N/2,最高阶数为1/2*N^2，因此，省略前面的相乘系数1/2，算法的复杂度是O(N^2)。

例6：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]：begin和end是左闭右闭区间，因此有=号
	while (begin <= end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

因此，算法的时间复杂度是

例7：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}

Fac(N)       运行1次

Fac(N-1)    运行1次

...

Fac(1)       运行1次

Fac(0)       运行1次

共运行N+1次，因此算法复杂度是O(N)。

例7plus

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	int i = 0;
	for (i = 0; i < N; i++)
	{
		//...
	}
	return Fac(N - 1) * N;
}

Fac(N)       运行N次

Fac(N-1)    运行N-1次

...

Fac(1)       运行1次

Fac(0)       运行0次

这也是一个等差数列，求和可知此算法复杂度是O(N^2)。

 举个例子：

有这样一道题：消失的数字，数组nums包含0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数，要求在O(N)时间内完成。

这里有三种解法：

1.排序，依次查找，如果下一个数不是上一个数+1，那么上一个数+1就是消失的数字。这种方法如果先采用快速排序，那么快速排序算法的时间复杂度为O(N*log(N))，然后再查到，最多查到N次，但是N和N*logN相比可以忽略，因此，这种方法的复杂度是O(N*logN)，时间复杂度较大。

2.异或，定义x=0，让size个数组元素依次和x异或，再让0-size这size+1个数与x依次异或，最后x是几，缺失的就是几。

int missnumber(int arr[], int size)
{
	int x = 0;
	int i = 0;
	for (i = 0; i < size; i++)
	{
		x ^= arr[i];
	}
	for (i = 0; i < size + 1; i++)
	{
		x ^= i;
	}
 
	return x;
}
int main()
{
	int arr[] = { 0,1,2,4};
	int ret = missnumber(arr, sizeof(arr)/sizeof(arr[0]));
	printf("%d\n",ret);
	
	return 0;
}

 这个算法的迭代次数是N+N+1，即2N+1，那么算法复杂度是O(N)。

3.  0-N等差数列求和，再减去数组中的每个元素。

int missnumber(int arr[], int size)
{
	int i = 0;
	int sum = (0 + size) * (size+1) / 2;
 
	for (i = 0; i < size; i++)
	{
		sum -= arr[i];
	}
 
	return sum;
}
int main()
{
	int arr[] = { 0,1,2,3,4,5,7,8};
	int ret = missnumber(arr, sizeof(arr)/sizeof(arr[0]));
	printf("%d\n",ret);
	
	return 0;
}

在这个算法中，迭代次数是size，因此，算法时间复杂度是O(N)。

例8：

// 计算斐波那契递归Fib的时间复杂度？
	long long Fib(size_t N)
	{
		if (N < 3)
			return 1;
		return Fib(N - 1) + Fib(N - 2);
	}

等比数列求和结果为2^(n-1)-1，但是实际执行次数肯定比这个次数少，但是时间复杂度就是算一个大概，因此，这个算法时间复杂度是O(2^n)。

空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

实例1：

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

在这个算法中，创建了end、exchange、i三个变量，为常数个，因此空间复杂度为O(1)。

实例2:

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
	if (n == 0)
		return NULL;
	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}

在这个算法中，使用malloc动态内存开辟了n+1个空间，因此，这个算法的空间复杂度是O(N)。

实例3：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
     if(N == 0)
         return 1;
 
     return Fac(N-1)*N;
}

在这个问题中，共有N次递归调用，在每次递归调用时，都会开辟函数栈帧，相当于开辟了N块空间，每个函数栈帧里都有常数个变量，因此，该问题的空间复杂度时O(N)。

实例4：

// 计算斐波那契递归Fib的空间复杂度？
	long long Fib(size_t N)
	{
		if (N < 3)
			return 1;
		return Fib(N - 1) + Fib(N - 2);
	}

这个代码和上面的例8完全一样，执行过程也完全一样，但是求得时空间复杂度，在递归时，函数先往深调用，最多创建N个函数栈帧，但最后的Fib(2)调用结束后，Fib(2)函数栈帧销毁，开辟和其同一深度的函数栈帧Fib(1)，此时还是N个函数栈帧，然后销毁Fib(1)的函数栈帧，创建上一深度Fib(3)的函数栈帧，再销毁，。。。，依次往复，在这个过程中，最多创建N个函数栈帧，因此空间复杂度为O(N)。

这里我们记住这样几句话:

时间是一去不复返的，时间是累计计算的；空间是可以重复利用，不累计计算。

 常见复杂度对比