Каковы результаты экспоненциальной работы на компьютере?

Question

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

Что будет с компьютером? Будет ли это запереть? Будет ли он работать на 100% мощности, пока он не завершит работу или не отключится питание? Произойдет ли сбой оборудования до его завершения?

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

Answer 1

Что будет с компьютером?

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

Будет ли он заблокирован?

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

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

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

Произойдет ли сбой оборудования до его завершения?

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

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

Answer 2

Зависит.

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

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

Answer 3

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