Пример алгоритма, который слишком сложен по времени?
Сколько бы я ни искал в Интернете, я не могу найти примеры алгоритмов, которые на практике не разрешимы из-за количества времени, которое они затрачивают на вычисления.
Я пытался придумать пример, такой как подсчет числа, размера и местоположения каждой звезды, которая проходит ближе всего к ракетному кораблю во время его полета к альфа-центаврине. Это был бы хороший пример? Я имею в виду, звездная система находится на расстоянии около 26 триллионов миль.
РЕДАКТИРОВАТЬ: я делаю короткую презентацию о нотациях Big-O и Little-O и хотел бы придумать что-то необычное в отношении того, ПОЧЕМУ решения проблем могут быть решаемы на практике, но они не могут быть решаемы в принципе из-за чрезвычайно большое количество времени для вычисления, поэтому Big-O используется для создания оценок. Причина, по которой я хотел пойти со звездами, заключается в том, что это кажется более интересным, чем некоторые другие предметы.
Спасибо!
7 ответов
Представьте, что у вас есть массив, обозначающий колоду из 52 карт. [AS, 2S, 3S, ... , JH, QH, KH] и вы хотите вернуть все возможные способы перемешивания этих карт.
У первой карты 52 возможности, у второй 51, у третьей 50 и так далее. Всего существует 52 факторных (52 * 51 * 50 * ... * 3 * 2 * 1) комбинации, что превышает 10^67 (я думаю, что это близко к числу атомов во вселенной).
Многие сложные проблемы возникают из-за необходимости многократного использования одних и тех же данных, а не только из-за большого количества данных.
Вы должны определенно рассмотреть NP-сложные проблемы, такие как проблема коммивояжера. Это отличные обучающие примеры, потому что они могут быть "решены" с помощью различных стратегий, и мы все еще работаем над ними.
Как вы описываете, алгоритмы, гарантирующие правильный ответ, часто слишком ресурсоемки для реализации в реальной жизни. Благодаря Big O мы знаем, что O((n^2)*(2^n)) просто невозможно выполнить на машинах для входов приличного размера.
Мы вынуждены идти на компромисс с алгоритмами, которые работают лучше, но могут не дать лучший или правильный результат. Эти алгоритмические компромиссы можно увидеть на множестве реальных примеров из реальной жизни - один интересный пример - тур по 50 достопримечательностям США.
С использованием современных алгоритмов по состоянию на 2009 год потребовалось два года, чтобы рассчитать RSA-768, который имеет "только" 232 десятичных знака - и это было сделано с использованием нескольких компьютеров параллельно.
Можно предположить, сколько времени потребуется для расчета коэффициента RSA 2048, который имеет 617 десятичных цифр.
Немецкий хакер пытается войти на серверы АНБ, чтобы узнать коды запуска ядерных ракет. Он знает, что все пароли NSA должны содержать не менее 16 символов, пароль администратора генерируется случайным образом каждый день в полночь, и он может включать в себя все ASCII. У него есть 26 дней до начала Второй мировой войны.
Должен ли он попытаться спасти мир? или уйти в отпуск. Только большая нотация покажет.
Я надеюсь, что этот пример был "интересным".
Ваша проблема не удивительна, потому что, похоже, она имеет линейную сложность (O(n) время). Если вы удвоили продолжительность своей поездки, то время, необходимое для выполнения вашей программы, удваивается. Тем не менее, вы, вероятно, просто ищете проблему с экспоненциальным решением, например проблему коммивояжера, которая быстро становится практически неразрешимой по мере увеличения количества городов. Посмотрите Сложность времени для получения дополнительной информации.
Еще одна интересная вещь, которую вы можете попробовать посмотреть, это проблема остановки.
Основная цель нотации Big-Oh - не оценить время выполнения программы на каком-то конкретном входе. Необходимо проанализировать, насколько быстро программа замедляется при увеличении размера ввода. Требуется ли вдвое больший ввод для запуска, в четыре раза или в шестнадцать раз?
Самый наглядный пример для Big-Oh - это то, где задача имеет очень маленький вклад, но ее выполнение занимает много времени. И когда вы немного увеличиваете размер ввода, это занимает гораздо больше времени. Некоторые из наиболее быстро растущих алгоритмов занимают экспоненциальное или факториальное время, и они обычно включают просмотр всех перестановок элементов (всех различных порядков или способов расположения элементов).
Следовательно, хороший пример: кто-то установил на сейфе 10-значный код доступа (цифры от 0 до 9), и вы должны его угадать. Ну, есть 10^10 комбинаций, и вы догадаетесь в среднем 5*10^9 раз, прежде чем все сделаете правильно. Но если это 11-значный код доступа, угадывание займет у вас в десять раз больше времени.
На самом деле вам нужно искать не сложность алгоритма, а сложность основной проблемы - можно использовать очень неэффективный алгоритм для сортировки, например, перебирая все возможные O(n!) заказов, но это не значит, что на практике сортировка занимает много времени.
Рассмотрим одну из самых фундаментальных проблем со строками. Самая длинная общая подпоследовательность из двух строк длины. n,
Известно, что проблема может быть решена в O(n^2) используя метод динамического программирования. С другой стороны, также доказано ( статья), что для общего случая проблемы любой алгоритм требует Ω(n^2) операции (в некоторых особых случаях возможны более быстрые алгоритмы).
Таким образом, если вы хотите решить общий случай этой проблемы для строк из миллиона символов (ничего особенного для современных вычислений), на самом деле любой алгоритм займет время, пропорциональное 10^12 операции. На самом деле, в вычислительной биологии проблема нахождения самой длинной общей подпоследовательности последовательностей ДНК, если она очень важна, и эти последовательности чрезвычайно длинные, так что это хороший пример реальной проблемы, о которой вы просили.