一文了解数组

数据结构算法入门系列的第二篇,这次介绍下数组, 数组是一个最基础而且常见的数据结构,几乎每种编程语言都有。

上一篇文章:

数据结构算法入门--一文了解什么是复杂度

今日推荐阅读:

深度学习在推荐系统中的应用


如何实现随机访问

数组的定义:

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。 ”

这里指出了数组的三个特点:

  1. 线性表(Linear List)
  2. 连续的内存空间
  3. 存储相同类型数据

首先,线性表就是数据排成一条线一样的结构,每个线性表最多只有前后两个方向,线性表结构如下图所示,数组、链表、队列和栈都属于这种结构

和线性表对立的就是非线性表,比如二叉树、堆、图等,它们不仅仅是简单的前后关系,如下图所示:

接着就是需要连续内存空间和保存相同类型的数据。这两个特点让数组有一个非常好的特性:随机访问。也就是根据下标访问数组的时间复杂度是 O(1) ,但问题就是插入和删除需要 O(n),因为需要进行大量的数据移动操作。

那么数组是如何实现随机访问的操作的呢?

首先,给定一个长度为 10 的 int 类型的数组 a[10] ,计算机会分配一块存储空间,这里假设就是 1000~1039 ,其中内存块的首地址是 base_address=1000,如下图所示

计算机给每个内存单元分配一个地址,然后通过地址访问内存中的数据。因此,这里如果需要随机访问数组的某个元素,同样也是根据地址访问,也就是首先需要找到该元素存储所在的地址,寻址公式如下所示:

a[i]_address = base_address + i * data_type_size

data_type_size 表示数组每个元素的大小,这里 int 类型是 4 个字节。

注意,对于数组来说,它支持随机访问,根据下标随机访问的时间复杂度是 O(1) ,但查找时间复杂度并非是 O(1) , 因为即便排好序的数值,通过二分查找,时间复杂度是 O(logn)

低效的插入和删除

数组的插入和删除操作由于其内存数据的连续性问题,这两个操作会非常低效,那么为什么会导致低效,有哪些改进方法呢?

插入操作

假设数组长度是 n ,现在需要将一个数据插入到数组的第 k 位置,如果需要执行这样的操作,需要将第 kn 位置上的元素都按顺序往后移动一位。这个操作的时间复杂度是多少呢?

最好的情况,就是末尾插入元素,这样不需要移动,O(1) 复杂度;最坏的情况,数组开头就插入元素,那么就是 O(n) 的时间复杂度。平均情况时间复杂度则如下所示,每个位置插入元素概率是相同的:

当然,如果数组是有序的,就需要按照上述做法移动元素。如果数组无序呢,一个快速的方法就是仅移动目标位置的元素,即第 k 个位置的元素放到数组末尾,然后插入元素即可,这样时间复杂度就是 O(1)

一个简单的例子如下图所示,数组有 5 个元素:a,b,c,d,e,现在希望在第三个位置插入新元素 x,此时可以直接将 c 放到末尾,即 a[5] = a[2],然后 a[2]=x,即可完成操作。

这种特殊的处理技巧,可以在特定场景下(比如数组无序)将插入元素的时间复杂度降到 O(1)

删除操作

和插入数据类似,删除第 k 个位置元素,同样需要将后续的元素往前移动。

  • 最好的情况是删除末尾数据,O(1)
  • 最坏就是删除开头的元素,O(n)
  • 平均情况时间复杂度也是 O(n)

同样在某些特定场景下,并不需要时刻追求数组中数组的连续性,可以将多次删除操作集中在一起进行操作。

