数据结构与算法(下)

数据结构与算法基础知识 #生活技巧# #工作学习技巧# #数字技能学习#

最好情况时间复杂度（best case time complexity）

什么是最好情况时间复杂度？

--->简单理解：最好情况时间复杂度就是算法在最理想、最幸运的输入条件下，所需要的最少运行时间。

通俗比喻

--->想象你在一个图书馆里找一本书：
--->最好的情况：你刚走进图书馆，要找的书就在入口处的显眼位置，你一眼就看到了，立刻拿到手 - 这就是最好情况，只需要1步

实际编程例子

// 在数组中查找目标元素 public int search(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; // 找到了，返回位置 } } return -1; // 没找到 } 最好情况：目标元素就在数组的第一个位置，只需要比较1次就找到了
时间复杂度：O(1)

最坏情况时间复杂度（worst case time complexity）

什么是最坏情况时间复杂度？

--->简单理解：最坏情况时间复杂度就是算法在最不利、最倒霉的输入条件下，所需要的最多运行时间。
--->最坏的情况：你要找的书要么在图书馆最偏僻的角落（最后一个位置），要么根本就不存在这本书，你必须把整个图书馆都翻遍才能确定结果

实际编程例子

// 在数组中查找目标元素 public int search(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return -1; // 没找到 } 最坏情况：数组是完全逆序的（从大到小排列，但我们要从小到大排序）
每次比较都需要交换，需要进行 n×(n-1)/2 次比较 时间复杂度：O(n²)

平均情况时间复杂度（average case time complexity）

什么是平均情况时间复杂度？

--->简单理解：平均情况时间复杂度就是算法在各种可能的输入情况下，平均需要的运行时间。它反映了算法在日常使用中的典型表现。
--->1. 最好情况：书就在门口，1秒找到 - 概率很小
--->2. 最坏情况：找遍整个图书馆，1小时才找到 - 概率也很小
--->3. 平均情况：大多数时候，你可能需要找20-30分钟 - 这是最常见的情况

实际编程例子

//假设要在长度为n的数组中查找一个元素： public int search(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return -1; }

各种情况分析：

如果元素在第1个位置：需要比较1次
如果元素在第2个位置：需要比较2次
如果元素在第3个位置：需要比较3次
如果元素在第n个位置：需要比较n次
如果元素不存在：需要比较n次

平均时间 = Σ(每种情况的时间 × 该情况发生的概率) 平均比较次数 = (1 + 2 + 3 + ... + n) ÷ n = n(n+1)/2 ÷ n = (n+1)/2 ≈ n/2

生活中的平均情况

上班通勤例子 最好情况：20分钟（5%的概率）
平均情况：35分钟（80%的概率）
最坏情况：60分钟（15%的概率）
平均通勤时间 = 20×0.05 + 35×0.8 + 60×0.15 = 38分钟这就是你每天应该预留的时间！
餐厅排队例子 有时候没人排队，直接就座（最好）
有时候排队很长，等1小时（最坏）
大多数时候等15-20分钟（平均）

实际编程例子

// 快速排序的平均情况 public void quickSort(int[] arr, int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } 最好情况：每次都能选到中位数作为基准，O(n log n) 最坏情况：每次都选到最大/最小值作为基准，O(n²) 平均情况：大多数时候基准选择比较均匀，O(n log n) 快速排序之所以被广泛使用，就是因为它的平均性能很好！

均摊时间复杂度（amortized time complexity）

--->简单理解：均摊时间复杂度就是把一系列操作的总时间平均分摊到每个操作上，得到的平均时间复杂度。
--->关键思想：虽然某些操作偶尔会很慢，但大部分时候都很快，从长远来看平均下来还是很高效的。

