数组各种操作的时间复杂度_查找数组元素时间复杂度

作者：代码探险家 | 2024-07-29 21:20:52

踩

查找数组元素时间复杂度

假如我们想要访问索引为 2 处的元素时，计算机会进行以下计算：
找到该数组的索引 0 的内存地址： m；
将内存地址加上索引值，作为目标元素的地址，即m+2，对应的元素为 “X”，这时便找到了目标元素。
我们知道，计算内存地址这个过程是很快的，而我们一旦知道了内存地址就可以立即访问到该元素，因此它的时间复杂度是常数级别，为 O(1)

查找元素
与读取元素类似，由于我们只保存了索引为 0 处的内存地址，因此在查找元素时，只需从数组开头逐步向后查找就可以了。如果数组中的某个元素为目标元素，则停止查找；否则继续搜索直到到达数组的末尾。最坏情况–末尾是目标元素或者数组中不包含目标元素，时间复杂度O（n）

删除元素
一个意思，如果删除掉一个元素，他之后的元素都会发生改变。最坏情况是删除第一个，操作了1+n-1，时间复杂度O（n）
插入元素
和删除类似

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】