- 可达家统计
UNORDERED_MAP 底层逻辑为哈希表。
- @ 2025-8-26 14:29:48
将 bool mp[N*N] 改为 unordered_map<int, bool> mp 后出现 Aborted(程序异常终止),核心原因是 时间效率不足导致超时,具体分析如下:
- 数据规模与操作复杂度对比 全局数组 mp[NN]: N=3005 时,NN≈9e6,数组大小为 9030025(3005×3005)。数组访问是 O (1) 时间,且内存连续,速度极快。 unordered_map<int, bool>: 哈希表的插入、查询操作平均时间是 O (1),但实际受 哈希冲突 和 动态内存管理 影响: 每次操作需要计算哈希值(如 hax(bel[v], bel[u])),并处理冲突链; 动态分配内存的 overhead 更高,频繁操作时耗时显著增加。
- 代码中的操作规模 在处理分量间边时,最坏情况(原图为完全图) 会遍历 N²≈9e6 条边。此时:
数组 mp 的访问是 9e6 次 O (1) 操作,耗时可忽略; unordered_map 的 9e6 次插入 / 查询 会因哈希计算、冲突处理和内存操作,导致总时间急剧上升,超过时间限制,最终被系统终止(Aborted)。 3. 解决方案 若需优化空间(如 N 更大时),可改用 bitset 或更紧凑的哈希结构,但在本题数据规模下:
优先保留全局数组 mp[N*N]:其时间效率最优,且 9e6 大小的 bool 数组仅占~9MB 内存(全局数组存放在数据段,空间充足)。
综上,unordered_map 的时间开销在大数据量下无法满足要求,导致程序超时终止。建议继续使用全局数组实现快速存在性判断。
0 条评论
目前还没有评论...
信息
- ID
- 345
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 83
- 已通过
- 14
- 上传者