8. 数据结构与算法

8. 数据结构与算法

常见面试题

1. 说说一个算法有哪些时间复杂度？归并算法时间复杂度是多少？⭐⭐⭐

   O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

   归并算法时间复杂度是O(nlogn)

2. 说说数组时间复杂度，什么场景下使用？⭐⭐⭐⭐⭐

   从渐进趋势来看，数组插入和删除操作的时间复杂度是O(n)。而数组是有序的，可以直接通过下标访问元素，十分高效，访问时间复杂度是O(1)（常数时间复杂度）。

   如果某些场景需要频繁插入和删除元素时，这时候不宜选用数组作为数据结构。

   频繁访问的场景下，可以使用数组。

3. 说说vector的实现原理⭐⭐⭐⭐⭐

   vector是数组的进一步封装，它是一个类。可以比数组更加灵活的处理内存空间。

   vector采用的数据结构是线性的连续空间，它以两个迭代器start和finish分别指向配置得来的连续空间中目前已将被使用的空间。迭代器end_of_storage指向整个连续的尾部。

   vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新的元素。vector在增加元素时，如果超过自身最大的容量Capacity，vector则将自身的容量扩充为原来的两倍。扩充空间需要经过的步骤：重新配置空间&