数据结构的意义

Vision271 · 2022-07-11 22:21:56 · 个人记录

• 本博客需要重构。计划重构成数据结构概述，内容为：

  • 什么是数据结构？

  • 为什么要有数据结构？

  • 我们如何运用数据结构？

• 在重构完毕前，您可以在评论区催更但不保证有效（笑）。

为什么要有数据结构？这是一个意义重大而深远的问题。

• 数据结构是数据的组织和存储方式。数组，链表，堆，栈，队列，块状xx，跳表，线段树，平衡树，...。数据的存储方式多种多样。

• 不同的存储方式，代表着不同的支持操作，和不同的时空复杂度。 取其中最有代表性的来说吧。

  • 数组是 O(1) 访问/修改，O(n) 插入/删除；

  • 链表则恰恰相反，访问/修改 O(n)，插入/删除 O(1)。

  • 而块状链表可以 O(\sqrt n) 地支持两种操作。

  • 据说跳表能均摊 O(\log) 地支持两种操作，不过没有见到广泛使用，也许太难写或者太均摊罢。

• 所以，我们根据题目的需要，采用一定的数据结构。

  • 或是放弃一部分操作的高效性，来加速题目所需操作的速度（如正常题目中不会用到块状链表，因为不需要插入/删除，我们只关心访问/修改）。

  • 或是以升高低复杂度操作的复杂度为代价，来降低复杂度瓶颈操作的复杂度，以获取更优的均摊复杂度（如块状链表的使用）。

  • 或是减小所需的空间（如主席树等的节点复用，广义来讲 dp 的压维/滚维也算）。

• 也有一些例外。

  • 有些时候，可持久化数据结构是回答在线问题的必要条件；

  • 可合并数据结构则能以美妙的时间复杂度犀利地解决某些棘手的难题。

  • 但这就不是数据结构的本质了——而是可持久化或合并的功劳。不过，它们也举足轻重。