关于字典树的时间复杂度

P8306 【模板】字典树

Compound_Interest @ 2022-07-20 09:17:18

字典树插入和查询都可以卡成O(n)

为什么这题能过

字典树的复杂度是什么

by rxjdasiwzl @ 2022-07-20 09:23:57

单次是 O(\text{串长})，不是 O(n)。

by Compound_Interest @ 2022-07-20 09:55:32

@rxjdasiwzl

构造每次都是长为n的串，卡成O(n)

by rxjdasiwzl @ 2022-07-20 10:49:08

@x17875487211

且输入字符串的总长度不超过 3 \times 10^6。

by _lfxxx_ @ 2022-07-26 17:12:01

楼主说的是最坏 O(n) 吧。