数据结构初阶之算法的时间复杂度和空间复杂度_等比数列求和时间复杂度

目录

算法效率

算法的复杂度

时间复杂度

等差数列与等比数列

等差数列

等比数列

时间复杂度的概念

大O的渐进表示法

练习

空间复杂度

空间复杂度概念

练习

常见复杂度对比

算法效率

算法的复杂度

任何一段代码运行时都需要耗费时间与空间（内存），所以一段代码可以从时间与空间的角度来判断它的好坏，因此就有了时间复杂度与空间复杂度。

时间复杂度主要是衡量一个代码运行的快慢，空间复杂度主要是衡量一段代码运行时需要多少额外的空间，不过因为现在的内存空间够大，所以空间复杂度显得不是很重要。

时间复杂度

时间复杂度开始前， 因为时间复杂度涉及很多的等差以及等比数列，所以先复习一下相关的概念

等差数列与等比数列

等差数列

就是数列从第二项起，每一项与前一项的差是一个常数的数列。这个常数叫做等差数列的公差。

等差数列求最后一项：an=a1+(n-1)*d。

等差数列求和：sum=(a1+an)*n/2。

等比数列

就是数列从第二项起，每一项与前一项的比值是一个常数的数列。这个常数叫做等比数列的公比。

等比数列求最后一项：an=a1*q^(n-1)。

等比数列求和有两种情况：

一、当q=1时：sum=n*a1。

二、当q!=1时：a1*(1-q^(n))/1-q。 

时间复杂度的概念

算法的时间复杂度时一个数学的函数式，它定量描述了算法的运行时间（算法执行所废的时间，理论上说是无法计算出来，因为每台设备不同，而且实际测试很麻烦），一个算法所花费的时间与执行次数成正比，所以算法中基本操作的执行次数，为算法的时间复杂度。

即；找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

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

大O的渐进表示法

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

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。（当执行次数固定时，也可以用1代替）。

2、在修改后的运行次数的函数中，只保留最高阶项。（最高阶对结果产生决定性的影响）。

3、如果最高阶系数存在且不是1，则去除与最高阶相乘的系数，得到的结果就是大O阶。

注意：现在的CPU运行次数足够快，所以可以用1代替。

另外有些算法的时间复杂度存在最好，平均，最坏的情况：

最好情况：任意输入规模的最小运行次数（下界）。

平均情况：任意输入规模的期望运行次数。

最坏情况：任意输入规模的最大运行次数（上界）。

实际中一般关注的是最坏的情况。

练习

// 请计算一下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;
}

上面的代码分为三部分，一是双重循环部分，而是2N循环部分，3是m=10部分。

双重循环部分的程序执行的次数是n^2,2N循环部分程序执行的次数是2N，m部分程序执行次数为10，所以精确的时间复杂度是O(N^2+2N+10)，大O渐进表示法表示的是估计的数，按照表述，常数的部分删除，删除非最高阶项，删除最高阶的系数部分，最后的结果是O(N^2)。

// 计算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);
}

 

 该段代码第一个循环从0到2N-1，一共执行了2N次，第二个循环从10到1，一共执行了10次，所以精确的时间复杂度为O（2N+10），大O渐进法只保留最高阶则为O（N）。

注意：判断时间复杂度并不是用循环的次数判断。

// 计算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);
}

上面的代码时间复杂度为O（M+N）。为什么是M+N。

因为M与N的大小并不能确定，且都不是常数项，所以需要保留。

void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

上面代码在的时间复杂度为O（1），数据结构中所有的常数项的时间复杂度都是O（1）。

const char * strchr ( const char * str, int character );

上面的代码有三种情况

1、最好的情况下只执行1次就找到字符的位置，此时的时间复杂度为O(1)。

2、平均的情况，执行N/2次找到字符的位置，此时的时间复杂度为O(N)。

3、最坏的情况，遍历整个字符串都没有找到或者最后一个字符是，此时时间复杂度为O(N)。

// 计算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次后完成，此时时间复杂度为O(N)。

平均时，在n^2/2次，时间复杂度为O(N^2)。

// 计算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;
}

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

0的阶乘为1，其后的阶乘为n*(n-1)!。

 

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

总共执行次数2^N

时间复杂度o(2^N) 

int main()
{
	int i = 1;
	int j = 1;
	int k = 0;
	int l = 10;
	for (l = 0; l < 8; l++)
	{
		k = i + j;
		i = j;
		j = k;
	}
	printf("%d", k);
	system("pause");
	return 0;
}

迭代的斐波那契数列求解，时间复杂度为O（N）。 

空间复杂度

空间复杂度概念

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

空间复杂度计算的也不是字节的大小，而是变量的个数。也使用大O渐进法。

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

练习

// 计算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;
 }
}

空间复杂度为O（1），因为使用常数个变量。

// 计算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;
}

空间复杂度为O（N），因为函数内开辟了fibArray的空间。

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

 

程序调用零时空间为N个，所以空间复杂度为O（N）。 

常见复杂度对比