数据结构与算法之美-读书笔记3

在面试的时候问到数组和链表的区别，很多人都回答说，“链表适合插入、删除，时间复杂度O(1)；数组适合查找，查找时间复杂度为O(1)”。

实际上，这种表述是不准确的。数组是适合查找操作，但是查找的时间复杂度并不为O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。

数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。 

容器能否完全替代数组？

针对数组类型，很多语言都提供了容器类，比如Java中的ArrayList、C++ STL中的vector。在项目开发中，什么时候适合用数组，什么时候适合用容器呢？

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

对于多维数组，直接采用数组，定义起来会方便很多。

比如Object[][] array；而用容器的话则需要这样定义：ArrayList array。

为什么数组的插入和删除操作很低效呢？
插入：
        如果有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。
        最好情况时间复杂度 O(1)         最坏情况复杂度为O(n)        平均负责度为O(n)
优化：如果数组中的数据不是有序的，也就是无规律的情况下，可以直接把第k个位置上的数据移到最后，然后将插入的数据直接放在第k个位置上。可以把时间复杂度变成O（1）。
删除：
与插入类似，为了保持内存的连续性。
最好情况时间复杂度 O(1)        最坏情况复杂度为O(n)        平均负责度为O(n)

还学到了一个数组访问越界问题
C语言中的数据越界是一种未决行为，一般比较难发现的逻辑错误。相比之下，Java会有越界检查。