存储结构由数组换为链表，时间复杂度会变高的算法有哪些?

一、存储结构由数组换为链表，时间复杂度会变高的算法

1、随机访问

数组具有常数时间复杂度的随机访问，即通过索引可以直接访问数组中的元素。而链表由于没有连续的内存空间，无法直接通过索引访问，而是需要从头节点开始逐个遍历，时间复杂度为O(n)，其中n是链表的长度。因此，对于需要频繁进行随机访问的场景，链表的时间复杂度会变高。

2、插入和删除操作

链表在插入和删除操作上具有优势，因为只需要修改相邻节点的指针，而无需移动其他元素。但当涉及到在链表中插入或删除某个节点时，需要先找到该节点的位置，这通常需要从头节点开始遍历链表，时间复杂度为O(n)，其中n是链表的长度。而数组的插入和删除操作可能需要移动其他元素以保持连续性，时间复杂度为O(n)或更高，具体取决于操作的位置和元素个数。

3、排序算法

某些排序算法的时间复杂度可能会因为使用链表而变高。例如，快速排序通常使用数组的随机访问特性来选择基准元素，并在数组中进行原地交换。而在链表中，由于没有随机访问，无法高效地选择基准元素和进行原地交换，导致快速排序的时间复杂度可能变高。而归并排序等基于合并的排序算法可能对链表更适用，因为链表在合并操作上具有优势。

4、查找算法

在查找算法中，例如二分查找这种基于有序数组的算法，由于数组具有随机访问特性，可以在O(log n)的时间内完成查找。而在链表中，由于没有随机访问，无法进行高效的二分查找，而需要遍历链表，时间复杂度为O(n)。因此，链表在某些查找算法中可能会导致时间复杂度变高。