初阶数据结构--时间复杂度和空间复杂度_初等变换的时间复杂度

1.算法效率

绝大多数事物都有一个好坏的评判标准，那么程序代码也不例外。算法效率就是它的评判标准，算法效率又主要体现在两个方面：1.时间复杂度（体现在算法运行速度）2.空间复杂度（体现在存储所需空间），但现在随着高科技的发展，内存越来越大，故我们对空间复杂度的重视程度要远不及时间复杂度。

2.空间复杂度

因为用的比较少，我就简单说两句：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 ，我们一般算变量的个数来代表它，与时间复杂度相似，我们也会用大o渐进表示法。

3.时间复杂度

算法中的基本操作的执行次数，为算法的时间复杂度量度，为了简洁的表示时间复杂度，我们去掉对结果影响不大的项，一般取最高阶项。（使用大o渐进表示法来表示）

我们在计算执行次数时有个原则，就是取最坏情况运行次数（例如，最好运行一次，最坏n次，那空间复杂度就是o（n）

下面，我介绍一种在程序中最直观体现算法快慢的方式--计算时间：

#include<stdio.h>
#include<time.h>
int main()
{
	int i = 1,n=0;
	scanf("%d", &n);
	clock_t begin = clock();
	for (i = 0; i < n; i++)
	{
		printf("计算时间\n");
	}
	clock_t end = clock();
	printf("%d\n", (end - begin) / CLK_TCK);//CLK_TCK意思是每秒打点数，最终结果单位为秒
	return 0;
}

运行结果：

在某些算法思想中空间复杂度往往会很高（例如递归），但常常代码较为简洁。

下面我们介绍一种常被忽略的改进算法的方法--异或

异或^:作为双目运算符，将两个操作数二进制上按位进行相同为0，相异为1的操作。

关于异或，我们使用的很少，因为它设计二进制按位运算，不是很直观，但上帝给他开了一扇窗，他的一个特点就是：两个相同数互相异或会消失，这一特性在某些地方有奇效。

例如在某大厂的笔试题中：请设计一个函数让两个数值交换（不定义第三个变量）

对于交换数字，我们再熟悉不过了，但不定义第三变量，却难倒一大批人，这个时候我们今天的主角——异或就闪亮登场了。

void exchang(int* a, int* b)
{
	*a = *a^*b;
	*b = *a^*b;//这个时候相当于两个b与一个a相异或，故只剩下一个a，达成对b赋a值
	*a = *a^*b;//这个时候相当于两个a与一个b相异或，故只剩下一个b，达成对a赋b值
}

再举个leetcode原题260. 只出现一次的数字 IIIhttps://leetcode-cn.com/problems/single-number-iii/

int* singleNumber(int* nums, int numsSize, int* returnSize){
	int x = 0, y = 0;//用来放最后结果
	int ret = 0;
	int i = 0;
	for (i = 0; i < numsSize; i++)
		ret ^= nums[i];//找到数组两个单独数相异结果
	//这两个数不同相异就必定有一位上是1，我们接下来随机找一位。
	int j = 0;
	for (j = 0; j < 32;j++)
	{
		if ((1<<j)&ret)//这里我们利用1左移j位，与ret按位相与==同为一才为1
			break;
	}
	//现在我们思考：如果异或结果有1那么就说明在这一位上，这两个数一个为1，一个为0
	//我们可以把数分为两组，这两个单数就被分在不同组
	//那么分别在这两个组中在异或，就找出了这两个值
	for (int k = 0; k < numsSize; k++)
	{
		if (nums[k] & (1 << j))//第一组
		{
			x ^= nums[k];
		}
		else
		{
			y ^= nums[k];
		}
	}
	int* arr = (int*)malloc(sizeof(int)* 2);
	arr[0] = x;
	arr[1] = y;
	*returnSize = 2;
	return arr;
}

 这个类型题如果不用这种方法，时间复杂度比较大，最起码这种方法只有o（n）复杂度，肯定不大。

希望对大家有所帮助，这是我数据结构系列第一讲。

如有收获，给个点赞吧。