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

顺序表
插入操作：平均移动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)

折半插入排序：时间复杂度为
希尔排序：最坏情况下O(n2)
冒泡排序
最好时，基本有序，第一趟比较n-1次，移动0次，所以最好为O(n)；
当初始为逆序时，需要进行n-1趟排序，第i趟进行n-i次比较，而且每次比较都需要移动元素3次来交换，最坏时间复杂度为O(n²)，平均也为O(n²)
快速排序：最好为 ，最坏为O(n2)，平均为
简单选择排序：时间复杂度T(n)=O(n2)
堆排序
堆的插入、删除操作：时间复杂度为 O(log2⁡n)最好最坏平均为 O(log2⁡n)
归并排序：时间复杂度： O(nlog2⁡n)