-
0 算法复杂度
算法复杂度
时间复杂度有关总结
一，常数时间的操作【基本操作】
常数时间——固定时间——O（1）——由实现细节决定
不会随着输入规模的变化而增加时间复杂度
1 基本操作解析
1.算数操作: a+b a-b a*b a/b
int a 32位 int b 32位 1+1 17899+78855- 执行时间一致，同样拥有32位的信息，一样用位相加
- 与数值本身的复杂程度没有关系
- 固定时间操作
2.数组寻址
int[] arr arr[1千万] arr[2百万] arr[8百万] 数组量大时【例如数百万或数亿个元素时】，可能进行跳转存储，但是查找时是固定时间操作- 数组逻辑结构为连续的区域，实际可能有几步进行跳转 【在数据量大时，进行分页或多维存储】
- 可以直接用索引取值，为固定时间操作，所用时间为一致的
- 存地址计算：
- Java中的数组是通过一块连续的内存来存储的。假设数组的起始地址是baseAddress，数组元素的大小是elementSize，数组中第i个元素的地址可以通过以下公式计算： elementAddress(i)=baseAddress+i×elementSize
3.linkedlist
- 为跳转结构的，每个结点有记录着下一个结点的地址
- 1千万长度，无法直接找到所需数据，需要跳转【必须从头节点开始逐个遍历节点】
- 找2百万和8百万数据时，所需时间不一致，为非固定时间操作，链表查找操作的时间复杂度为O(n)
2 常见的常数时间操作
以下是常数级时间复杂度操作的总结表格：
操作类别 示例代码 说明 赋值和访问 int a = 5;基本数据类型的赋值 arr[i];访问数组元素 obj.field;访问对象的字段 算术运算 a + b;加法 a - b;减法 a * b;乘法 a / b;除法 a % b;模运算 比较运算 a == b;等于 a > b;大于 a < b;小于 a >= b;大于等于 a <= b;小于等于 逻辑运算 a && b;与 `a !a;非 位运算 a & b;位与 `a b;` a ^ b;位异或 ~a;位非 a << b;左移 a >> b;右移 a >>> b;无符号右移 库函数调用 str.length();获取字符串长度 arr.length;获取数组长度 System.currentTimeMillis();获取当前时间 数据结构操作 ArrayList list.get(i);获取元素 list.set(i, value);设置元素 HashMap map.get(key);获取元素 map.put(key, value);插入/更新元素 map.remove(key);删除元素 HashSet set.add(value);添加元素 set.remove(value);删除元素 set.contains(value);检查是否包含元素 对象操作 new Object();创建新对象 obj.method();访问对象方法 obj1.equals(obj2);对象比较 二 时间复杂度【流程决定】
1 怎么算⭐
理解：算法流程中，数据量为N，执行完整个流程，常数操作数量是什么关系？
数据量很大时，只与阶数最大项有关
怎么估算：
- 将算法流程操作往下分解为常数时间的操作，确定算法流程的总操作数量与样本数量之间的表达式关系。
步骤分解与分析- 确定基本操作：
- 识别算法中的基本操作，如赋值、比较、算术运算等。这些操作的执行时间可以视为常数时间 O(1)O(1)O(1)。
- 分析每一步的操作数量：
- 对于每一部分或步骤，计算基本操作的执行次数。例如，循环体内的操作次数与循环的迭代次数有关。
- 求和所有步骤的操作数量：
- 将所有部分的操作次数相加，得到算法的总操作数量。
- 表达总操作数量与样本数量的关系：
- 将总操作数量表示为样本数量 n 的函数，通常会使用大O符号表示算法的时间复杂度。
- 确定基本操作：
- 最后只看最高阶项的部分。
2 例：选择排序-O（N^2）
流程分析
流程分析要将操作分解为常数时间操作【正确识别基本操作】
错误分解方式【没有正确分解基本操作】
1）—— 0~n-1 找最小 放0位置【看为一个操作】不是常数时间操作
2）—— 1~n-1 找最小 放1位置
. . .
n）—— n-1 不需要操作 这样看不出时间复杂度，正确分解方式
1）——
①.0~n-1 n个数找最小 n-1次比较 看加比
②.最小值放0位置 交换2）——
①.1~n-1 n-1个数找最小 n-2次比较 看加比
②.最小值放1位置 交换
. . .
（n-1）——
①.n-2~n-1 2个数找最小 1次比较 看加比
②.最小值放n-2位置 交换 （n）n-1位置不需要操作-
（n-1)+（n-2)+…+1 等差数列
-
a * N^2 +b * N + c (a,b,c为常数) 将 看，比，加操作 相加关系同样为此表达式
-
O（N^2）
图形化流程理解
使用等差数列求和 N就是数据量 和是操作数
代码示例
package class01; import java.util.Arrays; public class Code01_SelectionSort { public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 找到最小值，在哪，放到0位置上 // 1 ~ n-1 找到最小值，在哪，放到1 位置上 // 2 ~ n-1 找到最小值，在哪，放到2 位置上 for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // 对数函数 public static void comparator(int[] arr) { Arrays.sort(arr); } // 随机产生数组 public static int[] generateRandomArray(int maxSize, int maxValue) { // Math.random() [0,1) // Math.random() * N [0,N) // (int)(Math.random() * N) [0, N-1] int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { // [-? , +?] arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); //[0,maxValue+1]-[0,maxValue+1] 形成负的整数和正整数随机数 } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test 判断是否一致 public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {//一空一不空 return false; } if (arr1 == null && arr2 == null) {//都为空 return true; } if (arr1.length != arr2.length) {//长度不相等 return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test 打印数组 public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000;//测试次数 int maxSize = 100;//最大长度 int maxValue = 100;//最大值 boolean succeed = true;//成败标志 for (int i = 0; i < testTime; i++) {//开始测试 int[] arr1 = generateRandomArray(maxSize, maxValue);//生成随机数组 int[] arr2 = copyArray(arr1);//拷贝 selectionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); selectionSort(arr); printArray(arr); } }3 例：list.get-时间复杂度分析
要注意调用的api的底层
- 链表O(N)
- 数组O(1)
for（i=0；i循环时间复杂度为：n list.get如果为链表操作，每次从0开始遍历到i 时间复杂度为：N 所以此代码时间复杂度为： O（N^2)4 例：冒泡排序-O（N^2）
流程复杂度分析：
N个数，相邻两数谁大谁往后（O(1)） N个相邻数进行交换 N-1次 N-1个数 N-2个数 等差数列——O（N^2）代码示例
package class01; import java.util.Arrays; public class Code02_BubbleSort { public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 0 ~ N-1 // 0 ~ N-2 // 0 ~ N-3 for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } } } // 交换arr的i和j位置上的值 public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); bubbleSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); bubbleSort(arr); printArray(arr); } }5 例:插入排序-O（N^2）
插入排序过程:
- 想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。
- 想让arr[0~1]上有序，所以从arr1开始往前看，如果arr1
- 想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
- 最后一步，想让arr[0~N-1]上有序，arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
- 估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。
流程及复杂度分析：
[3,2,3,1,4,0] 0,1,2,3,4,5 1) 0~0 有序 2) 0~1 有序 1与前比 插入 3) 0~2 有序 2与前比 插入 4) 0~3 有序 3与前比 插入 5) 0~4 有序 4与前比 插入 6) 0~5 有序 5与前比 插入 不固定时间 时间随数据情况变化时，最差情况来估计流程 [7,6,5,4,3,2,1] 交换次数 1 2 3 4 5 6代码示例：
package class01; import java.util.Arrays; public class Code03_InsertionSort { public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 不只1个数 for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序 for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } } // i和j是一个位置的话，会出错 public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { // Math.random() -> [0,1) 所有的小数，等概率返回一个 // Math.random() * N -> [0,N) 所有小数，等概率返回一个 // (int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个 int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; // 长度随机 for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; // 随机数组的长度0～100 int maxValue = 100;// 值：-100～100 boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr = generateRandomArray(maxSize, maxValue); int[] arr1 = copyArray(arr); int[] arr2 = copyArray(arr); insertionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { // 打印arr1 // 打印arr2 succeed = false; for (int j = 0; j < arr.length; j++) { System.out.print(arr[j] + " "); } System.out.println(); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); insertionSort(arr); printArray(arr); } }6 冒泡排序和插入排序比较
冒泡排序：在数据优良情况下，流程固定，比较次数没有减少，减少了交换
插入排序：在数据优良情况下，减少了比较和交换
三，注意
- 算法的过程和具体的语言是无关的。
- 想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉。
- 一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己用过的每一个系统api都非常熟悉。否则会影响你对时间复杂度的估算。
四，常见时间复杂度
常见时间复杂度的表格总结：
时间复杂度 描述 示例 O(1) 常数时间复杂度 直接访问数组元素 O(log n) 对数时间复杂度 二分查找 O(n) 线性时间复杂度 遍历数组 O(n log n) 线性对数时间复杂度 快速排序、归并排序 O(n^2) 平方时间复杂度 冒泡排序、插入排序 O(n^3) 立方时间复杂度 简单的多层嵌套循环算法 O(2^n) 指数时间复杂度 某些递归算法 O(n!) 阶乘时间复杂度 解决旅行商问题 口诀：常对线幂指阶
第三方接口重试机制是怎么做的
安装BBR教程，来加速VPS
MQ回退消息 springboot
Android开发MVP架构记录
使用 Charles 去修改响应信息（真实工作使用场景1）
HIN应用调研总结
C++——list
1-十八烷基-3-三乙氧基丙基硅烷咪唑溴盐离子液体([ODTIm]Br)修饰Fe3O4磁性纳米颗粒
qlistwidget不显示内容