不会 @[鏡音リン](/space/show?uid=28913)
by Kiel @ 2018-10-15 23:12:20
@[something](/space/show?uid=84025) 能不能请您说明一下复杂度如何?
by Utsuji_risshū @ 2018-10-15 23:19:13
@[鏡音リン](/space/show?uid=28913) 你不是过了吗?
by Kiel @ 2018-10-15 23:21:11
O(n) 吧 @[鏡音リン](/space/show?uid=28913)
by Kiel @ 2018-10-15 23:25:01
@[something](/space/show?uid=84025) 不对
by Kiel @ 2018-10-15 23:25:18
map的查询和插入都是$\text{O}(\log n)$的。。。吧
by NaCly_Fish @ 2018-10-15 23:25:46
@[something](/space/show?uid=84025) 最多 O(n*文件夹个数)
by Kiel @ 2018-10-15 23:26:22
@[NaCly_Fish](/space/show?uid=115864) 我太弱了
by Kiel @ 2018-10-15 23:26:37
$O(\log n)$
by Anguei @ 2018-10-15 23:28:40
红黑树应该是比splay和treap都要快的二叉查找树,插入删除查找都是O(logn) 只是STL在不开O2的情况下普遍常数都比较大而已
但是如果你用map<string, ...>或者set<string>并且string的长度很大的话,意味着所有复杂度都要乘上字符串长度,因为平衡树肯定要频繁地比较元素大小,而string上的operator<复杂度是O(len)的
by GKxx @ 2018-10-15 23:32:27