Подсчет количества операций при приближении грубой силы
Я младший студент, и у меня был курс под названием "Разработка и анализ алгоритмов". Курс классный, но инструктор нет. Я не понимаю грубую силу и то, как подсчитать количество операций и как подсчитать временную сложность (худшая, лучшая, средняя), я пытался найти ее в сети, но каждый раз заканчиваю большой обозначения и разделяй и властвуй, что я не хочу. Если кто-то из вас, ребята, может скачать слайд с инструктором по этой ссылке и посмотреть, о чем я говорю....
Мне очень нужна ваша помощь в этом, и я обещаю, что сделаю все возможное
4 ответа
Грубая сила - это класс "алгоритмов" (или просто "способ делать вещи"), где вы не пытаетесь быть умным, просто глупый поиск. Пример: если вы хотите найти номер телефона в телефонной книге, то разумным решением будет наблюдать, что все записи отсортированы по фамилии, и напрямую искать правильную букву и т. Д. Решение методом грубой силы было бы прочитать телефонную книгу с самого начала, проверяя каждое имя и останавливаясь, когда найдено правильное имя.
Возможно, вам не понравится смотреть первые несколько лекций этой серии об алгоритмах.
Грубое принуждение - это задача тестирования всех возможных конфигураций конкретной проблемы и проверки соответствия одной из них свойствам решения.
Рассмотрим 4-значный пин-код. Если вы потеряете его, вы можете проверить все возможные коды от 0000 до 9999, чтобы найти правильный код. Это своего рода грубое принуждение.
То же самое можно использовать для решения некоторых проблем информатики, таких как проблема ранца 0/1, в которой вор хочет выяснить, что можно украсть. Каждый объект имеет значение v[i] и вес w[i]. Он или она хочет найти комбинацию, которая обеспечивает максимальное значение и имеет меньший вес, чем "W". Возможное решение этой проблемы - рассмотреть все комбинации объектов и найти значение и вес каждой комбинации, а затем выбрать оптимальную.
Могу ли я иметь пример сортировки выбора и пузырьковой сортировки, как посчитать время и как подсчитать операции и какова проблема коммивояжера?
Алгоритм сортировки выбора доступен в псевдокоде из Википедии, как и Bubble Sort. Временная сложность вычисляется числом раз, которое требуется алгоритму, чтобы пройти, пока он не получит правильный ответ.
Задача коммивояжера - это классическая проблема в информатике, которая связывает время выполнения алгоритма с выяснением ответа на вопрос.
Для остроумия:
Проблема заключается в следующем: учитывая количество городов и стоимость проезда из любого города в любой другой город, какой маршрут с наименьшей стоимостью обходит каждый город ровно один раз, а затем возвращается в начальный город?
Если я попытаюсь использовать алгоритм для подбора наилучшего маршрута, это займет очень много времени на любом маршруте, превышающем самый простой маршрут. Вот где приходит Big(O), он показывает мне, как каждый алгоритм, который я выберу, будет влиять на то, как долго я получу ответ.
Я разместил этот ответ, основываясь на комментариях, которые вы оставили для других ответов. Что бы это ни стоило, нотация Big-O - это именно то, что вам нужно, это показатель того, сколько времени займет выполнение вашего алгоритма.