2062: время машин. Тоби Уолш
тридцать – в миллиард. То есть можно с уверенностью сказать, что однажды компьютеры будут владеть такой вычислительной мощностью, что мы сможем делать с их помощью все, что захотим? К сожалению, это предположение далеко от правды.
Ученые разработали серьезную теорию вычислительной сложности. Она описывает, сколько вычислений нужно, чтобы решить разные проблемы конкретным или абстрактным способом. Для теории вычислительной сложности не имеет значения, какой именно компьютер используется. Это может быть персональный компьютер, смартфон или умные часы. Разница в устройстве обусловливает только разницу во времени выполнения задачи, ее постоянный коэффициент. То, что нас интересует, касается гораздо больших изменений во времени выполнения, чем постоянный коэффициент задачи. Для нас важен экспоненциальный рост, и, как мы увидим в дальнейшем, даже больше, чем экспоненциальный.
Допустим, вы хотите вычислить наибольшее число в списке. Это – линейная проблема. Вам необходимо просканировать весь список. Этот процесс займет время, пропорциональное количеству входных данных, то есть объему списка. Если список удвоить, это займет в два раза больше времени. Если утроить – в три раза.
А теперь представим, как можно упорядочить этот список – от меньшего к большему. Простейший метод заключается в том, чтобы найти для начала меньший пункт; как мы только что выяснили, это займет пропорциональное объему списка время. Затем необходимо найти предпоследнюю по величине вещь и т. д. В итоге время, которое нужно потратить на сортировку этого или любого другого списка, увеличивается в геометрической прогрессии. Если удвоить длину списка, это займет в четыре раза больше времени. Если утроить – в девять раз. Если учетверить – в шестнадцать. Звучит так себе. Однако вычисления могут масштабироваться еще хуже.
Существуют такие вычислительные проблемы, в которых время выполнения растет экспоненциально вместе с объемом входных данных. Представьте себе такую задачу: супруги при разводе хотят поделить свое имущество на две равноценные части. Простейший метод решения – это высчитать сумму каждой возможной комбинации вещей. Если стоимость одной из таких комбинаций равна половине стоимости всего имущества, то ответ найден. Каждый раз к входным данным – списку вещей – прибавляется одна единица, количество комбинаций, которые надо учитывать, удваивается, как и (в худшем случае) время выполнения алгоритма.
Хорошие новости заключаются в том, что экспоненциальный рост вычислительной мощности поможет решить подобные проблемы. Каждое удвоение мощности позволит выполнить задачу, в которой на одну вещь больше. Каков бы ни был объем входных данных, в конце концов он попадет в этот диапазон. Для того чтобы обработать информацию, включающую в себя на десять единиц больше возможного, нужно просто подождать еще десять поколений компьютеров.
Однако есть и вычислительные задачи, в которых время выполнения увеличивается быстрее. В таком случае экспоненциальный рост не спасет.