收费网站模板,查看网站被恶意镜像,哈尔滨建站模板源码,wordpress编辑器 模板1. 常见的错误
这里我要特别纠正一个“错误”。我在面试的时候#xff0c;常常会问数组和链表的区别#xff0c;很多人都回答说#xff0c;“链表适合插入、删除#xff0c;时间复杂度O(1)#xff1b;数组适合查找#xff0c;查找时间复杂度为O(1)”。
实际上#xff…1. 常见的错误
这里我要特别纠正一个“错误”。我在面试的时候常常会问数组和链表的区别很多人都回答说“链表适合插入、删除时间复杂度O(1)数组适合查找查找时间复杂度为O(1)”。
实际上这种表述是不准确的。数组是适合查找操作但是查找的时间复杂度并不为O(1)。即便是排好序的数组你用二分查找时间复杂度也是O(logn)。所以正确的表述应该是数组支持随机访问根据下标随机访问的时间复杂度为O(1)。
2. 插入的优化
数组插入操作是O(n)但某些情况可以优化
如果数组中的数据是有序的我们在某个位置插入一个新的元素时就必须按照刚才的方法搬移k之后的数据。但是如果数组中存储的数据并没有任何规律数组只是被当作一个存储数据的集合。在这种情况下如果要将某个数据插入到第k个位置为了避免大规模的数据搬移我们还有一个简单的办法就是直接将第k位的数据搬移到数组元素的最后把新的元素直接放入第k个位置。为了更好地理解我们举一个例子。假设数组a[10]中存储了如下5个元素abcde。
我们现在需要将元素x插入到第3个位置。我们只需要将c放入到a[5]将a[2]赋值为x即可。最后数组中的元素如下 abxdec
利用这种处理技巧在特定场景下在第k个位置插入一个元素的时间复杂度就会降为O(1)。这个处理思想在快排中也会用到我会在排序那一节具体来讲这里就说到这儿。
3. 删除操作的优化
跟插入数据类似如果我们要删除第k个位置的数据为了内存的连续性也需要搬移数据不然中间就会出现空洞内存就不连续了。
和插入类似如果删除数组末尾的数据则最好情况时间复杂度为O(1)如果删除开头的数据则最坏情况时间复杂度为O(n)平均情况时间复杂度也为O(n)。
实际上在某些特殊场景下我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行删除的效率是不是会提高很多呢
我们继续来看例子。数组a[10]中存储了8个元素abcdefgh。现在我们要依次删除abc三个元素。 为了避免defgh这几个数据会被搬移三次我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据只是记录数据已经被删除。当数组没有更多空间存储数据时我们再触发执行一次真正的删除操作这样就大大减少了删除操作导致的数据搬移。
如果你了解JVM你会发现这不就是JVM标记清除垃圾回收算法的核心思想吗没错数据结构和算法的魅力就在于此 很多时候我们并不是要去死记硬背某个数据结构或者算法而是要学习它背后的思想和处理技巧这些东西才是最有价值的。如果你细心留意不管是在软件开发还是架构设计中总能找到某些算法和数据结构的影子。
4.为什么大多数编程语言中数组要从0开始编号而不是从1开始呢
如果数组从1开始计数那我们计算数组元素a[k]的内存地址就会变为
a[k]_address base_address (k-1)*type_size
从1开始编号每次随机访问数组元素都多了一次减法运算对于CPU来说就是多了一次减法指令。
不过我认为上面解释得再多其实都算不上压倒性的证明说数组起始编号非0开始不可。所以我觉得最主要的原因可能是历史原因。
C语言设计者用0开始计数数组下标之后的Java、JavaScript等高级语言都效仿了C语言或者说为了在一定程度上减少C语言程序员学习Java的学习成本因此继续沿用了从0开始计数的习惯。实际上很多语言中数组也并不是从0开始计数的比如Matlab。甚至还有一些语言支持负数下标比如Python。
5.总结
作为高级语言编程者是不是数组就无用武之地了呢当然不是有些时候用数组会更合适些我总结了几点自己的经验。
1.Java ArrayList无法存储基本类型比如int、long需要封装为Integer、Long类而Autoboxing、Unboxing则有一定的性能消耗所以如果特别关注性能或者希望使用基本类型就可以选用数组。
2.如果数据大小事先已知并且对数据的操作非常简单用不到ArrayList提供的大部分方法也可以直接使用数组。
3.还有一个是我个人的喜好当要表示多维数组时用数组往往会更加直观。比如Object[][] array而用容器的话则需要这样定义ArrayListArrayList array。
我总结一下对于业务开发直接使用容器就足够了省时省力。毕竟损耗一丢丢性能完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发比如开发网络框架性能的优化需要做到极致这个时候数组就会优于容器成为首选。
