假设我编写了一个程序，其中包含一个具有指数运行时间的算法，然后通过一个足够大的数据集运行该程序，该数据集多年都无法完成。
电脑会发生什么？会被锁吗？它会以 100% 的容量运行，直到它完成或电源关闭？硬件在完成之前会失败吗？
如果您还没有猜到，我正在做有关时间复杂度的作业。这不是家庭作业问题。这只是我的一个随机想法。
问问题
256 次
3 回答
3
电脑会发生什么？
它将运行算法直到完成[或出现意外错误]
会被锁吗？
这取决于算法是如何实现的——但通常——“程序”可能会冻结，但计算机仍然能够工作[可能更慢]，特别是如果机器是多核的。
它会以 100% 的容量运行，直到它完成或电源关闭？
如果算法是串行实现的，并且机器是多核的 - 它不会以 100% 的容量运行。如果它是多线程的 - 它可能会。
硬件在完成之前会失败吗？
对于需要2^n操作的算法，以及n=1000[对于现代现有机器] - 它很可能会 [在它完成之前地球不会在这里]。但是没有任何保证。
Important: The problem with exonential problems is not their effect on machines, this is not the problem with them. The problem is they take a long time. how long? well, for O(n!) algorithm [naive TSP implementation], for n == 20, the run-time is ~decade. increase n by one, just a small change in the problem size - and you get ~200 years run time! an extra addition will make it ~4000 years... [again, assuming modern present machine, and for c the constant for O(n!) c >= 1
于 2012-03-29T00:44:48.163 回答
1
这取决于。
但是想象一台硬件永远不会出现故障的理论计算机，那么您当然可以设计出可以运行很长时间的算法。就像，直到宇宙热寂很久。
没有什么特别的原因会因为长时间运行而锁定计算机，尽管典型操作系统中可能存在错误，这些错误会在长时间运行后导致问题。
于 2012-03-29T00:41:12.553 回答
0
“时间复杂度”只是获得结果所需的某种时间度量。因此计算机将继续执行，直到它不会以某种方式停止 - 通过 Ctrl^C 或停电。
于 2012-03-29T00:40:41.247 回答