一、存儲結構由數組換為鏈表,時間復雜度會變高的算法
1、隨機訪問
數組具有常數時間復雜度的隨機訪問,即通過索引可以直接訪問數組中的元素。而鏈表由于沒有連續的內存空間,無法直接通過索引訪問,而是需要從頭節點開始逐個遍歷,時間復雜度為O(n),其中n是鏈表的長度。因此,對于需要頻繁進行隨機訪問的場景,鏈表的時間復雜度會變高。
2、插入和刪除操作
鏈表在插入和刪除操作上具有優勢,因為只需要修改相鄰節點的指針,而無需移動其他元素。但當涉及到在鏈表中插入或刪除某個節點時,需要先找到該節點的位置,這通常需要從頭節點開始遍歷鏈表,時間復雜度為O(n),其中n是鏈表的長度。而數組的插入和刪除操作可能需要移動其他元素以保持連續性,時間復雜度為O(n)或更高,具體取決于操作的位置和元素個數。
3、排序算法
某些排序算法的時間復雜度可能會因為使用鏈表而變高。例如,快速排序通常使用數組的隨機訪問特性來選擇基準元素,并在數組中進行原地交換。而在鏈表中,由于沒有隨機訪問,無法高效地選擇基準元素和進行原地交換,導致快速排序的時間復雜度可能變高。而歸并排序等基于合并的排序算法可能對鏈表更適用,因為鏈表在合并操作上具有優勢。
4、查找算法
在查找算法中,例如二分查找這種基于有序數組的算法,由于數組具有隨機訪問特性,可以在O(log n)的時間內完成查找。而在鏈表中,由于沒有隨機訪問,無法進行高效的二分查找,而需要遍歷鏈表,時間復雜度為O(n)。因此,鏈表在某些查找算法中可能會導致時間復雜度變高。