use*_*577 2 arrays algorithm complexity-theory search
我在考试中表示:
找到一种算法,该算法可以搜索未排序列表中的最大数字,并具有O(log(N))的Big-Oh复杂度.
我发现的唯一具有log n复杂性的搜索算法是二进制搜索算法,但是需要对我的列表/数组进行排序.
有这样的算法吗？
jxh*_*jxh 10
这是一个棘手的问题.尚未说明该清单有N个要素.所以,你可以使用变量的变化,并更换ñ与2 ķ.现在,在具有K个元素的列表上使用线性算法解决问题.
如果我们假设列表中有N个元素,则可能的解决方案是使用N个并行计算元素[ CE 0 .. CE N ].在算法的基本情况下,我们让[ CE N/2 ... CE N ]中的每个计算元素CE i比较列表值x 2i-N和x 2i-N + 1.每个计算元件将它们的两个指定值中较大的一个报告给CE i/2.该算法的迭代步骤是接收两个报告值的每个计算元件CE k向CE k/2报告最大值.该迭代逻辑继续,直到CE 0处理来自其自身的报告.它不是再次向自己报告,而是输出结果.
如果排除了并行计算,则问题无法解决.
| 归档时间： |
|
| 查看次数： |
10473 次 |
| 最近记录： |