Каковы эффекты экспоненциального времени выполнения на компьютере?

Question

Предположим, что я написал программу, содержащую алгоритм, который имел экспоненциальную среду выполнения, а затем запускал программу через достаточно большой набор данных, в котором он не закончил годами.

Что произойдет с компьютером? Заблокирован ли он? Работает ли он на 100% до тех пор, пока он не закончится или питание не отключится? Не сработает ли оборудование до его завершения?

Я занимаюсь домашней работой по временной сложности, если вы уже не догадались. Это не вопрос домашней работы. Это просто случайная мысль.

Answer 1

Что произойдет с компьютером?

Он будет работать алгоритм, пока он не закончит [или есть неожиданная ошибка]

ли он запереть?

Это зависит от того, как алгоритм реализован, но обычно - «программа», вероятно, замерзнет, ​​но компьютер все равно сможет работать [возможно, медленнее], особенно если машина является многострочной.

Будет ли он работать при 100% -ной емкости, пока он не закончит работу или не отключится питание ?

Если алгоритм реализован серийно, а машина является многокорпусной - она ​​не будет работать на 100% -ной capcity. Если он многопоточен - он, вероятно, будет.

Не удалось ли аппаратное обеспечение завершить его?

для алгоритма, который нуждается в 2^n опа и n=1000 [для современных настоящие машины] - это, скорее всего, будет [земля не будет здесь, прежде чем это делается]. Но для этого нет никаких гарантий.

Важная информация: Проблема с эксонентными проблемами заключается не в их влиянии на машины, это не проблема с ними. Проблема в том, что они занимают много времени. сколько? ну, для O(n!) алгоритм [наивный TSP реализация], для n == 20, время выполнения ~ десятилетие.увеличьте n одним, просто небольшим изменением размера проблемы - и вы получите ~ 200 лет работы! дополнительное дополнение сделает его ~ 4000 лет ... [опять же, предполагая современную современную машину, а для c постоянная для O(n!)c >= 1

Answer 2

«Сложность времени» - это лишь некоторое время, необходимое для получения результата. Таким образом, компьютер продолжит выполнение до тех пор, пока он не будет остановлен каким-то образом - Ctrl + C или отключением.

Answer 3

От этого зависит.

Но представляя теоретический компьютер, где аппаратное обеспечение никогда не потерпит неудачу, тогда вы, безусловно, могли бы разработать алгоритмы, которые будут работать очень долгое время. Например, до жары смерти вселенной долгое время.

Нет особой причины, по которой компьютер должен блокироваться только из-за работы в течение длительного времени, хотя могут быть ошибки в типичных операционных системах, которые могут вызвать проблемы после очень длительных периодов работы.