【数据结构】算法的复杂度-EW帮帮网

前言：经过了C语言的学习，紧接着就步入到数据结构的学习了。在C语言阶段我们在写大多数的oj题的时候会遇到一些问题，就是算法的效率低使用的时间较多，占用的空间也多，数据结构就是来优化算法的。

文章目录

一，数据结构和算法
二，算法的效率

一，数据结构和算法

1，什么是数据结构

数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构，如：线性表、树、图、哈希等。

2，什么是算法

算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是⼀系列的计算步骤，⽤来将输入数据转化成输出结果。

3，算法的重要性

算法的好坏可以不仅反应一个程序员写代码的水平有多高，在程序运行的时候还能节省空间和时间，所以算法的优化是非常重要的。其次，在找工作的时候企业面试也会考算法。

知道了算法的重要性，就来看看如何来改进算法。

二，算法的效率

算法效率顾名思义，算法越好占用的时间和空间越少，效率越高。算法的越差占用的时间和空间越多，算法效率越差。
我们以一道算法题为例：
旋转数组

void rotate(int* nums, int numsSize, int k) 
{ 
	while(k--) 
	{ 
		int tmp = nums[numsSize-1]; 
		for(int i = numsSize - 1;i > 0 ;i--) 
		{ 
			nums[i] = nums[i-1]; 
		}
		nums[0] = tmp; 
	} 
}

思路是将第一个元素保存，再将后面的元素往前移动最后再将前面的元素放到后面的空位，轮转几次就循环几次。

在这里插入图片描述

但是力扣却说超出了时间限制，这就说明我们设计的算法不够好，需要优化。既然是时间超出了限制那么就有人要问了如何优化算法呢？

我们给出一个概念叫时间复杂度。紧接着我们就来介绍一下什么是时间复杂度。

1，时间复杂度的概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。
在早期计算机的内存很小所以人们比较关注内存的占用情况，但如今计算机的内存容量已经可以达到一个很高的程度所以当今人们更加关注时间的效率，更加关注时间复杂度。

2，时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N),比如正比例函数f(x)=kx,它定量描述了该算法的运行时间。时间复杂度可以衡量程序的时间效率。

那怎么去计算时间复杂度呢？是计算程序运行的时间，还是程序运行的次数呢？ 答案是，通过运行的次数去算时间复杂度。

为什么呢？
由于程序运行的时间受到多种因素的影响比如：编译器的不同，机器的配置不同都会影响程序的运行时间是不好测量的。
我们知道算法程序被编译后生成二进制指令，程序运行，就是cpu执⾏这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么执⾏次数和运⾏时间就是等⽐正相关，这样也脱离了具体的编译运⾏环境。所以执行次数就可以代表程序时间效率的优劣。比如解决⼀个问题的算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率⼀定优于算法b。

所以我们得出一个等式：程序执行的时间 = 二进制指令运行时间 * 执行次数。二进制指令运行的时间可以假设是一样的。所以时间就看次数。

有了上面的了解，紧接着趁热打铁拿一些程序来练练手：

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

通过上面的代码我们能很明显的看出来，count总共执行了NN次+2N次+10次，写成函数表达式就是：T(N)=N^2+2*N+10

3，大O渐进表示法

对于这个式子要怎么看呢？
要看懂这个式子就要明白大O的渐进表示法，什么是大O的渐进表示法呢？

⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号
在这里插入图片描述
回到这个式子：T(N)=N^2+2*N+10 通过第一条规则我们知道高阶项随着N变大对式子的影响比较大，低阶项随着N变大对式子的影响越来越小所以我们要保留高阶项去掉低阶项。我们在学数学的时候也学过越高阶的项对整个式子越大，也印证了这一点。

所以上面代码最终的时间复杂度为:O(N^2)，复杂度的表=示通常使用大O的渐进表示法。

再来看一段代码，计算时间复杂度

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

上面代码执行次数为：T(N)=2N+10 前面我们知道了，高阶项对整个式子的影响较大所以我们因该保留高阶项去掉低阶项。难道这里的时间复杂度是O(2N)吗？

答案是否定的，我们再来看看推导大O阶的第二条规则，当高阶项存在且系数不是1，就取出系数，在这里就相当于去掉2N中的2变成了N。原因也很简单当N不断变大系数对结果的影响越来越小所以可以去掉。

