免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123
最近访问板块 发新帖
楼主: Susake_

[算法] 讨论下这几种算法[寻高效的算法] [复制链接]

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-09-10 16:18 |显示全部楼层
这里的什么线段树是什么?是在数据插入时的排序算法吗?

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-10 16:42 |显示全部楼层
本帖最后由 Susake_ 于 2014-09-10 16:42 编辑

回复 21# cobras
你百度一下BST(二叉排序树),很多其他的变形都是基于它的,那些我也不懂~

   

论坛徽章:
1
亥猪
日期:2014-09-10 11:43:17
发表于 2014-09-10 18:57 |显示全部楼层
回复 18# ID好难
ID好难 发表于 2014-09-10 15:13
回复 15# Kurosaki_Ichigo

我说的是可以用线段树,并且它可以处理动态插入查询的情况。这个问题应该也可以用树状数组来写
    呵呵,成约架了。。。不至于,你太认真了。。。

约架?你想多了。因为我确定你写不来只是痛快痛快嘴瞎出主意。我呢最多算是吓唬吓唬你,让你别再瞎说而已。

本不想表现的这么强势,你们如果是刚接触相关算法想借这个题目练练手,或者讨论相关思路想法,我是不会干预的。但讨论就要有个讨论的态度,不要将自己的猜想说的言之凿凿(我就不再往重了说了)。我及其反感此类行为。

如果准备练手就实实在在写点代码,尤其玩算法,从理论到实践还是有一定差距的,需要通过多动手来提高算法的应用能力。

最后关于这第一题说两句。

对于元素集是先给出的情况,如果查询次数很少(少于元素总数的对数)那么直接遍历对比就好,效率是最高的,每一次查询的时间复杂度是O(n)。

如果查询次数比较多,那排序后二分检索是最佳方案。实现很简单,排序的复杂度是O(nlog(n)),每次查询的复杂度是O(log(n))。注:这里的log(n)是以2为底的。

当然用二叉排序树也可以,但算法的实现难度要高一些,效率相对低上述大部分情况下要低。

要想达到上述算法的效率水平,关键在于树的平衡调整,这时该叫AVL树了。

还可以用红黑树,当然实现难度更高。

如果元素集是动态的,随机出现插入、查询,甚至删除操作,那这时优先考虑树型结构。

但无论哪个都用不着线段树。非要套用我也拦不住,不过是浪费着内存当排序树使而已。

敲完这么多字反观开始的部分感觉话说的重了些,不想改了,也不想说什么见谅之类的虚伪客套话。总之希望大家以一个正确的态度探讨。

论坛徽章:
0
发表于 2014-09-10 21:01 |显示全部楼层
回复 23# Kurosaki_Ichigo


    。。。你是学生吧,戾气这么重

论坛徽章:
11
巨蟹座
日期:2013-12-23 11:12:14双子座
日期:2014-08-28 09:14:55子鼠
日期:2014-07-25 16:21:22摩羯座
日期:2014-07-23 15:17:47摩羯座
日期:2014-05-30 13:09:05午马
日期:2014-04-30 18:10:00天秤座
日期:2014-04-25 12:12:00申猴
日期:2014-04-22 11:30:15午马
日期:2014-03-07 16:06:40辰龙
日期:2013-12-25 18:36:00摩羯座
日期:2014-09-02 17:00:55
发表于 2014-09-10 21:05 |显示全部楼层
本帖最后由 Susake_ 于 2014-09-10 21:36 编辑

回复 24# ID好难
他不是学生~
顺便发段代码,数据结构形式没搞出来,不过扩展库里面的貌似弄出来了

  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/priority_queue.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. #include <ext/pb_ds/trie_policy.hpp>

  6. std::priority_queue <int> pr_q;__gnu_pbds::trie <std::string, int> trie_t;
  7. __gnu_pbds::tree <int, int, std::less<int>, __gnu_pbds::splay_tree_tag, __gnu_pbds::tree_order_statistics_node_update> sp_t;
  8. __gnu_pbds::priority_queue<std::pair <int, int>,std::greater<std::pair <int, int> >, __gnu_pbds::pairing_heap_tag > pa_h;

  9. int main(int argc, char *argv[])
  10. {
  11.     sp_t[1] = 1;///0下标,为1的有一个
  12.     sp_t[2] = 1;///1下标,为2的有一个
  13.     sp_t[3] = 2;///2下标,为3的有两个
  14.     sp_t[5] = 1;///3下标,为5的有一个
  15.     int sum = 0;
  16.     int key = 5;///查询比key大的个数
  17.     for(int i = sp_t.order_of_key(key) + 1; i < sp_t.size(); i++)///从查找的元素的后一个序列开始
  18.         sum += sp_t[sp_t.find_by_order(i) -> first];
  19.     printf("%d\n", sum);
  20.         return 0;
  21. }
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP