首页 > 代码库 > 分块感想
分块感想
分块大法好
数据结构+算法=程序,这句话是个大神讲的。可见数据结构几乎占了算法题中的半壁江山。
数据结构的基本思想就是分块:树状数组是按其二进制表达来分块的,线段树是根据其区间长度分块……(将原序列分解为若干连续不想相交的子序列)
分块就被誉为“万能数据结构”,其思想个人认为比较好理解。 就是讲数据打包,对整个包的数据的询问可以直接预处理得出。修改包中的元素则需维护整个包的信息。(这是分块我认为最重要的两个性质(优缺点));但分块的大小不同于树状数组,线段树……(其块的大小不变)现在讨论一下块的大小多少合适:
设块的大小为m,有n个元素组成序列;则查询的时间复杂度:
对于整个块,每个块时间复杂度O(1)(不是O(1)以后讨论,结论不变)为O(n/m);
对于散块,就是每次查询最前面最后面多出的那些东东,为O(m)
所以查询总的时间复杂度为O(m)+O(n/m),由算术平均不等式得出m+(n/m)<=2sqrt(n)当且仅当m=n/m时成立
修改时结论不变
所以块的大小为sqrt(n)时时间复杂度最优
分块感想
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。