Студопедия — Вычислительная и емкостная сложность алгоритма
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Вычислительная и емкостная сложность алгоритма






Физическое время реализации алгоритма при некотором наборе входных данных может быть определено как , где - количество операций i-ого типа, - время выполнения операции i-го типа, n – количество типов операций. Для одного и того же алгоритма при заданном наборе входных данных время t зависит от языка программирования и быстродействия конкретной ЭВМ. Если мы имеем такую оценку для нескольких алгоритмов решения одной и той же задачи, реализованных на разных языках и предназначенных для выполнения на ЭВМ с различным быстродействием, очевидно, что объективный выбор алгоритма выполнить невозможно. Можно принять за эталон некоторую операцию и, зная отношение времени выполнения i-й операции ко времени выполнения эталонной, можно определить суммарное число эталонных операций:

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

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

В зависимости от существующей на данной стадии разработки алгоритма его детализации аналогичной по смыслу с и оценкой может быть суммарное количество некоторых доминирующих операций или основных действий или шагов. Однако все эти оценки являются некоторой скалярной величиной, так как определяются для заданного набора входных данных. Очевидно, что для входных данных, имеющих другой размер, они будут отличаться. Размер входа задачи может быть как скаляром, так и вектором.

Временная и вычислительная сложность являются функцией от размера входа. Размер входа – скаляр, если количество, например, некоторых действий или шагов зависит только от одного параметра входа задачи. Например, в задачах на графах – только от количества вершин или рёбер. Размер входа – вектор, если от нескольких: для графов – количество вершин, рёбер, локальной степени вершин и т. д.







Дата добавления: 2015-04-19; просмотров: 483. Нарушение авторских прав; Мы поможем в написании вашей работы!



Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Психолого-педагогическая характеристика студенческой группы   Характеристика группы составляется по 407 группе очного отделения зооинженерного факультета, бакалавриата по направлению «Биология» РГАУ-МСХА имени К...

Общая и профессиональная культура педагога: сущность, специфика, взаимосвязь Педагогическая культура- часть общечеловеческих культуры, в которой запечатлил духовные и материальные ценности образования и воспитания, осуществляя образовательно-воспитательный процесс...

Устройство рабочих органов мясорубки Независимо от марки мясорубки и её технических характеристик, все они имеют принципиально одинаковые устройства...

Классификация ИС по признаку структурированности задач Так как основное назначение ИС – автоматизировать информационные процессы для решения определенных задач, то одна из основных классификаций – это классификация ИС по степени структурированности задач...

Внешняя политика России 1894- 1917 гг. Внешнюю политику Николая II и первый период его царствования определяли, по меньшей мере три важных фактора...

Оценка качества Анализ документации. Имеющийся рецепт, паспорт письменного контроля и номер лекарственной формы соответствуют друг другу. Ингредиенты совместимы, расчеты сделаны верно, паспорт письменного контроля выписан верно. Правильность упаковки и оформления....

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия