重学数据结构与算法_热门推荐_行情

重学数据结构与算法

2024-12-23 17:16 浏览:100

空间是廉价的，时间是昂贵的

相较于空间复杂度(投入金钱增加算力)，时间复杂度(消耗时间)更为重要！

降低时间与空间复杂度的方法：

例.输入数组 a = [1,2,3,4,5,5,6] 中查找出现次数最多的数值。

暴力解法是：两层for遍历，维护一个最大次数time_max，对每个元素计算出现次数time_tmp，与time_max进行对比，时间复杂度是

优化思想：如何仅用单层for循环完成，用hash思想，引入k-v字典数据结构map，一次for保存每个元素出现的次数，再求每个元素次数的最大值，时间复杂度是。

还用上面的例子介绍：

实际上，有(数组)和(链表)两种结构，这里仅介绍链式存储。

线性表增删查：其他链表的操作与单向链表雷同，仅介绍单向链表

链表的问题常常围绕数据顺序的处理：，

例1.

头指针front，尾指针rear

哈希冲突： 不同对象的哈希地址相同（键值对的值相同）

分治需要使用递归
每轮递归的包括：分解问题、解决问题、合并结果

插入排序： 维护一个排好序的序列，不断为每个未插入的元素，与序列元素比较，找到合适的插入位置。

从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。

快速排序：也是不断的将序列不断二分，但分割的过程中，保证做。具体通过维护两个指针实现，从左右端点不断向中间走，如果左指针小于，暂存左指针去看右指针，如果右指针小于首元素，则交换指针元素。重复此过程直到左右指针相遇，从相遇处进行二分。（）
但存在交换操作（）

和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。

之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。

其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都有不止一种实现方法。

选择排序：适用于数据量较小的情况，时间复杂度为 O(N^2)，空间复杂度为 O(1)，是一种不稳定的排序算法。

插入排序：适用于数据量较小且基本有序的情况，时间复杂度为 O(N^2)，空间复杂度为 O(1)，是一种稳定排序算法。但对于基本有序的数据，插入排序效率最高。

归并排序：适用于数据量较大的情况，时间复杂度为 O(NlogN)，空间复杂度为 O(N)，是一种稳定排序算法。缺点是需要额外的空间开销。

快速排序：适用于数据量较大的情况，时间复杂度为 O(NlogN)，空间复杂度为 O(logN)，是一种不稳定的排序算法。缺点是在极端情况下可能会出现退化，效率大幅下降。

希尔排序：适用于数据量较大的情况，时间复杂度为 O(N^1.3 - N^2)，空间复杂度为 O(1)，是一种不稳定的排序算法。缺点是实现较为复杂。

堆排序：适用于数据量较大的情况，时间复杂度为 O(NlogN)，空间复杂度为 O(1)，是一种不稳定的排序算法。缺点是实现较为复杂。

计数排序：适用于值域范围较小的整数序列，时间复杂度为 O(N+K)，空间复杂度为 O(K)，是一种稳定排序算法。缺点是需要额外的空间开销。

桶排序：适用于分布比较均匀的数据，时间复杂度为 O(N)，空间复杂度为 O(M)，是一种稳定排序算法。缺点是对于分布不均匀的数据，效率不如快排和归并排序。