信阳建设企业网站,网站做友链盈利,怎样才能做好网站优化,如何优化网站标题目录
一、时间复杂度BigO
大O的渐进表示法#xff1a;
例题一#xff1a;
例题2#xff1a;
例题3#xff1a;冒泡排序的时间复杂度
例题4#xff1a;二分查找的时间复杂度
书写对数的讲究#xff1a;
例题5#xff1a; 实例6#xff1a;
利用时间复杂度解决编…目录
一、时间复杂度BigO
大O的渐进表示法
例题一
例题2
例题3冒泡排序的时间复杂度
例题4二分查找的时间复杂度
书写对数的讲究
例题5 实例6
利用时间复杂度解决编程题
编辑思路一
思路二
源码
思路三
回顾位操作符
二、空间复杂度详解
概念
例题1冒泡排序的空间复杂度是多少
例题2单路递归
例题3
解析
例题4硬菜双路递归
利用空间复杂度解决编程题
思路一
代码
思路二
代码
思路三
代码 一、时间复杂度BigO
首先我们不能以机器运行算法的时间来评判一个算法的时间复杂度因为即使是相同的算法在不同机器上机器的个体差异性运行时间都可能不尽相同因此我们采用
【大O表示法】——算法的渐进复杂度TnOfn。
就是算执行次数 首先解读这个公式fn表示代码执行的次数O表示正比例关系而Tn就表示算法的渐进复杂度就是当一个问题量级增加的时候算法运行时间增长的一个趋势。
即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
大O的渐进表示法
实际中我们计算时间复杂度时我们其实不一定要计算精确的执行次数而只需要大概执行次数。
大O渐进表示法的规则
用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1则取出与这个项相乘的常数使其前面的系数是1得到的就是大O渐进表达式。用最坏的情况去考虑计算时间复杂度 。
例题一 我们可以计算出count语句被执行多少次从而算出该算法的时间复杂度。
不难计算出这样一个数学函数表达式 例题2 strchr是一个库函数用来计算某个特定字符在字符串中的位置实现方法就是循环遍历。
这样时间复杂度一共有三种情况
1、最幸运遍历一次就找到
2、最不幸一直遍历到最后才找到
3、取平均值遍历到中间才找到
以上三种情况到底哪种是符合时间复杂度的呢答案是最坏情况也就是ON
下面是更复杂的一些计算时间复杂度的例题。
一些更复杂的代码我们不能只看代码去计算时间复杂度我们要看重代码的思想是什么底层逻辑
例题3冒泡排序的时间复杂度 我们首先要计算最坏的情况那就是数据本来从小到大顺序排列而要求从大到小排列所以全部都需要重新排第一次n-1,第二次n-2,第三次n-3以此类推直到最后的1这就是一个等差数列求和公差是1计算得出最高次项是N^2所以最终O(N)N^2。
那最好的情况是不是O(1)呢
答案不是因为如果已经排好序我们还需要判断是否有序判断是否有序就需要时间所以最好的情况就是O(N)
例题4二分查找的时间复杂度 二分查找的最坏情况就是我们要查找的数据在边界查找区间缩放只剩下一个值时就是最坏。最坏情况下查找了多少次除了多少次2就查找了多少次。
假设区间个数是N/2/2/2/2一直除到最后区间只剩下一个值。 书写对数的讲究
由于对数在文本中不好写支持一些展示公式编辑器才方便所以时间复杂度简写成logN,只有log以2为底N的对数才可以简写成logN,其他都要写出来。
暴力搜索O(N)和二分查找O(logN)量级的天差地别 例题5
计算阶乘递归的时间复杂度 注意计算递归的时间复杂度主要看函数被调用的次数然后再看函数内部的时间复杂度。
递归算法的时间复杂度是多次调用的累加。
我们发现上述代码的递归函数调用了N1次而每次函数的内部都是O(1),所以最终的时间复杂度就是O(N).相当于N1个1的时间复杂度 实例6 跟上面的代码区别是这是一个双路递归上面是单路递归 上图是双路递归的调用次数不难发现规律是以2^n为数量级进行递增然后再进行等比数列求和最终计算出来的数量级就是2^n,所以O(N)2^N 最终的三角形是右下角缺失一块但并不影响我们的数量级。
但是2^n的时间复杂度算的非常慢因为CPU能接受是以亿为单位但是2^n很快就到达CPU的顶峰了。
所以用递归求解斐波那契数列只有理论上可行
利用时间复杂度解决编程题
思路一
排序遍历下一个数不等于下一个数据1这个下一个数就是消失的数字
时间复杂度O(logN*N)用快排qsort的前提下
思路二
用0~N等差数列求和公式计算结果减去数组中的值结果就是消失的数字
时间复杂度O(N)
源码
int main()
{int arr[] { 0,1,3 };int sum 2 * 3;//求和直接用等差数列的公式计算for (int i0;i3;i){sum - arr[i];}printf(%d\n, sum);return 0;
}
思路三
单身狗思路异或两个成对出现的数字中出现了一个单独的数字用异或去解决
int main()
{int arr[] { 1,3,4 };int ret 0;for (int i1;i4;i){ret ^ i;}for (int i0;i3;i){ret ^ arr[i];}printf(%d\n, ret);return 0;
}
回顾位操作符
^——异或操作符——对应的二进制相同返回0对应的二进制位不同就返回1注意两个相同的数字异或结果是0任何一个数据与0异或结果就是它本身并且异或操作符满足交换律
——按位与操作符——只要有0结果就是0
|——按位或操作符——只要有1结果就是1
二、空间复杂度详解
概念
空间复杂度也是一个数学表达式是对一个算法在运行过程中额外临时占用存储空间大小的量度
空间复杂度不是程序占用了多少字节的空间而是计算的是变量的个数也采用大O渐进表示法。
注意函数运行时所需要的栈空间存储参数、局部变量、一些寄存器信息等在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。
例题1冒泡排序的空间复杂度是多少 首先参数传过来的数组不算入空间复杂度如果我们是为了让这个数组排序额外创建了一个数组这样的数组才算入空间复杂度。
这样计算发现只有endexchangei是我们额外创建的变量所以一共是3个即空间复杂度是O(1)注意O(1)不代表空间空间复杂度是1个而是常数个。
例题2单路递归 不难看出为了解决题目代码额外创建了一个数组所以最后的空间复杂度就是O(N)
例题3 解析
假设有N层递归每次递归需要调用一次函数而调用函数需要创立栈帧每调用一次函数就需要创建一次栈帧而创建一次栈帧需要常数个的空间注意栈帧在函数使用完毕后是会销毁的但是空间复杂度计算的是最大的空间占用所以只有当递归结束时才计算整体的栈帧。所以最终的空间复杂度就是ON。
例题4硬菜双路递归 我们首先要明确这样一个原则时间是累计的一去不复返空间是可以重复利用的。
创建和销毁函数栈帧的潜规则
我们先明白这样一个道理当一个函数调用完毕后第一个函数创建的栈帧的空间就会返回操作系统接着继续再调用另外一个函数第二个函数创建后需要的栈帧空间就是上一个函数的空间是一模一样的下面的例子为证a和b的地址是一样的。 有了上面的基础后我们还要知道双路递归函数的调用顺序下图为例。 当我们一路递归调用完毕函数创建的栈帧销毁接下来另一个新的函数就会继续用这个空间重复利用所以最多额外占用N个空间即空间复杂度是O(N)。
利用空间复杂度解决编程题 思路一
先将最后一个数取出来然后将数组里前面的元素向右移动一位这样就算是右旋一次接着进行循环一共循环k次。
这样的空间复杂度O(1)时间复杂度O(N^2)因为考虑最差情况不能是KN因为K是一个变量情况有好有坏算复杂度直接取最差的情况。
代码
int main()
{int arr[] { 1,2,3,4,5,6,7 };int sz sizeof(arr) / sizeof(arr[0]);int k 0;scanf(%d, k);for (int i0;ik;i){int tmp arr[sz - 1];for (int j0;jsz-1;j){arr[sz - 1 - j] arr[sz - 2 - j];}arr[0] tmp;}for (int i0;isz;i){printf(%d , arr[i]);}return 0;
}
思路二
用空间换时间再开辟一个数组直接将数据拷贝到新的数组然后再整体拷贝到原来的数组
时间复杂度就是O(N),因为我们额外开辟了一个数组空间所以我们的空间复杂度就是O(N)
代码
int main()
{int arr[] { 1,2,3,4,5,6,7 };int* tmp (int*)malloc(sizeof(arr) * sizeof(arr[0]));if (tmp NULL){perror(malloc);exit(-1);}int k 0;int sz sizeof(arr) / sizeof(arr[0]);scanf(%d, k);//注意memcpy最后一个参数以字节为单位memcpy(tmp, arr sz - k % sz, k % sz * sizeof(arr[0]));memcpy(tmp k % sz, arr, (sz - k % sz) * sizeof(arr[0]));memcpy(arr, tmp, sz * sizeof(arr[0]));for (int i0;isz;i){printf(%d , arr[i]);}free(tmp);tmp NULL;return 0;
}
思路三
三步翻转法 空间复杂度是O(1),时间复杂度是O(N)这就是最优解法
不容易想到需要积累
代码
void reverse(int* left, int* right)
{while (left right){/*int* tmp left;left right;right tmp;*///将两个地址交换int tmp *left;*left *right;*right tmp;left;right--;}
}int main()
{int arr[] { 1,2,3,4,5,6,7 };int sz sizeof(arr) / sizeof(arr[0]);int k 0;scanf(%d, k);reverse(arr, arrsz-k-1);reverse(arr sz-k, arr sz - 1);reverse(arr, arr sz - 1);for (int i0;isz;i){printf(%d , arr[i]);}return 0;
}
