Алгоритмы
Introduced| English | Русский |
|---|---|
| algorithm/ˈælɡərɪθəm/ | алгоритм |
| flowchart/ˈfləʊtʃɑːt/ | блок-схема |
| pseudocode/ˈsuːdəʊkəʊd/ | псевдокод |
| tracing/ˈtreɪsɪŋ/ | отслеживание |
| binary search/ˈbaɪnəri sɜːtʃ/ | бинарный поиск |
| linear search/ˈlɪnɪə sɜːtʃ/ | линейный поиск |
| efficiency/ɪˈfɪʃənsi/ | КПД |
Указывайте, какие входы должна обрабатывать процедура
- Алгоритм описывает однозначные шаги для задачи. Процедура, решающая stated конечную задачу, должна завершаться и давать правильный результат для каждого допустимого входа.
- Успешный прослед на одном входе показывает этот случай, а не доказательство для всех входов. Граничные случаи и случаи пустого ввода могут выявить ошибки, которые упускает типичный пример.
Что требуется для последовательности шагов, чтобы она считалась алгоритмом? Выберите все подходящие варианты.
Процедура, решающая указанную конечную задачу, требует однозначных шагов, правильных результатов и завершения на допустимых входах. Псевдокод и блок-схемы являются представлениями, а не требованием использовать определенный язык программирования.
Четко представляйте выборы и обновления
- Блок-схема использует ромб принятия решений, прямоугольник процесса, параллелограмм ввода/вывода и терминалы начала/конца, соединенные направленными стрелками потока.
- Псевдокод описывает шаги без привязки к конкретному языку программирования. Перед проследом укажите значение присваивания, начало индекса, границы цикла и условия ветвления.
Соотнесите каждую форму блок-схемы с её значением.
Используйте прямоугольники процессов, ромбы решений и терминалы начала/конца согласно данным; ввод/вывод обычно изображается параллелограммом. Подписывайте ветви решений и направления потока.
Записывайте фактические значения переменных
- Прослед следует заявленным обновлениям по порядку. Временная переменная может сохранить значение, которое иначе было бы перезаписано.
- Показывайте low, high, middle и сравниваемое значение для бинарного поиска; показывайте каждую измененную переменную для арифметического цикла. Оценивайте, что делает процедура, а не только ее предполагаемую цель.
Заданная конвенция бинарного поиска. Используйте нулевую базу с включительными границами и округление вниз их среднего для middle. Поиск числа 7 в [1,3,5,7,9,11] сравнивает индекс 2/значение 5, индекс 4/значение 9, затем индекс 3/значение 7. Количество сравнений составляет три согласно этой конвенции.
Линейный против бинарного поиска
Уменьшение вдвое превосходит последовательную проверку, и разница увеличивается с ростом списка.
Используя нулевые включительные границы и floor((low+high)/2), сколько сравнений использует бинарный поиск для нахождения 7 в [1,3,5,7,9,11]?
Средние индексы — 2, 4, затем 3, со значениями 5, 9 и 7. Три сравнения при указанной конвенции.
Сравнивайте работу при ее предпосылках
- Линейный поиск может остановиться раньше, но может осмотреть все n элементов. Бинарный поиск последовательно делит пополам отсортированный диапазон поиска и требует согласованных обновлений границ.
- Эффективность описывает, как требуемая работа масштабируется с размером входа в рамках определенного модели. Сортировка сначала имеет собственную стоимость; неотсортированный вход не может полагаться на гарантию порядка бинарного поиска.
Для уже отсортированного списка из миллиона элементов примерно сколько сравнений средних значений может потребовать бинарный поиск в худшем случае?
Каждое сравнение уменьшает оставшийся диапазон поиска вдвое; около 20 сравнений достаточно для миллиона упорядоченных элементов. Это исключает любую стоимость сортировки заранее.
Бинарный поиск работает по неотсортированному списку, просто медленнее.
Без требуемого порядка отбрасывание половины может пропустить присутствующий элемент. Некоторые случаи могут случайно удалась, но корректность не гарантирована.
Проверяйте ноль и последний допустимый индекс. Лист 4.4 рассматривает цикл суммы с условием i меньше n, который пропускает последний член. Его эвклидово прослед также объясняет завершение: каждый положительный делитель заменяется на меньший неотрицательный остаток, пока не будет достигнуто ноль.