[求助] 关于一个算法的时间复杂度,请达人指点

【 在 lblz 的大作中提到: 】 : RT : 给出一个算法,要求时间复杂度为O(nlgn), 使之能在给定的一个由n个整数构成的集合S和另一个整数x时,判断出S中是否存在有两个其和等于x的元素. : ps: 我的想法是利用递归... 还望达人指点 算法导论..... lz注意这道题是2.3-7,但是2.3-5提到了二分查找，这是一个提示 我当时想到的就是用个 O(nlgn)的排序算法进行排序，然后针对每个元素 elem ,用二分查找 x-elem ,这个时间复杂度也是 O(nlgn)，所以总的时间复杂度是 O(nlgn)

re UnitTest。。。 先把S中的每个元素elem求x-elem。得到一个对应的集合S' 再判断两个集合的交集是否为空。

《编程之美》 2.12 节

【 在 UnitTest 的大作中提到: 】 : 算法导论..... : lz注意这道题是2.3-7,但是2.3-5提到了二分查找，这是一个提示 : 我当时想到的就是用个 O(nlgn)的排序算法进行排序，然后针对每个元素 elem ,用二分查找 x-elem ,这个时间复杂度也是 O(nlgn)，所以总的时间复杂度是 O(nlgn) 有道理,我当时就是只考虑到利用前面那个递归的O(nlgn),后面的没想到,看来还是基础不扎实啊

这本书见一次鄙视一次，弄了一些ACM的水题，讲的却不规范，很容易让人走火入魔 据说还要出新版，再次鄙视 【 在 UnitTest 的大作中提到: 】 : 《编程之美》 2.12 节

【 在 PtwCJ 的大作中提到: 】 : 这本书见一次鄙视一次，弄了一些ACM的水题，讲的却不规范，很容易让人走火入魔 : 据说还要出新版，再次鄙视 赞 屁涕，漫漫长夜，无心睡眠哈~~ 不过现在这些书，包括 算法导论在内 对我来说都是 面试宝典，没有区别 ，嗯嗯

Orz 马上睡去 各OJ也是面试题库... The C Puzzle Book据说是C的真正的面试宝典 还有《高效程序的奥秘》英文名是hacker什么的，我刚翻了两天就觉得受益匪浅 【 在 UnitTest 的大作中提到: 】 : 赞 屁涕，漫漫长夜，无心睡眠哈~~ : 不过现在这些书，包括 算法导论在内 对我来说都是 面试宝典，没有区别 ，嗯嗯

排序，从前向后、从后向前同时扫描一次即可

如果数字范围不大，那么有O(n)的算法。