添加:动态数组最好O(1),最坏O(n),平均O(n),链表一样
删除:动态数组最好O(1),最坏O(n),平均O(n),链表一样
修改:动态数组都为O(1),链表最好O(1),最坏O(n),平均O(n)
获取:动态数组都为O(1),链表最好O(1),最坏O(n),平均O(n)
10大排序算法(基于数组进行排序)
冒泡排序:最好O(n),最坏O(n^2),平均O(n^2)
选择排序:最好O(n^2),最坏O(n^2),平均O(n^2)
插入排序:最好O(n),最坏O(n^2),平均O(n^2)
归并排序:最好O(nlogn),最坏O(nlogn),平均O(nlogn)
快速排序:最好O(nlogn),最坏O(n^2),平均O(nlogn)
希尔排序:最好O(n),最坏O(n^4/3)-O(n^2),平均取决于布长序列
堆排序:最好O(nlogn),最坏O(nlogn),平均O(nlogn)
基数排序:最好O(d*(n+k))最坏O(d*(n+k)),平均O(d*(n+k))
桶排序:最好O(n+k),最坏O(n+k),平均:O(n+k)
计数排序:最好O(n+k),最坏O(n+k),平均:O(n+k)
递推式及复杂度对照表
T(n)=T(n/2)+O(1) 时间复杂度:O(logn)
T(n)=T(n-1)+O(1) 时间复杂度:O(n)
T(n) = T(n/2)+O(n) 时间复杂度:O(n)
T(n)=2*T(n/2)+O(1) 时间复杂度:O(n)
T(n)=2*T(n/2)+O(n) 时间复杂度:O(nlogn)
T(n)=T(n-1)+O(n) 时间复杂度:O(n^2)
T(n)=2*T(n-1)+O(1)时间复杂度为:O(2^n)
T(n)=2*T(n-1)+O(n)时间复杂度为:O(2^n)