oyy0v0😼

O（？）时间复杂度算法流程中数据量为N 的话，时间复杂度讨论的在==N的样本==中执行完整个算法后==与常数操作的数量的关系==。 如何判断呢要将算法分解到常数操作，再去分析时间复杂度是多少 举例来说：选择排序 数组：【7】【8】【10】【2】【12】【5】【1】【….】【N】 下标 0 1 2 3 4 5 6 …… N-1 第一步：N个数看一遍，找最小值 ​ N次 N-1次 第二步：最小值放0位置O（1） ​ 1次交换 第三步：1~N-1个数看一遍 ，找最小值，进行一次交换。。。。依次循环 最终一共进行了一个等差数列，N个数，N-1个数，N-2个数……次 等差数列求和公式最终优化可以写成 (a,b,c)是常数 aN^2+bN+c 复杂度就是只要最高阶项O（n^2）,所以选择排序就是一个O（n^2）的算法。 因为当N数据量趋近于无穷时常数项就可以忽略了，而取 ...

选择排序选择排序就是每次循环找最小的然后交换。 1234567891011121314151617181920212223242526272829303132public class Code01_selectionSort { public static void selectionSort(int arr[]){ //如果数组只有一个或者为空则直接排序完成 if(arr == null || arr.length<2){ return; } //0~N-1找最小值，在哪，放到0位置上 //1~N-1找最小值... for(int i = 0;i<arr.length-1;i++){ int minIndex = i; for(int j = i+1; j < arr.length; j++){ //i~N-1 上找到最小值 ...

认识二分法原理：从一个有序数组里面，找中间位置的数（不用时间），判断中间的数和目标数字的大小，目标数字比中间的小，则需要找的范围就在中间位置的左边，直到最后一个数，如果最后一个数都不等于那么不存在这个数。 这是O（log2N)的算法 因为一共砍了log2N次（找中间值的次数），比大小的时间是O（1）。 二分法解决的问题： 在一个有序数组中，找某个数存不存在 在一个有序数组中，找大于某个数的最左位置 比如【1】【2】【3】【3】【3】 找大于等于三的最左位置就是下标为2的位置 在一个有序数组中，找到小于等于某个数的最右位置 局部最小值问题 二分代码：1. 12345678910111213141516171819public static boolean exist(int[] sortedArr, int num){ if(sortedArr == null || sortedArr.length == 0){ return false; } int L = 0; in ...

对数器就是利用两个不同的方法去解题，在测试量很大的时候去利用两个方法去解决同一个问题，比对两个方法解决出来的结果 如果一致则表明方法实现，没有则没实现。 因为测试量大所以基本上不会出现特殊例子让方法失败，即因为测试量很多所以极小概率会出现不成功的状况。 其次因为测试方法不同，并且测试量大，所以极小概率会出现两个方法都出错。 通过对数器可以检测代码的正确性以及找出错误代码例子从而进行修改 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869public class Code02_insertionSort { public static int[] generateRandomArray(int maxSize, int maxValue){ int[] arr = new int[(int) ((maxSize + 1) * Math.rand ...

动态数组 动态数组是什么？ 动态数组的使用和扩容。 动态数组的扩容与时间复杂度分析 数组VS动态数组​ 数组就是一开始有固定长度的，而动态数组和数组不同的事情就是多了一个扩容的功能。 ​ 以java中的ArrayList为例子假设一开始ArrayList数组一开始长度为3，可是你往里面加入了4个数字，刚开始加入3个数字的时候没有问题，当开始加入第四个数的时候，ArrayList始自动新建一个长度为原来长度的2倍的数组，即现在数组长度为6，然后将旧数组的数放入到新数组中，继续将剩下的数放入到新数组中，后将老的数组全部销毁掉。 问题：那么动态数组的扩容的一系列操作会影响他的时间复杂度吗？​ 假设一开始动态数组长度为1（以最差的情况来看），让后往里面放入N个数过程如下： 一开始是长度为1然后扩容为2为4,8,16一直到N而每一次扩容后放入数据的操作都是O（1） 所以整体来说一共进行了1+2+4+8+16+…+N次是一个等比数列也就是说时间复杂度是O（N） 加入所有数据的时间复杂度是O（N）但是加入一个数的时间复杂度是O（1），因为一共是N均摊一下就是1了，所以动态数组 ...

枚举类引入数学上的枚举法： 举例：1<x<3 , 2<y<6, 求x+y<8的有多少个 java上的枚举类的对象是有限个，并且是确定的，就可以使用枚举类。 举例：星期一，二，三。。。日。 自定义枚举类：（JDK1.5之前）123456789101112131415161718192021222324252627282930313233public class Mydate { //属性 private final String dateName;//星期几 private final String dateDesc;//星期的描述 //属性已经被private final修饰了，利用构造器赋值 //构造器也私有，外界不能调用，只能自己内部调用 private Mydate(String dateName, String dateDesc){ this.dateName=dateName; this.dateDesc=dateDesc; } //提供的 ...

Helloworld用java写helloworld 12345public class Test01 { public static void main(String[] args){ System.out.println("hello world"); }}