讨论下这几种算法[寻高效的算法]

cobras

这里的什么线段树是什么？是在数据插入时的排序算法吗？

Susake_

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

   

Kurosaki_Ichigo

回复 18# ID好难

ID好难 发表于 2014-09-10 15:13
回复 15# Kurosaki_Ichigo

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

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

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

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

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

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

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

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

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

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

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

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

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

ID好难

回复 23# Kurosaki_Ichigo


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

Susake_

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

1. 
   
2. #include <bits/stdc++.h>
   
3. #include <ext/pb_ds/assoc_container.hpp>
   
4. #include <ext/pb_ds/priority_queue.hpp>
   
5. #include <ext/pb_ds/tree_policy.hpp>
   
6. #include <ext/pb_ds/trie_policy.hpp>
   
7. 
   
8. std::priority_queue <int> pr_q;__gnu_pbds::trie <std::string, int> trie_t;
   
9. __gnu_pbds::tree <int, int, std::less<int>, __gnu_pbds::splay_tree_tag, __gnu_pbds::tree_order_statistics_node_update> sp_t;
   
10. __gnu_pbds::priority_queue<std::pair <int, int>,std::greater<std::pair <int, int> >, __gnu_pbds::pairing_heap_tag > pa_h;
    
11. 
    
12. int main(int argc, char *argv[])
    
13. {
    
14.     sp_t[1] = 1;///0下标,为1的有一个
    
15.     sp_t[2] = 1;///1下标,为2的有一个
    
16.     sp_t[3] = 2;///2下标,为3的有两个
    
17.     sp_t[5] = 1;///3下标,为5的有一个
    
18.     int sum = 0;
    
19.     int key = 5;///查询比key大的个数
    
20.     for(int i = sp_t.order_of_key(key) + 1; i < sp_t.size(); i++)///从查找的元素的后一个序列开始
    
21.         sum += sp_t[sp_t.find_by_order(i) -> first];
    
22.     printf("%d\n", sum);
    
23.         return 0;
    
24. }
    

复制代码