数据结构名称 | 时间复杂度(一般)(建立—修改—查询) | 时间复杂度(合并) | 时间复杂度(分裂) | 时间复杂度(分治) |
---|---|---|---|---|
数组 | \(\mathcal{O}(1)-\mathcal{O}(1)-\mathcal{O}(1)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) |
可持久化数组 | \(\mathcal{O}(1)-\mathcal{O}(\log n)-\mathcal{O}(\log n)\) | \(/\) | \(/\) | \(\mathcal{O}(n)\) |
\(\rm Hash\) 表 | \(\mathcal{O}(1)-\mathcal{O}(1)-\mathcal{O}(1)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) |
可持久化 \(\rm Hash\) 表 | \(\mathcal{O}(1)-\mathcal{O}(\log n)-\mathcal{O}(\log n)\) | \(/\) | \(/\) | \(\mathcal{O}(n)\) |
咕咕咕。。。