Студопедия

КАТЕГОРИИ:

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



Эффективность алгоритма. Временная сложность алгоритма. Полиноминальные и экспоненциальные алгоритм.

Читайте также:
  1. Автотрансформаторы, схемы включения обмоток, энергетическая эффективность.
  2. Алгоритм. Свойства алгоритма. Способы описания алгоритма. Примеры.
  3. Внезапная и кратковременная потеря сознания на фоне сужения или окклюзии артерий, снабжающих головной мозг
  4. Вопр. Понятие алгоритма. Способы описания алгоритмов
  5. ВОПРОС 10. Особенности труда в торговле. Производительность и эффективность труда работников
  6. Временная организация клетки: понятие о жизненном (клеточном) цикле. Характеристика интерфазы.
  7. Временная стоимость денег. Операции наращения и дисконтирования.
  8. ВРЕМЕННАЯ ЭКСПОЗИЦИЯ ИЗ МЕКСИКИ
  9. В№25 Современная западная религиозная философия
  10. В№32. Пространственно-временная организация бытия.

http://akak-ich.ru/informatika-effect_alg.php

Алгоритм, в конечном счете, выполняется в машинной системе со специфическим набором команд и периферийными устройствами. Для отдельной системы какой-либо алгоритм может быть разработан для полного исполь­зования преимуществ данного компьютера и поэтому достигает высокой степени эффективности. Критерий, называемый системной эффективностью (sys-tem efficiency), сравнивает скорость выполнения двух или более алгоритмов, которые разработаны для выполнения одной и той же задачи. Выполняя эти алгоритмы на одном компьютере с одними и теми же наборами данных, мы можем определить относительное время, используя внутренние системные часы. Оценка времени становится мерой системной эффективности для каждого из алгоритмов.

При работе с некоторыми алгоритмами могут стать проблемой ограничения памяти. Процесс может потребовать большого временного хранения, ограничивающего размер первоначального набора данных, или вызвать требующую времени дисковую подкачку. Эффективность пространства(space efficiency) — это мера относительного количества внутренней памяти, используемой каким-либо алгоритмом. Она может указать, какого типа компьютер способен выполнять этот алгоритм и полную системную эффективность алгоритма. Вследствие увеличения объема памяти в новых системах, анализ пространственной эффективности становится менее важным.

Третий критерий эффективности рассматривает внутреннюю структуру алгоритма, анализируя его разработку, включая количество тестов сравнения итераций и операторов присваивания, используемых алгоритмом. Эти типы измерений являются независимыми от какой-либо отдельной машинной системы. Критерий измеряет вычислительную сложность алгоритма относительно n, количества элементов данных в коллекции. Мы называем эти критерии вычислительной эффективностью (computational efficiency)алгоритма и разрабатываем нотациюBig-О для построения измерений, являющихся функциями n

В информатике, теория сложности вычислений являетсяразделом теории вычислений, изучающим стоимость работы,требуемой для решения вычислительной проблемы.Стоимость обычно измеряется абстрактными понятиямивремени и пространства, называемыми вычислительнымиресурсами. Время определяется количеством тривиальныхшагов, необходимых для решения проблемы, тогда какпространство определяется объёмом памяти или места наносителе данных. Таким образом, в этой областипредпринимается попытка ответить на центральный вопросразработки алгоритмов: «как изменится время исполнения иобъём занятой памяти в зависимости от размера входа ивыхода?». Здесь под размером входа понимается длинаописания данных задачи в битах (например, в задачекоммивояжера длина входа пропорциональна количествугородов и дорог между ними), а под размером выхода —длина описания решения задачи (оптимального маршрута взадаче коммивояжера).




Дата добавления: 2015-01-05; просмотров: 40; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Абстрактные структуры данных | NP-полные задачи
lektsii.com - Лекции.Ком - 2014-2017 год. (0.008 сек.) Главная страница Случайная страница Контакты