数据结构：时间复杂度汇总_数据结构时间复杂度总结

顺序表
插入操作：平均移动n/2个元素，则时间复杂度为O(n)
表尾插入：时间复杂度为O(1)
删除操作：顺序表中删除任意一个元素，平均需要有(n-1)/2个元素移动，时间复杂度为O(n)
查找操作：平均比较次数(n+1)/2，时间复杂度为O(n)
数据交换位置：时间复杂度O(n)
删除值为x的元素：时间复杂度O(n)
有序表改成无序表：时间复杂度O(n)
求两个等长升序序列A,B的中位数：时间复杂度O(n)
顺序表按值查找：有序时，顺序表可以折半查找,O(log₂n)
无序时，都为O(n)
按序号查找：顺序表为O(1),链表为O(n)
链表
插入操作：时间复杂度T(n)=O(1)
删除操作：时间复杂度T(n)=O(1)
头插法：时间复杂度T(n)=O(1)
尾插法：时间复杂度T(n)=O(n)
按值或序号查找：时间复杂度T(n)=O(n)
循环双向链表查找：时间复杂度T(n)=O(n)
双向循环链表插入和删除：时间复杂度T(n)=O(1)

栈
出栈、入栈的时间复杂度为T(n)=O(n)
链式存储结构的时间复杂度均为T(n)=O(1)

普里姆算法：时间复杂度O(n2)
折半查找：时间复杂度为
排序
直接插入排序
最好情况:初始有序,为O(n);
最坏情况:初始逆序,为O(n2);
平均时间复杂度T(n)= O(n2)

折半插入排序：时间复杂度为