【左程云算法全讲】认识复杂度、对数器、二分法与异或运算

本文主要是介绍【左程云算法全讲】认识复杂度、对数器、二分法与异或运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

系列综述：
💞目的：本系列是个人整理为了秋招面试的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于左程云算法课程进行的，每个知识点的修正和深入主要参考各平台大佬的文章，其中也可能含有少量的个人实验自证。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈【C++】秋招&实习面经汇总篇

文章目录

- - 算法的评估
  - - 时间复杂度
    - 空间复杂度
  - 对数器
  - 二分法
  - 异或运算
- 参考博客

😊点此到文末惊喜↩︎

算法的评估

时间复杂度

作用：衡量算法流程复杂度的一种指标，指标只与数据量有关，与优化无关
常数时间复杂度：操作时间和数据量无关
计算方法
- 将流程拆分成一个个的基本动作，保证每个动作都是常数项
- 计算基本动作和数据量N的最差关系，举最差的例子去测试
- 记为：O(忽略系数的最高阶项数)
常数阶时间复杂度的估计可以通过大量的随机样本测试获得
问题的最优解
- 一般先满足尽量低的时间复杂度，再满足空间复杂度尽量低
时间复杂度排行：常对幂指阶

空间复杂度

本质：与功能要求无关，是辅助算法流程实现的空间复杂度

对数器

作用：通过生成随机序列输入，自动测试自定义程序和正确程序(通常是简单不易出错的程序)的结果差异，从而测试程序的正确性
测试方法
- 实现要测试的方法A
- 实现容易写出的方法B（不对时空复杂度做要求）
- 实现一个随机样本产生器
- 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
- 比较结果不一样的随机样本，并针对该样本进行方法A的优化
- 当样本数量很多时比对测试依然正确，基本确定方法a已经正确。
对数器的实现

//函数名：generateRandomVector
//函数功能描述：随机数组（样本）生成器
//函数参数：size    生成数组最大尺寸
//         	value   数组每个元素的最大值
//返回值：  vector<int> 生成的随机序列数组
//for test
vector<int> generateRandomVector(int size, int value) {//time 函数返回从 1970 年 1 月 1 日午夜开始到现在逝去的秒数，因此每次运行程序时，它都将提供不同的种子值。srand((int)time(NULL));//为随机数生成器产生随机种子//分配随机大小的数组，产生随机数的范围公式number = (rand()%(maxValue - minValue +1)) + minValue;vector<int> result(rand() % (size + 1));for (int i = 0; i < result.size(); i++) {result[i] = rand() % (value + 1);}return result;
}//大样本测试
//函数名：main
//函数功能描述：大样本测试
//函数参数： size    生成数组最大尺寸
//         value   数组每个元素的最大值
//返回值：  vector<int> 生成的数组
//for test
int main(){auto test_time = 50000;//测试次数，设置比较大，排除特殊情况auto size = 10;//生成数组最大尺寸auto value = 30;//生成数组每个元素的最大值auto if_accept = true;//方法是否正确标志位for(auto i = 0; i < test_time; i++) {//拷贝初始化，生成新的数组向量vector<int> nums(generateRandomVector(size, value));//生成两个临时数组拷贝vector<int> nums1(nums);vector<int> nums2(nums);//绝对正确方法sort(nums1.begin(), nums1.end());//自己写的方法，想要测试的算法Solution::reversePairs(nums2);//判断两个向量是否相同，vector类已经重载了比较运算符，不用自己实现，不相同说明算法不正确if(nums1 != nums2) {if_accept = false;//输出结果不相等的原始向量for(auto c: nums) {cout << c << " ";}break;}	}//输出结果cout << (if_accept ? "nice!\n" : "false!\n");
}

二分法

默认 $O (l o g N)$ 为 $O(log_2N)$
二分法的作用：
- 在一个有序数组中，找某个数是否存在
- 在一个有序数组中，找>=某个数最左侧的位置
- 在一个有序数组中，找<=某个数最右侧的位置
- 局部最小值问题，如先下降后上升，找最小（可以不严格单调有序）
$N * 2 + 1$ 可以等价替换为 $(N << 1) ∣1$
基本二分算法

bool BinarySearch(vector<int> vec, int target){if (vec.size() == 0) return false;int L = 0;int R = vec.size()-1;int mid = 0;while (L < R) {mid = L + ((R-L)>>1);if (vec[mid] == target) {return true;} else if(vec[mid] > target) {R = mid - 1;} else {L = mid + 1;}}return vec[L] == target;	// 最后L和R都指向同一个结果
}

异或运算

异或
- 基本运算：忽略进位的相加，如110 ^ 011 = 101，无进位是指每一个位相加都不进位
- 常见运算
  - 0 ^ N = N
  - N ^ N = 0：偶数个相同的数异或为0
- 规律：异或运算满足交换律和结合律，相同数列异或结果与顺序无关
原地快速交换
- a 和 b不能是同一块内存，不同地址但是值相同也可以
```
a = a ^ b;
b = a ^ b;
a = a ^ b;
```
一个数组中只有一种数出现了奇数次，其他数出现了偶数次，如何找到并打印这种数
- 异或操作可以将出现偶数次的异或为0，最终只保留出现奇数次的值

void PrintOddTimes(vector<int> vec) {int eor = 0;for (int i = 0; i < vec.size(); ++i) {eor ^= vec[i];	// 出现偶数的都会被异或为0}cout << eor << endl;
}

提取值类型中最右的1：N & ((~N) + 1)
一个数组中有两种数出现了奇数次，其他数都出现了偶数次，如何打印这两个数

public class no_04_题目4 {public static void main(String[] args) {//注意：因为通过eor最右侧的1为特征，a和b在此位上必不相同，故可以用这位来划分区间int eor  = 0;int[] arr = {1,1,1,2,2,2,4,4,5,5,5,5,6,6,8,8,};//1.数组所有数与其异或一次for (int i:arr)eor ^= i;	// 最终eor = a ^ b;// 其中a和b为目标两个数// 2.提取eor最右侧的1【也就是a与b的划分位】，因为a != b，所以异或必不为0int rightOne = eor & (~eor + 1);//3.准备变量onlyOne与数组中在rightOne位上是1的异或，得到a与b其中一个int onlyOne = 0;for (int i:arr)if ((rightOne & i) != 0)onlyOne ^= i;//4.onlyOne 就是 其中一个，onlyOne ^ eor是另一个System.out.println(onlyOne + "   " + (onlyOne ^ eor));}
}