网站备案必须要幕布吗,2023最近的新闻大事10条,团购做的好的网站有哪些,建设银行网站 查余额查询【一周刷爆LeetCode#xff0c;算法大神左神#xff08;左程云#xff09;耗时100天打造算法与数据结构基础到高级全家桶教程#xff0c;直击BTAJ等一线大厂必问算法面试题真题详解#xff08;马士兵#xff09;】https://www.bilibili.com/video/BV13g41157hK?p3v…【一周刷爆LeetCode算法大神左神左程云耗时100天打造算法与数据结构基础到高级全家桶教程直击BTAJ等一线大厂必问算法面试题真题详解马士兵】https://www.bilibili.com/video/BV13g41157hK?p3vd_source04ee94ad3f2168d7d5252c857a2bf358
目录
1、认识复杂度和简单排序算法
1.1 常数时间操作 时间复杂度
1.2 基础排序算法
1.2.1 选择排序
1.2.2 冒泡排序
补充异或运算
1.2.3 插入排序
1.3 二分查找
1.4 对数器
1.5 master公式 笔记
1、认识复杂度和简单排序算法
1.1 常数时间操作 时间复杂度
常数时间的操作与数据量无关的操作每次都是固定时间完成
数组查数是链表不是
数组是记录在案的有目录可供直接取用与数据量无关而链表没有记录在案的目录只能一个个查找因此与数据量有关
时间复杂度忽略最低项后只要最高项且忽略掉系数。
忽略系数的原因当数据量N足够大的时候它的系数对它造不成影响。
评估一个算法流程的好坏先比较时间复杂度指标当指标相同时再实际运行去测哪个算法更好。 1.2 基础排序算法
选择排序冒泡排序都是O(N^2)实现方式不同但本质没区别
1.2.1 选择排序
选择排序从i0开始每加一次从arr[i]开始遍历到arr[n-1]并把最小值交换到arr[i]上。
遍历0到n-1、1到n-1、2到n-1等等
1.2.2 冒泡排序 冒泡排序两个位置间比较慢慢把数字升序或降序
从i0开始如果arr[i]大于arr[i1]它俩交换。这个方法每次遍历后右边的数都是前面最大的。
遍历0到n-1、0到n-2、0到n-3等等 补充异或运算
可以理解为无进位相加二进制中0^001^00^111^10
N进制中N^00^NNN^N0
异或运算满足交换律、结合律
//使用前提a和b各自指向的内存空间必须不同a和b的数值可以一样但a的地址不能等于b的地址否则异或运算就会把a和b都抹为0int a 某个值;int b 某个值;aa^b; //aa^b, bbba^b; //aa^b, ba^b^ba^(b^b)a^0aaa^b; //aa^b^ab, ba
【异或运算】例题
1136. 只出现一次的数字 - 力扣LeetCode
描述只有一个数字出现奇数次找出它。
思路用“异或 a^a0”消除所有偶数次的数。
2描述有两个数a和b都出现奇数次找出它们两个。
思路先边遍历边异或得到targetsa^b再将targets再和整个数组异或一遍得到其中一个奇数次的数a。然后a和targets再异或得到b。
1.2.3 插入排序
插入排序简而言之就像打扑克按数字顺序整理好手中的牌抽新牌后插入到对应位置上。
由于在数组中插入一个位置时后面的数都要整体往后移所以干脆在比较的同时就交换了位置因此看着像冒泡排序。
从int i1开始因为再i0上已经做到了有序。
数据状况不同会导致算法流程的时间复杂度不同。
时间复杂度是按最差情况估计算法表现。
1.3 二分查找
时间复杂度O(logN)
无论数组是否有序都可以二分
例题
1在有序数组中找某数是否存在
2在有序数组中找≥某数的最左侧位置
3在无序数组中找局部最小值问题 1.4 对数器
原理利用随机样本产生器去测试方法a和方法b检查二者的输出和性能。修改样本大小和随机程度之后多测几次。
方法a想测的方法
方法b好实现但性能不太好的方法 java实现
Math.random()是等概率返回[0,1)区间内的一个小数。
而(int)Math.random() * N则是等概率返回[0, N-1]区间内的一个整数。
// 数组长度随机int[] arr new int[ (maxSize1) * (int)Math.random() ];// 数组数值随机使用相减来概率得到负数for(int i0; iarr.length; i){arr[i] (int) ( (maxValue1) * Math.random() - (int) ( maxValue * Math.random() );}
然后创建两个空数组分别存储调用方法a和b之后的结果比较结果是否相同。 1.5 master公式
master公式T(N) a*T(N/b) O(N^d)
log(b,a) d复杂度为O( N^log(b,a) )
log(b,a) d复杂度为O( N^d * logN )
log(b,a) d复杂度为O( N^d )
