知识卡片

普通读书笔记卡 · 3640.b

增强设计先核验维护成本

理解等级:高级

增强数据结构可按四个问题推进:

  • 底层结构是什么、
  • 要存什么附加信息、
  • 原有修改操作能否高效维护它、
  • 如何实现新操作。

第三问是可行性门槛,设计过程可往返迭代,不必机械按顺序完成。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第17章 数据结构的扩张 · 查看原书依据

      You can break the process of augmenting a data structure into four steps: Choose an underlying data structure. Determine additional information to maintain in the underlying data structure. Verify that you can maintain the additional information for the basic modifying operations on the underlying data structure. Develop new operations. As with any prescriptive design method, you’ll rarely be able to follow the steps precisely in the order given. Most design work contains an element of trial and error, and progress on all steps usually proceeds in parallel. There is no point, for example, in determining additional information and developing new operations (steps 2 and 4) if you cannot maintain the additional information efficiently.

    参考来源

    - 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[10000,15000))。 - 结论依据:原文依次列出底层结构、附加信息、基本修改操作的维护验证和新操作四步,并说明维护不够高效时其余设计无意义。 - 原始内容:You can break the process of augmenting a data structure into four steps: Choose an underlying data structure. Determine additional information to maintain in the underlying data structure. Verify that you can maintain the additional information for the basic modifying operations on the underlying data structure. Develop new operations. As with any prescriptive design method, you’ll rarely be able to follow the steps precisely in the order given. Most design work contains an element of trial and error, and progress on all steps usually proceeds in parallel. There is no point, for example, in determining additional information and developing new operations (steps 2 and 4) if you cannot maintain the additional information efficiently.