为何某些版本的线段树的时间复杂度常数如此之大?
  • 板块学术版
  • 楼主Herman526
  • 当前回复15
  • 已保存回复16
  • 发布时间2023/11/26 08:48
  • 上次更新2023/11/26 10:39:40
查看原帖
为何某些版本的线段树的时间复杂度常数如此之大?
786834
Herman526楼主2023/11/26 08:48

众所周知,线段树、平衡树这一类树形数据结构,面对比较大的数据,时间复杂度常数会较大。然而,面对小数据,某些版本(比如我)的线段树时间复杂度的常数也大得明显。

在做 P1253 时,我便发现了这个问题。在本题中,有一组数据明显是放水的——n=q=1n=q=1,这个测试点,即使是暴力,也大概率可以在 3ms3\text{ms} 内搞定。而我的线段树,却花了 6ms6\text{ms} 才完成(开 O2 甚至更慢)。确实,线段树在回答询问前需要先进行较多的预处理,但是 n=1n=1 时,这种预处理的量是极少的,而回答所需的时间也很少。然而,提交记录中,却也有一些是花了 5ms5\text{ms} 以上才完成该组数据的。不过,我的线段树的总效率却还不错(如最后一个点可以在 1.2s1.2\text s 内完成)。除了该题,P3373 等也是如此。

大家知道这种“常数”是由什么引起的吗?有什么方法,能帮我们摆脱这些“常数”的困扰?

2023/11/26 08:48
加载中...