存不存在解决一个问题的算法集,当算法使用的线程数量增加时时间复杂度将大幅度减小?

对于一个问题,存在一个解决这个问题的算法集{Ln}n是自然数,其中Ln是一个使用n个线程的算法。但是,当n趋于无穷大时,算法Ln所需要耗费的时间Tn近似地等于K*n^(-s),其中K是常数,s>1?

我们知道,一般来讲一个程序的执行耗时与线程数量大致成反比,这就类似于n个人盖房子的效率是一个人的n倍,但是有没有可能不止快n倍,而是快n²倍,甚至e^n倍?

假如多线程一定可以用单线程用用线性的时间模拟的话,那么就不存在这种情况了。但是有没有可能设计一种计算机模型,它的多线程程序无法用单线程在线性时间内模拟?

还有一个问题,退一步,是否存在一个算法集{Ln},其中算法Ln消耗的空间是n A个单位,程序总耗时是Tn,当n趋于无穷大时Tn近似地等于K*n^(-s),s>1?
已邀请:

要回复问题请先登录注册