复杂度

一般用 大O表示法 来描述复杂度，表示 数据规模n 对应的复杂度。不过要注意 大O表示法 仅仅是一种粗略的分析模型，是一种估算，用来帮助我们在短时间内了解一个算法的执行效率。 时间复杂度又称"渐进式时间复杂度"，用来表示代码执行时间与数据规模之间的增长关系

上面这段代码是往数组尾插入元素，并且实现了自动扩容功能。在数组未满的情况下，直接放到数组尾即可，因此，最好时间复杂度为 O(1)。在数组满的情况下，需要进行 n 次移动，并申请 n 个空间，因此，最坏时间复杂度是 O(n)，最坏空间复杂度是 O(n)

快速排序最坏时间复杂度和平均时间复杂度的区别是什么？ 答：其中 是一趟快排需要的比较次数，一趟快排结束后将数组分成两部分 和. 最好时间复杂度: 核心点:最好情况下，每一次划分都正好将数组分成长度相等的两半. 最坏时间复杂度: 核心点:最坏情况下，每一次划分都将数组分成了0和n-1两部分. 平均时间复杂度: 核心点:任意一种划分情况出现的概率都相等. 所有的划分情况为：. 综上 :快速排序最好时间复杂度为 最坏时间复杂度为 平均时间复杂度为. 快速排序的空间复杂度是多少？ 答：快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的 空间复杂度 为 O (logn) ，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O (n) 。什么是快速排序的最坏情况？ 答：什么是快速排序的最坏情况，那就是， 对于每一个区间，我们在处理的时候，选取的轴刚好就是这个区间的最大值或者最小值 。 比如我们需要对 n 个数排序，而每一次进行处理的时候，选取的轴刚好都是区间的最小值

依旧还是面试题，比较麻烦的是，这个排序的关键在于，我们需要时间复杂度为O(n)，空间复杂度为O(1)。 题目大概是这样的，看了输入输出基本就会明白了： 这里其实主要没做出来是因为我没有很好地理解怎么计算复杂度，尤其是空间复杂度，时间复杂度我勉强记忆成for循环的嵌套还是可以的，但是空间复杂度呢？ 这里空间复杂度意味着没有长度为n的数组（但是可以是常量个）。 括号里的当时是我没想到的部分，我以为是：一个数组都不能开