食品餐饮网站建设,wordpress 友情链接 插件,如何网站专题策划,给wordpress创建ftp一、时间复杂度
一个操作如果和样本的数据量没有关系#xff0c;每次都是固定时间内完成的操作#xff0c;叫做常数操作。 时间复杂度为一个算法流程中#xff0c;常数操作数量的一个指标。常用O(读作big O)来表示。具体来说#xff0c;这个算法流程中#xff0c;发生了多…一、时间复杂度
一个操作如果和样本的数据量没有关系每次都是固定时间内完成的操作叫做常数操作。 时间复杂度为一个算法流程中常数操作数量的一个指标。常用O(读作big O)来表示。具体来说这个算法流程中发生了多少常数操作进而总结出常数操作数量的表达式。 评价一个算法流程的好坏先看时间复杂度的指标然后再分析不同数据样本下的实际运行时间也就是“常数项时间”。 选择排序、冒泡排序的时间复杂度为O(N2)O(N^2)O(N2)额外空间复杂度为O(1)O(1)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[j1]){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)O(N),最差情况下(数组刚好与想要排序的顺序相反)其时间复杂度为O(N2)O(N^2)O(N2)在时间复杂度的考量上以最差情况为标准所以为O(N2)O(N^2)O(N2)其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就等于01异或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;假设两个出现奇数次的数分别为ab。这道算法题与之前的算法题有相同之处但是第一次遍历异或的结果是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。
