划分和征服算法数值

如果使用随机快速排序算法对大小为n = 1000的文件进行排序需要10 ms，那么大约需要多长时间对大小为n = 1000000000的文件进行排序（假设所有数据在主存储器中可用）划分和征服算法数值

2015-07-19 Shiv KuMar

这可能属于math.stackexchange，因为它是一个数值计算问题，不以任何方式，除了表面上的任何方式。他们应该知道，快速排序的预计运行时间是Theta（n log n），如果不是那么只是告诉他们，他们应该没有问题帮助你。 – user2566092

你使用台式电脑吗？快速排序中的一个操作需要大约1微秒的时间，这太慢了。也许你的实现/时间测量有问题，或者排序需要二次时间。 – stgatilov

如果随机Quicksort的平均时间（或基本操作的数量）是O（n log（n））并且对于n = 10^3需要10ms，则意味着关系10 = t 10^3 log（10^3），其中t是操作持有的时间。根据以前的关系，您可以通过一次基本操作t = 10 /（10^3 log（10^3））ms获得计算机花费的时间。因此，以n = 10^9结束的时间为t 10^9 log（10^9）。用t = 10 /（10^3log（10^3））代替，您的计算机需要10 /（10^3log（10^3））10^9log（10^9）ms或10^7 9/3 ms。

是你在找什么？

来源

2015-07-19 20:34:52 marc1s

划分和征服算法数值

回答

相关问题