База ответов ИНТУИТ

Инструменты, алгоритмы и структуры данных

<<- Назад к вопросам

Для оценки качества алгоритма принято использовать абстрактную сложность алгоритма, не связанную с его реализацией. Чаще всего используют две меры сложности - временную и емкостную, характеризующие время работы алгоритма и память, требуемую для его работы. Укажите утверждения, справедливые для абстрактной сложности алгоритма:

(Ответ считается верным, если отмечены все правильные варианты ответов.)
Варианты ответа
для функции, характеризующей сложность не требуется задание точной формулы, - достаточно определить ее с точностью до порядка, что позволяет использовать математическую нотацию О-большое(Верный ответ)
константные множители можно не учитывать при оценке абстрактной сложности(Верный ответ)
абстрактная сложность рассматривается как функция, зависящая от размера задачи(Верный ответ)
константные слагаемые можно не учитывать при оценке абстрактной сложности(Верный ответ)
функция, характеризующая сложность, должна быть строго определена
Похожие вопросы
В ходе работы алгоритма на каждом шаге алгоритма находится элемент, не имеющий предшественников, добавляемый в перечисление, задающее сортировку элементов. Кандидатов на эту роль может быть несколько. Какую структуру данных следует выбрать для хранения кандидатов, чтобы клиент мог управлять процессом выбора кандидатов?
Реализация алгоритма топологической сортировки включала такой прием, как предварительная трансляция исходных данных в форму, удобную для эффективной реализации алгоритма. Что справедливо о применении этого приема в других программистских задачах? Этот прием следует применять:
При решении одной и той же задачи можно использовать разные алгоритмы. На практике часто важно, сколько времени и сколько памяти требуется для решения этой задачи. Понятно, что эти характеристики зависят от входных данных, которые определяют "размер" задачи. Для контейнеров естественным "размером" может служить n- число элементов, хранимых в контейнере. Самый простой путь определения для алгоритма характеристик требуемой памяти и времени - это проведение экспериментов и вычисление характеристик на основе наблюдений с последующим усреднением данных. Укажите утверждения, корректные относительно данного способа вычисления характеристик алгоритма:
Для некоторых алгоритмов получены оценки сложности. Из приведенных формул укажите две, задающие эквивалентные оценки?
Структуры данных, используемые в алгоритме топологической сортировки, работают не с самими элементами множества, а с их номерами. Какие утверждения справедливы относительно возможного типа сортируемых элементов в предлагаемой реализации алгоритма?
Какие операции можно считать базисными для алгоритма построения топологической сортировки?
Какие утверждения справедливы о сложности решения задачи о топологической сортировке?
Какие утверждения справедливы о сложности операции вставки элемента в дерево поиска с n элементами?
При реализации алгоритма обращения списка на том же месте, требующего O(count) времени, на каждом шаге цикла достаточно выполнить несколько операторов ссылочного присваивания. Сколько требуется операторов?
Гарри Поттер ищет важную для него информацию. Он надеется, что она может быть в одной из книг библиотеки Хогварда, содержащей N книг. Гарри наугад выбирает книгу и просматривает ее содержимое, на что у него уходит T минут. При неудаче он повторяет поиск, выбирая новую книгу. Для такого алгоритма поиска каковы значения времени поиска: минимальное, максимальное, в среднем?