所以上面代码最终的时间复杂度为: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); 
}

上面代码的执行次数为：第一个for循环执行M次+第二个for循环执行N次。
这里不知道M和N到底谁大所以我们分情况讨论：

当M==N的时候时间复杂度为O(M)或O(N)
当M>>N的时候时间复杂度为O(M)
当N>>M的时候时间复杂度为O(N)

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

上面代码的执行次数：就为for循环执行的100次，那时间复杂度为O(100)吗？
答案是否定的，再来看看推导大O阶的第三条规则，当T(N)中没有与N有关的项时直接用1来代表所有加法常数.

所以时间复杂度为O(1).

// 计算strchr的时间复杂度？ 
const char * strchr ( const char * str, int character) 
{ 
	const char* p_begin = s; 
	while (*p_begin != character) 
	{
		if (*p_begin == '\0') 
		return NULL; 
		p_begin++; 
	} 
	return p_begin; 
}

上面是一个查找字符的代码，那么执行次数由上面决定呢？

答案是由该字符所处在的位置来决定，所以我们还是分类讨论：当字符在第一个位置，则程序执行一次就能将其找到；所以时间复杂度为O(1)
当字符在中间位置时，假设有N个字符，则程序至少要执行N/2次才能找到；所以时间复杂度为O(N/2)
当字符在最后一个位置时，假设有N个字符，则程序要执行N次才能将其找到；所以时间复杂度为O(N)

计算strchr的时间复杂度分为几种情况：
最好情况：O(1)
最坏请况：O(N)
平均情况：O(N/2)

在这里插入图片描述
接着再来计算一些复杂程序的时间复杂度：

// 计算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(N^2)。

再看一个代码：

void func5(int n) 
{ 
	int cnt = 1; 
	while (cnt < n) 
	{ 
		cnt *= 2; 
	} 
}

在这里插入图片描述
这里可能会有人疑惑，x解出来不是以2为底n的对数吗？怎么省略了底数2了呢？

当n接近无穷打时，底数的大小对结果影响不大。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表示为 log n
不同书籍的表示方式不同，以上写法差别不大，我们建议使用log n

所以该程序的时间复杂度为O(logN)

最后来看一个递归算法的时间复杂度：

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

在这里插入图片描述
所以该程序时间复杂度为：O(N)

以上就是常见的时间复杂度的计算下面来说说影响算法效率的第二个因素，空间复杂度：

4，空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大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; 
	} 
}

我们只需关注哪里创建了变量就好了，看到程序只创建了一个exchang变量，只创建了一次，所以空间复杂度为O(1)

再来看一个空间复杂度为O(N)的情况

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

这个程序在计算是将复杂度的时候见到过，当时只关注时间复杂度而现在我们关注的是空间复杂度，空间复杂度怎么计算呢？

将到空间我们就关注函数在运行时候显式申请的额外空间来确定空间复杂度，函数调用了N次，就会创建N个函数栈帧所以空间复杂度为O(N)。

最后再用一张图给出各个时间复杂度的曲线，复杂度越简单曲线越平缓操作次数越小，斜率越小。
在这里插入图片描述

在这里插入图片描述

最后我们再来看看前面我们提出的那道算法题：
轮转数组
我们给出优化后的代码：

//逆置函数
 void revers(int* nums,int left,int right)
 {
    while(left<right)
    {
        int tmp=0;
        tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        left++;
        right--;
    }

 }

void rotate(int* nums, int numsSize, int k) {

    //注意要处理k超过数组大小的情况
    k=k%numsSize;
    revers(nums,0,numsSize-k-1);
    revers(nums,numsSize-k,numsSize-1);
    revers(nums,0,numsSize-1);
}

我们给出代码分析：
在这里插入图片描述
该程序的时间复杂度为O(N)空间复杂度为O(1)，前面给出的算法时间复杂度为O(N^2)
从O(N^2)变成了O(N)就完成算法的优化。

以上就是本章的全部内容啦！
最后感谢能够看到这里的读者，如果我的文章能够帮到你那我甚是荣幸，文章有任何问题都欢迎指出！制作不易还望给一个免费的三连，你们的支持就是我最大的动力！
在这里插入图片描述

【数据结构】算法的复杂度