银行存钱的例子 平时：每天存1元钱，很轻松，花费时间很少
偶尔：存钱罐满了，需要花很长时间去银行存钱并换新的存钱罐
均摊分析：虽然去银行那天很麻烦，但平均下来每天的"存钱成本"还是很低的
搬家的例子 平时：每天只是把东西随手放在房间里，很快
偶尔：房间乱得无法住人了，需要花一整天时间大扫除
均摊分析：虽然大扫除那天很累，但平均下来每天的"整理成本"不高

经典编程例子：动态数组（ArrayList）

// 简化的动态数组实现 public class DynamicArray { private int[] array; private int size; private int capacity; public DynamicArray() { capacity = 1; array = new int[capacity]; size = 0; } public void add(int element) { // 如果数组满了，需要扩容 if (size == capacity) { resize(); // 这个操作很耗时！ } array[size] = element; size++; } private void resize() { capacity *= 2; // 容量翻倍 int[] newArray = new int[capacity]; // 把所有元素复制到新数组 - O(n)时间 for (int i = 0; i < size; i++) { newArray[i] = array[i]; } array = newArray; } } 分析这个例子：

单次操作分析：

大部分情况：直接在数组末尾添加元素，时间复杂度 O(1) 偶尔情况：数组满了需要扩容，复制所有元素，时间复杂度 O(n) 如果只看最坏情况：每次添加都可能需要扩容，时间复杂度是 O(n)但这样分析是不准确的！ 均摊分析：

假设我们连续添加 n 个元素：

容量变化：1 → 2 → 4 → 8 → 16 → ... → n 扩容次数：log₂(n) 次 总的复制操作：1 + 2 + 4 + 8 + ... + n/2 ≈ n 次 总时间：n (插入操作) + n (复制操作) = 2n 均摊到每次操作：2n ÷ n = 2，即 O(1) 用"存钱"来类比：

第1天：存1元（容量1，满了要扩容，复制1个元素） 第2天：存1元（容量2，直接存） 第3天：存1元（容量2，满了要扩容，复制2个元素） 第4天：存1元（容量4，直接存） 第5天：存1元（容量4，直接存） 第6天：存1元（容量4，直接存） 第7天：存1元（容量4，满了要扩容，复制4个元素）

意义

 最好情况时间复杂度 - "理想状态下的潜力"

意义：告诉你算法在最理想条件下能有多快
作用：

发现算法优势：了解算法的最佳表现 特殊场景优化：如果你的数据经常符合最好情况，这个算法就很有价值 算法潜力评估：看看算法的"天花板"在哪里  最坏情况时间复杂度 - "安全保障的底线"

意义：告诉你算法在最糟糕条件下会有多慢
作用：

日常性能预估：大多数时候系统会是什么样的表现 算法选择依据：选择算法时最重要的参考指标 用户体验评估：用户平时会感受到的性能 成本核算：计算平均运营成本  ### 平均情况时间复杂度 - "日常使用的参考"

意义：告诉你算法在一般情况下的表现
作用：

日常性能预估：大多数时候系统会是什么样的表现 算法选择依据：选择算法时最重要的参考指标 用户体验评估：用户平时会感受到的性能 成本核算：计算平均运营成本  ### ### 均摊时间复杂度 - "长期投资回报"

意义：将一系列操作的总成本平均分摊，看长期表现
作用：

长期性能评估：虽然偶尔很慢，但长期来看很高效 数据结构设计：很多高效数据结构都依赖均摊分析 批量操作优化：证明某些"看起来慢"的操作实际上很高效 投资决策：类似"前期投入大，后期收益高"的策略

网址：数据结构与算法(下) https://www.yuejiaxmz.com/news/view/1215585

相关内容

《数据结构与算法分析
《数据结构与算法》—— O(3N)=O(N) ?
程序员到底为什么要掌握数据结构与算法？
数据结构之算法的时间与空间复杂度
Pascal之父——Nicklaus Wirth——算法+数据结构=程序
面试官问你：程序=算法+数据结构，能深入讲讲吗？
数据与智能算法
编程祖师爷尼古拉斯•威茨：算法+数据结构=程序
构建树型结构数据解析
python数据结构练习

随便看看