s********x
发帖数: 914 | 1 比如quick sort吧。
如果用Parallel threads把array分成几个section来sort，应该比nlog(n)更快吧。这
样不是很多interview问题就不是最优解了吗？ |
h*******e
发帖数: 1377 | 2 如果量子计算机的话np难度问题 都会降低复杂度。。 |
A*****i
发帖数: 3587 | 3 什么是量子计算机？天天听人说一直很好奇
【在 h*******e 的大作中提到】
: 如果量子计算机的话np难度问题 都会降低复杂度。。
|
b*****u
发帖数: 648 | 4 那不就是merge sort么
【在 s********x 的大作中提到】
: 比如quick sort吧。
: 如果用Parallel threads把array分成几个section来sort，应该比nlog(n)更快吧。这
: 样不是很多interview问题就不是最优解了吗？
|
s********x
发帖数: 914 | 5 是啊，但是paralellized不就可以超过nlog(n)吗。一般的merge sort是sequential的。
【在 b*****u 的大作中提到】
: 那不就是merge sort么
|
f******k
发帖数: 43 | 6 多线程来做无非就是复杂度除以线程数，不会改变复杂度级别吧，还是nlog(n)吧，除非
生成的线程数是和n相关的
是啊，但是paralellized不就可以超过nlog(n)吗。一般的merge sort是sequential的。
【在 s********x 的大作中提到】
: 是啊，但是paralellized不就可以超过nlog(n)吗。一般的merge sort是sequential的。
|
s********x
发帖数: 914 | 7 最终看的是running time吧，不是理论上的复杂度
除非
的。
【在 f******k 的大作中提到】
: 多线程来做无非就是复杂度除以线程数，不会改变复杂度级别吧，还是nlog(n)吧，除非
: 生成的线程数是和n相关的
:
: 是啊，但是paralellized不就可以超过nlog(n)吗。一般的merge sort是sequential的。
|
f*******t
发帖数: 7549 | |
S********o
发帖数: 4 | 9 在一台机器下，非多核的情况下用多线程不会有改善。
并行没有解决算法的复杂度，只是把任务分解给多机器或多CPU去处理而已。
【在 s********x 的大作中提到】
: 比如quick sort吧。
: 如果用Parallel threads把array分成几个section来sort，应该比nlog(n)更快吧。这
: 样不是很多interview问题就不是最优解了吗？
|
