lxmfly123
V2EX  ›  问与答

关于《算法》(第 4 版)中对算法性能的均摊分析的疑问

  •  
  •   lxmfly123 · Jul 13, 2016 · 2451 views
    This topic created in 3590 days ago, the information mentioned may be changed or developed.

    1.4.8.5 中所述:(对于算法 1.1 ,即动态调整数组大小的下压栈)假设 N 是 2 的幂。如果数据结构初始为空, N 次连续的 push() 调用需要访问数组元素 N + 4 +8 + 16 + ... + 2N = 5N - 4 次。而程序计数的结果却如下:

    N: 1 counter: 1

    N: 2 counter: 2

    N: 4 counter: 10

    N: 8 counter: 26

    N: 16 counter: 58

    N: 32 counter: 122

    N: 64 counter: 250

    N: 128 counter: 506

    N: 256 counter: 1018

    算法 1.1 链接 http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/ResizingArrayStack.java.html

    请指点。

    Supplement 1  ·  Jul 13, 2016

    已解决!

    新建长度为 n 的数组,也是对数组元素访问了 n 次,少数了。

    yemenchun1
        1
    yemenchun1  
       Jul 13, 2016
    ![教授上课的截图]( )

    教授为啥算的~3n?

    我算的为什么是 5n-2 = n(n 个新元素) + 2n-1(翻倍时复制旧数组) + 2n-1(翻倍时找新数组的位置)呀?

    什么样算访问一次数组?
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   3285 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 14:11 · PVG 22:11 · LAX 07:11 · JFK 10:11
    ♥ Do have faith in what you're doing.