网站建设好了怎么在百度可以搜到梅江区住房和城乡建设局官方网站

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则将自身的容量扩充为原来的两倍。扩充空间需要经过的步骤：重新配置空间&