0 算法复杂度

  • 开发
  • 6

算法复杂度

时间复杂度有关总结

一，常数时间的操作【基本操作】

常数时间——固定时间——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，执行完整个流程，常数操作数量是什么关系？

数据量很大时，只与阶数最大项有关

怎么估算：

  • 将算法流程操作往下分解为常数时间的操作，确定算法流程的总操作数量与样本数量之间的表达式关系。
    步骤分解与分析
    1. 确定基本操作：
      • 识别算法中的基本操作，如赋值、比较、算术运算等。这些操作的执行时间可以视为常数时间 O(1)O(1)O(1)。
    2. 分析每一步的操作数量：
      • 对于每一部分或步骤，计算基本操作的执行次数。例如，循环体内的操作次数与循环的迭代次数有关。
    3. 求和所有步骤的操作数量：
      • 将所有部分的操作次数相加，得到算法的总操作数量。
    4. 表达总操作数量与样本数量的关系：
      • 将总操作数量表示为样本数量 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:i++)
{
    list.get(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）

插入排序过程:

  1. 想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。
  2. 想让arr[0~1]上有序，所以从arr1开始往前看，如果arr1<arr[0]，就交换。否则什么也不做。
  3. 想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
  4. 最后一步，想让arr[0~N-1]上有序，arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
  5. 估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。

流程及复杂度分析：

[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 冒泡排序和插入排序比较

冒泡排序：在数据优良情况下，流程固定，比较次数没有减少，减少了交换

插入排序：在数据优良情况下，减少了比较和交换

三，注意

  1. 算法的过程和具体的语言是无关的。
  2. 想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉。
  3. 一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己用过的每一个系统api都非常熟悉。否则会影响你对时间复杂度的估算。

四，常见时间复杂度

常见时间复杂度的表格总结：

时间复杂度 描述 示例
O(1) 常数时间复杂度 直接访问数组元素
O(log n) 对数时间复杂度 二分查找
O(n) 线性时间复杂度 遍历数组
O(n log n) 线性对数时间复杂度 快速排序、归并排序
O(n^2) 平方时间复杂度 冒泡排序、插入排序
O(n^3) 立方时间复杂度 简单的多层嵌套循环算法
O(2^n) 指数时间复杂度 某些递归算法
O(n!) 阶乘时间复杂度 解决旅行商问题
口诀：常对线幂指阶
阅读全部

相关推荐

  3. 算法复杂度分析

    2024-06-17 03:46:03       33 阅读

  4. 【算法】复杂度分析

    2024-06-17 03:46:03       25 阅读

  7. 算法的空间复杂度

    2024-06-17 03:46:03       32 阅读

  10. 数据结构-算法复杂度

    2024-06-17 03:46:03       12 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-06-17 03:46:03       16 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-06-17 03:46:03       16 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-06-17 03:46:03       15 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-06-17 03:46:03       18 阅读

热门阅读

  1. react捡起来了

    2024-06-17 03:46:03       6 阅读

  7. python判断一个数是不是偶数

    2024-06-17 03:46:03       9 阅读

  8. 编程机器人的参数表怎么看

    2024-06-17 03:46:03       6 阅读

  12. AI芯片战场的迁徙：从训练到推理的深度剖析

    2024-06-17 03:46:03       6 阅读

  13. Linux部署FTP服务

    2024-06-17 03:46:03       5 阅读

  15. 大模型算法岗 100 道面试题（含答案）

    2024-06-17 03:46:03       6 阅读

  20. vue项目导入 .xlsx 文件

    2024-06-17 03:46:03       6 阅读

  21. Eureka注册中心

    2024-06-17 03:46:03       4 阅读

  22. 6月16日-英语学习日记-（专科生）

    2024-06-17 03:46:03       5 阅读

  23. 推荐一个轻量级适合阅读的优秀C++开源项目

    2024-06-17 03:46:03       7 阅读

  24. 华为OD机考题HJ1 字符串最后一个单词的长度

    2024-06-17 03:46:03       6 阅读

  25. 没有废话-MySQL,MyBatis 动态参数添加序号值(默认递增或根据内容进行递增)

    2024-06-17 03:46:03       7 阅读

  27. Postman接口测试工具详解

    2024-06-17 03:46:03       8 阅读

  28. msys2 |arch pacman：tesseract ocr 安装 - 思源笔记自动调用

    2024-06-17 03:46:03       8 阅读

  30. 中高级软件工程师的c语言面试题

    2024-06-17 03:46:03       7 阅读