V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
XiiLii
V2EX  ›  程序员

数组索引的时间复杂度 O(1) 的本质是并行二分查找

  •  
  •   XiiLii · 2022-11-27 22:10:58 +08:00 · 1061 次点击
    这是一个创建于 711 天前的主题,其中的信息可能已经有所发展或是发生改变。

    上图是寻址逻辑电路,输入端 A 、B 共同组成 2 bit 的地址线,2 bit 的地址线可以表示 00 、01 、10 、11 这 4 个地址,它们分别位于输出端 Z 、Y 、X 、W ,通过地址线表示的二进制数就可以找到输出端中的不同地址(以后就可以对其进行读写操作了)

    也可以这样理解:输入端 A 、B 相当于两个开关,输出端 Z 、Y 、X 、W 相当于 4 个灯泡,两个开关的不同状态的组合就可以控制其中 1 个灯泡中的亮灭。

    接下来分析单一输入端:

    输入端 A 为 1 时,会选出输出端 X输出端 W

    输入端 A 为 0 时(经过非门会变成 1 ),会选出输出端 Z输出端 Y

    结论:不管输入端 A 是 0 还是 1 ,都会选出一半

    输入端 B 为 1 时,会选出输出端 W输出端 Y

    输入端 B 为 0 时(经过非门会变成 1 ),会选出输出端 X输出端 Z

    结论:不管输入端 B 是 0 还是 1 ,都会选出一半

    由于只有当与门同时为 1 时,输出端才会输出 1 。

    现在,当输入端 A输入端 B分别为 0 、1 时,输出端 Y就是输入端 A 、B 共同选出的地址。

    上图的红线为 1 (输入端 A 的 0 经过非门会将其之后的线路置为 1 )

    那它的时间复杂度是怎么样的呢?

    由于输入端 A 、输入端 B (比如地址 01 )是同时输入的,所以电路会进行并行的二分查找,一个输入端的一次二分查找是 O(1),所有的输入端并行,进行一次二分查找同样是 O(1)。

    以上是 2 bit 寻址,更多 bit 的寻址同样是并行进行的,所以时间复杂度同样是 O(1)。

    寻址的物理本质是并行二分查找,而数组索引就是在寻址,所以这就是为什么数组的时间复杂度是 O(1) 的原因。

    下图是 3 bit 寻址逻辑电路

    可以看到有 3 个输入端、8 个输出端。因为 3 bit 地址线的寻址空间大小是 2^3=8 。输入端越多,可以寻找的地址空间也就越大。

    当输入端有 32 bit 时,可以寻找的地址空间有 2^{32}=4294967296 个,它对应的内存空间是 4 GB ,这也就是为什么 32 位系统支持的最大内存是 4 GB 的原因了。

    64 位系统的寻址空间大小是 16 EB

    1 EB = 1024 PB

    melkor
        1
    melkor  
       2022-11-28 11:10:47 +08:00
    但是电路接通和断开何来「查找」呢?
    RecursiveG
        2
    RecursiveG  
       2022-11-28 12:46:52 +08:00
    可以这么理解,但没必要。
    yolee599
        3
    yolee599  
       2022-11-28 12:58:44 +08:00 via Android
    数组索引其实就是一条 ADD 指令
    maggch97
        4
    maggch97  
       2022-11-28 13:00:22 +08:00 via Android   ❤️ 1
    怎么不本质到电子的迁移
    XiiLii
        5
    XiiLii  
    OP
       2023-01-05 21:00:37 +08:00
    @maggch97 这里说的是逻辑,不局限于电子
    XiiLii
        6
    XiiLii  
    OP
       2023-01-05 21:03:01 +08:00
    @melkor 查找本质读取,哪个条路径接通就读取到哪个地址
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2759 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 13:49 · PVG 21:49 · LAX 05:49 · JFK 08:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.