java - Why is deletion of an item at end of Dynamic array O(n) time complexity?
问题描述
I am currently reading my textbook and I am totally confused why a dynamic array would require O(n) time to delete an item at the end. I understand that deleting an item from any other index is O(n) because you have to copy all the data and move them to fill in the gap, but if it’s at the end don’t we simply just decrement the count and set the index to like 0 or null? I included a picture from my book. It’s weird cause it says indexing is O(1) so we must know where the item is so we don’t have to traverse the array like a linked list.
解决方案
First, let's look up what the books means with a "Dynamic Array":
Dynamic array (also called as growable array, resizable array, dynamic table, or array list) is a random access, variable-size list data structure that allows elements to be added or removed. [...]
Note: We will see the implementation for dynamic array in the Stacks, Queues and Hashing chapters.
From this we learn that array lists are examples of a "Dynamic Array" as the author of the book defines it.
But looking further, the book mentioned that:
As soon as that array becomes full, create the new array of size double than the original array. Similarly, reduce the array size to half if the elements in the array are less than half.
(emphasis added by me)
A Java ArrayList
doesn't do this - it doesn't decrease in storage when elements are removed. But the author is talking about (or believes that ArrayList
does) reduce the array size.
In that case, from a worst-worst-case perspective, you could say that the complexity is O(n)
because reducing the size involves copying n
elements to the reduced array.
Conclusion:
Although it's not true for Java ArrayList
implementations, when the author of this book talks about "dynamic arrays" that "reduce the array size" on deletion when necessary, then the worst-case complexity of a delete at the end of the array is indeed O(n)
.
推荐阅读
- qt - 带有 QT 的 HTTP 请求错误,但带有 CURL 的请求良好
- reactjs - 如何在 React 中从 Contentful 渲染参考字段?
- c# - MVVMHelpers AsyncCommand await 无法正常工作
- spring-boot - 重复订阅标识符 STOMP
- sql - 将新列和变量行添加到 SQL 选择查询作为输出并在其中执行算术运算
- c++ - C/C++ 跨平台 Timer As csharp System.Threading.Timer no boost 或其他
- flutter - 如何使用 CustomPainter 绘制形状以及每个函数的值如何工作?(又名cubicto beziers quadraticbezier等)
- c - 在 cmd 中打印和存储西班牙语字符(á、é、í、ñ...)
- python - 使用 Django Abstract User 时密码没有被散列
- asp.net - 如何访问共享项目中的自动映射器配置文件?