如下图所示是一个长度为 10 的数组,存储了 8 个元素,`现在是需要依次删除前三个元素,a,b,c。如果每次删除操作都将所有元素往前移动,那么后续的 5 个元素总共需要移动 3 次,为了避免这个情况,我们可以先记录被删除的数据,每次操作仅仅记录那个位置的元素被删除。当数组没有空间存储数据时,再进行一次真正的删除操作,这样可以避免删除操作导致的数据搬移。

这个做法其实就是 Java 中 JVM 标记清除垃圾回收算法的核心思想。

所以,我们对于数据结构和算法的学习,不应该只是死记硬背,而是需要了解它背后的思想和处理技巧,明白为什么需要这种数据结构和这种算法。

数组的越界问题

首先来看一段 C 语言的代码,如下所示:

int main(int argc, char* argv[]){    int i=0;    int arr[3] = {0};    for(; i<=3; i++){        arr[i] = 0;        printf("hello world\n")    }    return 0;}

这段代码的问题就是打印结果的时候,因为循环结束条件问题,会无限打印 "hello world",给定的数组长度是 3, 但是循环结束条件是 i<=3 ,而 a[3] 其实就是访问越界了。

但是,在 C 语言中,只要不是访问受限的内存,所有的内存空间都是可以自由访问的。也就是说,a[3] 也是可以访问的,但是会定位到非数组所在的内存上,而这个地址正好是存储变量 i 的内存地址,也就是 a[3]=0 就相当于 i=0 ,最终导致代码的无限循环。

数组越界在 C 语言中是一种未决行为,没有规定这种情况编译器应该如何处理,所以通常会出现各种奇怪的逻辑错误。

不过,其他编程语言并不会将数组越界的工作丢给程序员来做,它们会有做越界的检查。

数组索引从 0 开始的原因

大多数的编程语言中,数组,或者说数据结构,索引都是从 0 开始,而不是从 1 开始。

首先,从数组存储的内存模型上看,索引,或者说“下标”最确切的定义应该是偏移(offset)

前面介绍了数组的寻址公式:

a[i]_address = base_address + i * data_type_size

如果数组是从 1 开始计数,那么寻址公式就会为:

a[i]_address = base_address + (i-1) * data_type_size

对比两个公式,可以知道每次访问数组元素,从 1 开始计数的方式会多一次减法运算,相当于让 CPU 多一次减法指令,但随即访问数组元素应该是非常基础的操作,需要尽可能高效,因此,为了减少一次减法操作,数组采用从 0 开始计数,而非从 1 开始。

其次,主要是 C 语言设计者用 0 开始计数,后续的编程语言,如 Java 等都效仿了 C 语言,这也是方便 C 语言程序员学习其他语言的学习成本。当然,像 Python 还支持负数下标。

本文分享自微信公众号 - 算法猿的成长(AI_Developer),作者:kbsc13

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 来了解下计算机视觉的八大应用

    之前通过三篇文章简单介绍了机器学习常用的几种经典算法,当然也包括了目前很火的 CNNs 算法了:

    材ccc
  • 关于春招 & 秋招面试的一些经验

    周末了,就不写技术了,来聊聊关于春招/秋招面试的事情,刚好最近也是逐渐开始春招找实习或者找工作的时候了,我就介绍一些当初准备春招实习和秋招工作面试的一些经验吧,...

    材ccc
  • Python基础入门_2基础语法和变量类型

    Python 基础入门系列第二篇,上一篇简单介绍了为什么用 Python,以及安装和配置环境。

    材ccc
  • 数组基础知识: 100万成员的数组取第一和最后一个有性能差距吗?

    数组几乎可以是所有软件工程师最常用到的数据结构,正是因为如此,很多开发者对其不够重视.

    帅地
  • Shell 数组

    Shell中数据类型不多,比如说字符串,数字类型,数组。数组是其中比较重要的一种,同时Shell中的数组不像JAVA/C,只能是一维数组,没有二维数组;数组元素...

    企鹅号小编
  • Java基础系列(五):数组

    在Java中,有一种数据结构叫做数组,它用来存储同一类型的值的集合。通过一个整型下标可以访问数组中的每一个值。例如,如果a是一个整型数组,那么a[i]就是数组中...

    Vi的技术博客
  • 探究JS V8引擎下的“数组”底层实现

    JavaScript 中的数组有很多特性:存放不同类型元素、数组长度可变等等,这与数据结构中定义的数组结构或者C++、Java等语言中的数组不太一样,那么JS数...

    2020labs小助手
  • 13 个 JS 数组精简技巧,一起来看看。

    数组是 JS 最常见的一种数据结构,咱们在开发中也经常用到,在这篇文章中,提供一些小技巧,帮助咱们提高开发效率。

    前端小智@大迁世界
  • 数组是如何随机访问元素?数组下标为什么从0开始,而不是1?

    数组(Array)是一种线性表数据结构,它用一组连续的内存空间,来存储相同类型的数据。

    搜云库技术团队
  • Java--数组

    SuperHeroes

扫码关注云+社区

领取腾讯云代金券