Подсчет количества операций при приближении грубой силы

Question

Я младший студент, и у меня был курс под названием «Разработка и анализ алгоритмов». Курс классный, но инструктор нет. Я не понимаю грубую силу и то, как подсчитать количество операций и как подсчитать временную сложность (худшая, лучшая, средняя), я пытался найти ее в сети, но каждый раз заканчиваю большой обозначения и разделяй и властвуй, что я не хочу. Если кто-то из вас, ребята, может скачать слайд с инструктором по этой ссылке и посмотреть, о чем я говорю ....

слайд

Мне очень нужна твоя помощь в этом, и я обещаю, что сделаю все возможное

Answer 1

Грубая сила - это класс "алгоритмов" (или просто "способ делать вещи"), где вы не пытаетесь быть умным, просто глупый поиск. Пример: если вы хотите найти номер телефона в телефонной книге, то разумным решением будет наблюдать, что все записи отсортированы по фамилии, и напрямую искать правильную букву и т. Д. Решение методом грубой силы было бы прочитать телефонную книгу с самого начала, проверяя каждое имя и останавливаясь, когда найдено правильное имя.

Answer 2

Возможно, вам не понравится смотреть первые несколько лекций этой серии об алгоритмах .

Answer 3

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

Рассмотрим 4-значный пин-код. Если вы потеряете его, вы можете проверить все возможные коды от 0000 до 9999, чтобы найти правильный код. Это своего рода грубое принуждение.

То же самое можно использовать для решения некоторых проблем информатики, таких как проблема ранца 0/1, в которой вор хочет выяснить, что можно украсть. Каждый объект имеет значение v [i] и вес w [i]. Он или она хочет выяснить комбинацию, которая обеспечивает максимальное значение и имеет меньший вес, чем «W». Возможное решение этой проблемы - рассмотреть все комбинации объектов и найти значение и вес каждой комбинации, а затем выбрать оптимальную.

Answer 4

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

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

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

Для остроумия:

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

Если я попытаюсь использовать алгоритм для перебора лучшего маршрута, потребуется действительно очень много времени на любом маршруте, превышающем самый простой маршрут. Вот где приходит Big (O), он показывает, как каждый алгоритм, который я выберу, будет влиять на то, как долго я получу ответ.

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