算法与数据结构（一）

一、时间复杂度

一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体来说，这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”。
选择排序、冒泡排序的时间复杂度为$O(N^2)$，额外空间复杂度为$O(1)$
c++实现的选择排序算法：

	//创建一个数组int arr[] = {1, 6, 3, 6, 8, 6, 4};//判断数组是否为空或者只有一个数组if (arr == NULL || sizeof(arr) < 2){return;}//开始选择排序for (int i = 0; i < sizeof(arr)/sizeof(arr[0]) - 1; i++){// 暂存最小的数据下标索引int min = i;//从第一个操作数开始筛选for (int j = i + 1; j < sizeof(arr) / sizeof(arr[0]); j++){if (arr[min] > arr[j]){int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}}}for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){cout << arr[i] << " ";}cout << endl;

冒泡排序：

	//创建数组int arr[] = { 2, 3, 5, 1, 3, 4, 5 };//判断数组是否为空或者只有一个数组if (arr == NULL || sizeof(arr) < 2){return;}//开始冒泡排序for (int i = sizeof(arr) / sizeof(arr[0]) - 1; i > 0; i--){for (int j = 0; j < i; j++){if (arr[j] > arr[j+1]){arr[i] = arr[j] ^ arr[i];arr[j] = arr[j] ^ arr[i];arr[i] = arr[j] ^ arr[i];}}}//输出排序后的数组for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){cout << arr[i] << " ";}cout << endl;

以上两种排序算法不管数组内部是什么情况，都需要执行固定的操作，但是插入排序要考虑数组内部的情况，在最好情况下（数组刚好按照想要排序的顺序排列），其时间复杂度为$O(N)$,，最差情况下(（数组刚好与想要排序的顺序相反）)，其时间复杂度为$O(N^2)$，在时间复杂度的考量上，以最差情况为标准，所以为$O(N^2)$，其c++实现：

//创建数组int arr[] = { 2, 2, 3, 1, 3, 1, 5, 6 };//如果数组为空或者只有一个数据时，跳过if (arr == NULL || sizeof(arr) < 2){return;}//外侧循环for (int i = 1; i < sizeof(arr)/ sizeof(arr[0]); i++){//内侧循环for (int j = i; j > 0; j--){//如果内测循环指针指向的数据比左侧数据小，则进行交换if (arr[j - 1] > arr[j]){int tem = arr[j];arr[j] = arr[j - 1];arr[j - 1] = tem;}}}//输出排序后的数组for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){cout << arr[i] << " ";}cout << endl;

二、力扣刷题：

有一系列数组，只有一个数字出现了奇数次，其余的数出现了偶数次，求出出现奇数次的数据，要求算法的时间复杂度为O(N)：

void test10()
{//创建一系列数组int arr[] = { 2, 2, 3, 1, 3, 1, 5 };int eor = 0;for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++){//使用初始变量0逐个异或数组中的每一个元素eor ^= arr[i];}cout << "出现奇数次的数字为：  " << eor << endl;
}

在异或操作中，0异或0就会出现0的结果，1异或1就等于0，1异或0就等于1。异或操作也可以看成二进制的无进位相加。所以当数组中出现偶数个相同的元素时，其结果会是0，由于异或操作有交换性质，当0异或一个奇数个元素时，其结果就是该数。
有一系列数组，有两个数字出现了奇数次，且这两个奇数次的元素不相等，其余的数出现了偶数次，求出出现奇数次的数据，要求算法的时间复杂度为O(N)：

	//创建一系列数组int arr[] = { 2, 2, 3, 1, 3, 1, 5, 6 };int eor = 0;int eor1 = 0;for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){//最终得出a异或b的结果eor ^= arr[i];}//提取eor二进制中的最后一个1int RightOne = eor & (~eor + 1);for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){if ((RightOne & arr[i]) == 0){//得出两个奇数次数数字之一eor1 ^= arr[i];}}cout << eor1 << (eor1 ^ eor) << endl;

假设两个出现奇数次的数分别为a，b。这道算法题与之前的算法题有相同之处，但是第一次遍历异或的结果是a异或b。我们只需要知道a或者b再异或一下a异或b的结果就可以得到另一个数字的结果。我们可以这样假设，因为a与b不相等，a异或b的结果也就肯定不为0。在二进制中，a异或b的结果肯定某一位会出现1。假设a异或b的结果为1010。在这里我们只看其中的一位，也就是第二位。a异或b在第二位中出现1,反映到a,b上我们可以知道。a或者b肯定在第二位为1，在这里我们假设a在第二位为1。我们只需要再次迭代一下数组中的元素，可以通过与的操作将第二位上不是1的数进行过滤，如果第二位上是1，我们只需要进行一个异或操作即可，因为除了a之外，其余第二位上是1的数都是偶数，所以最后异或出来的数就是a，再用a异或（a异或b）的结果可以得出b。