仙居网站开发,天元建设集团有限公司欠款,网站的需求分析,杭州市住建局官网时间复杂度 在算法和数据结构中#xff0c;有许多时间复杂度比 O(1) 更差的情况。以下是一些常见的时间复杂度#xff0c;按照从最优到最差的顺序排列#xff1a; O(1)#xff1a; 常数时间复杂度#xff0c;操作的运行时间与输入规模无关#xff0c;是最理想的情况。 O…时间复杂度 在算法和数据结构中有许多时间复杂度比 O(1) 更差的情况。以下是一些常见的时间复杂度按照从最优到最差的顺序排列 O(1) 常数时间复杂度操作的运行时间与输入规模无关是最理想的情况。 O(log n) 对数时间复杂度常见于分治算法和二分搜索等。 O(n) 线性时间复杂度操作的运行时间与输入规模成正比。 O(n log n) 线性对数时间复杂度常见于一些高效的排序算法如快速排序和归并排序。 O(n^2) 平方时间复杂度常见于一些简单的嵌套循环算法-选择,冒泡,插入 O(n^k) 多项式时间复杂度其中 k 是常数通常表示更高次幂的多项式时间复杂度。 O(2^n) 指数时间复杂度常见于一些指数级增长的问题如穷举搜索。 O(n!) 阶乘时间复杂度通常表示在排列组合问题中的情况。时间复杂度表示形式
对应的选泡插排序时间复杂度都是O(n^2)空间复杂度是O(1)
冒泡排序
时间复杂度:有两个for循环,第一个for循环是每个元素都要与其他的元素比较一遍,所以如果有N个元素,那么最外层的for循环的时间复杂度就是O(N),然后每一次外层的for循环,都会在内部的for循环中两两进行比较,又是O(N),因为是for循环嵌套.所以最后的时间复杂度就是O(n^2),空间复杂度的话-一般来说,除了用户要求的内存空间之外,额外申请的新的空间,则就是空间复杂度,这里用了一个temp临时变量来存储数据,所以该空间复杂度是O(1) public class 冒泡排序 {public static void main(String[] args) {int arr[] {1, 2, 4, 5, 3, 6, 8, 7};//第一层for循环代表的是轮数,从第一个数开始,每个数都要和其他的数进行比较,所以有多少数,总共就有多少轮for (int i 0; i arr.length; i) {//第二层for循环代表的是如果是逆序则换位置,因为有j1 为了防止下标越界,所以在第二层for循环的时候,在减1for (int j0;jarr.length-i-1;j){if (arr[j]arr[j1]){int tepm arr[j];arr[j]arr[j1];arr[j1]tepm;}}}for (int i : arr) {System.out.print(i);}}}选择排序
package 算法;
public class 选择排序 {//先在[0~n-1]下标范围内找到最小值放到0位置上//再在[1~n-1]下标范围内找到最小值放到1位置上//依次如此操作直到最后一个最小值【最大值】放在n-1位置上完成排序操作public static void main(String[] args) {int arr[] {2, 1, 4, 5, 3, 6, 8, 7};for (int i 0; i arr.length-1; i) {int minIndexi;//最小值的下标设为第一个数的下标索引//然后第一个数和第二个数开始进行比较,看哪个数是最小的, 如果哪个是最小的,则记住最小值的下标,然后两个数进行交换,直到和其他的元素都比较完后,在走下一个数(也就是第一层for循环)for (int ji1;jarr.length;j){minIndexarr[j]arr[minIndex]?j:minIndex;}//交换位置int temp arr[i];arr[i]arr[minIndex];arr[minIndex]temp;}for (int i : arr) {System.out.print(i);}}}插入排序
public class 插入排序 {//思路就是:默认第一个数的位置已经确定.从第二个位置开始,如果比第一个位置的数小,则换位置,//第三个数再和第二个数比较,如果小于第二个数,则换位置,否则不换,然后继续和第一个位置上的数进行比较,小于则换位置.否则不换, 以此类推public static void main(String[] args) {int arr[] {2, 1, 4, 5, 3, 6, 8, 7};for (int i 1; i arr.length; i) {for(int ji-1;j0arr[j]arr[j1];j--){int temparr[j];arr[j]arr[j1];arr[j1]temp;}}for (int i : arr) {System.out.print(i);}}
}
运算
异或 (^) 不同为1,相同为0 有两个特性: a^0a a^a0 例题1: a1 ,b2 在不使用第三个临时变量来完成两个数的交换,这里就可以用到异或方法
package 算法;/*** author : gaoPengShuai* date : 2023/11/21 21:21* modyified By :*/
public class 异或 {public static void main(String[] args) {int a 1;int b2;System.out.println(交换之前a的值是:a b的值是:b);//在不使用第三个变量来完成两个数的交换aa^b;ba^b;aa^b;System.out.println(交换之后a的值是:a b的值是:b);}
}运行结果:交换之前a的值是:1 b的值是:2
交换之后a的值是:2 b的值是:1Process finished with exit code 0
例题2:
在一个数组中,一个数出现了奇数次,其他的数出现了偶数次.找到该出现奇数次的数 public static void test1(){//在一个数组中,一个数出现了奇数次,其他的数出现了偶数次.找到该出现奇数次的数int arr[] {1,2,3,2,3,3,1};int temp 0;for (int i : arr) {temp^i;}System.out.println(temp);}
注意:这两个例题就用到了,a^a0 然后0^bb的方法,直接将两个数进行交换,但是值得注意的是,a和b值可以相同,但是内存地址不能相同,因为自己异或自己的结果是0,会将之前的值覆盖为0
例题3:
找到一个数转为二进制后,提取出最右侧的1 public static void test3(){//找到一个数转为二进制后,提取出最右侧的1int a5;int eora (-a);//也可以写成 a(~a1)System.out.println(值是:eor);}运行结果:
值是:1 或 ( | ) 1 or 111 or 010 or 000 or 11。参加运算的两个对象只要有一个为1其值为1
与 () 000; 010; 100; 111. 两位同时为“1”结果才为“1”否则为0
取反( ~ )
~ 取反 ~是一元运算符用来对一个二进制数按位取反即将0变1将1变0
左移()
左移1位:相当于将该数的二进制后面补一个0 ,原理整体向左边走,就是之前的值乘2;
右移()
右移1位:相当于将该数的二进制后面少一位 ,原理整体向右走,就是之前的值除以2;
