一、初识数据结构与算法
1.1 数据结构与算法
数据结构是指在计算机中组织和存储数据的方式。它关注数据的逻辑关系、操作和存储方式，以及如何有效地访问和修改数据。常见的数据结构包括数组、链表、栈、队列、树、图等。
算法是解决问题的一系列步骤或规则。它描述了如何通过输入数据来产生所需的输出结果。算法可以用来执行各种计算任务，如排序、搜索、图形处理等。好的算法应该具有正确性、可读性、高效性和健壮性。
数据结构和算法之间存在密切的关系。选择合适的数据结构可以提高算法的效率，而好的算法可以更好地利用数据结构的优势。数据结构和算法相互支持，共同构成了计算机科学的基础。
1.2 二分查找
二分查找（Binary Search）（折半查找）是一种在有序数组中查找特定元素的常用算法。它通过将目标值与数组中间元素进行比较，从而将查找范围缩小一半，直到找到目标值或确定目标值不存在。
1.0版 基础版
2.0版 改动版
1.3 如何判断算法好坏
1.3.1 时间复杂度
时间复杂度是衡量算法执行时间随输入规模增长而变化的度量。它表示了算法执行所需的基本操作数量，通常用大 O 符号来表示。
以下是常见的时间复杂度：
- 常数时间复杂度：O(1)，表示算法的执行时间不随输入规模变化而变化，执行时间固定。
- 对数时间复杂度：O(log n)，表示算法的执行时间随输入规模呈对数级增长。例如，二分查找算法就具有对数时间复杂度。
- 线性时间复杂度：O(n)，表示算法的执行时间随输入规模呈线性增长。例如，遍历一个数组的算法就具有线性时间复杂度。
- 线性对数时间复杂度：O(n log n)，表示算法的执行时间随输入规模呈线性对数级增长。例如，快速排序和归并排序等排序算法具有线性对数时间复杂度。
- 平方时间复杂度：O(n^2)，表示算法的执行时间随输入规模呈平方级增长。例如，嵌套循环的算法就具有平方时间复杂度。
- 指数时间复杂度：O(2^n)，表示算法的执行时间随输入规模呈指数级增长。指数时间复杂度的算法通常具有非常高的时间复杂度，效率很低。
需要注意的是，时间复杂度只是对算法执行时间的一种度量方式，它可以帮助我们比较不同算法的效率。在实际应用中，除了时间复杂度，还需要考虑空间复杂度、具体硬件环境等因素来综合评估算法的性能。
1.3.2 空间复杂度
空间复杂度是衡量算法在执行过程中所需的额外空间（内存）随输入规模增长而变化的度量。它表示了算法所需的额外空间与输入规模之间的关系，通常用大 O 符号来表示。
以下是常见的空间复杂度：
- 常数空间复杂度：O(1)，表示算法的额外空间使用量固定，不随输入规模变化而变化。常数空间复杂度的算法只使用固定数量的额外内存空间。
- 线性空间复杂度：O(n)，表示算法的额外空间使用量随输入规模线性增长。例如，在存储输入数据的数组或列表中，算法需要使用与输入规模相等的额外空间。
- 线性对数空间复杂度：O(n log n)，表示算法的额外空间使用量随输入规模呈线性对数级增长。例如，某些排序算法在排序过程中需要使用辅助空间，其空间复杂度与输入规模的对数级相关。
- 平方空间复杂度：O(n^2)，表示算法的额外空间使用量随输入规模平方级增长。例如，在存储二维矩阵或多维数组时，算法需要使用与输入规模平方相关的额外空间。
需要注意的是，空间复杂度只考虑算法在执行过程中所需的额外空间，不包括输入数据本身的空间。在实际应用中，除了空间复杂度，还需要综合考虑时间复杂度、具体硬件环境等因素来评估算法的性能。
1.4 重看二分查找
⼆分查找性能
下⾯分析⼆分查找算法的性能
时间复杂度
最坏情况：O(log n)
最好情况：如果待查找元素恰好在数组中央，只需要循环⼀次 O(1)
空间复杂度
需要常数个指针 i,j,m，因此额外占⽤的空间是 O(1)
3.0 平衡版
4.0 java版
5.1 返回的是最左侧的重复元素
改动：
java算法基础和数据结构
5.1 返回的是最右侧的重复元素
改动：
二、基础数据结构
2.1 数组
空间占用：
Java 中数组结构为
- 8 字节 markword
- 4 字节 class 指针（压缩 class 指针的情况）
- 4 字节 数组大小（决定了数组最大容量是 2^{32}）
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/24798.html