Sid*_*Sid 1 algorithm big-o computer-science
我这个学期已经学过算法课程,我正试图解决CLRS中的一个问题
2.3-7描述一个theta(n lg n)时间算法,给定一组n个整数和另一个整数x,确定S中是否存在两个元素,其和是x.
我不知道如何处理这个问题.我试图使用合并排序算法解决它,因为它在nlogn时间内完成,但我不知道它是否是正确的方法.
任何人都可以告诉我在已经指定运行时间时解决算法时的一般方法是什么？
谢谢.
我怀疑对于这些问题有任何一般方法,例如在任何"建议算法"任务中.但是,所需的运行时可以暗示要使用的"构建块"(就像log通常表示需要树或排序数组一样).例如,您可以查看标签wiki中的'big-o',以获取每个所需运行时的算法示例.
针对您的问题的算法的想法:
首先,对array(O(n lg n))进行排序; 然后对于y数组的每个元素检查元素x-y是否存在(同样O(n lg n),因为数组已排序).