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

复杂度、对数器、二分法与异或运算"/>

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

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

文章目录

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

😊点此到文末惊喜↩︎

算法的评估

时间复杂度

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

空间复杂度

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

对数器

1. 测试方法
   • 实现要测试的方法A
   • 实现容易写出的方法B（不对时空复杂度做要求）
   • 实现一个随机样本产生器
   • 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
   • 比较结果不一样的随机样本，并针对该样本进行方法A的优化
   • 当样本数量很多时比对测试依然正确，基本确定方法a已经正确。
2. 对数器的实现

//函数名：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");
}

二分法

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

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都指向同一个结果
}

异或运算

1. 异或
   • 基本运算：忽略进位的相加，如110 ^ 011 = 101，无进位是指每一个位相加都不进位
   • 常见运算
     • 0 ^ N = N
     • N ^ N = 0：偶数个相同的数异或为0
   • 规律：异或运算满足交换律和结合律，相同数列异或结果与顺序无关
2. 原地快速交换
   • a 和 b不能是同一块内存，不同地址但是值相同也可以

   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
   

3. 一个数组中只有一种数出现了奇数次，其他数出现了偶数次，如何找到并打印这种数
   • 异或操作可以将出现偶数次的异或为0，最终只保留出现奇数次的值

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

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

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));}
}

🚩点此跳转到首行↩︎

参考博客

1. 对数器
2. 单调队列
3. 快速链表quicklist
4. 《深入理解计算机系统》
5. 侯捷C++全系列视频
6. 待定引用
7. 待定引用
8. 待定引用