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

Шаг алгоритма

Читайте также:
  1. Для реализации логики алгоритма и программы с точки зрения структурного программирования НЕ ДОЛЖНЫ применяться
  2. Описание алгоритма
  3. Описание алгоритма умножения чисел с ПЗ
  4. Описание функционирования алгоритма программного обеспечения (ПО).
  5. Построение алгоритма диагностирования
  6. Построение отмеченной граф-схемы алгоритма
  7. Разработка алгоритма программы

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

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

 

Если сложность какого-либо алгоритма есть О(g(п)), то говорим, что этот алгоритм «затрачивает порядка О(g(п)) времени».

Подобным же образом определяются символы О(g(п1, ,пk)) и Ω(g(п1, ,пk)) для функции многих переменных, например:

f(п1, ,пk) = О(g(п1, ,пk)) существуют константыС, N > 0, такие, что f(п1, ,пk) С g(п1, ,пk) для всех п1, ,пk N;

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

 

Оптимизационные задачи

Мы будем рассматривать оптимизационные задачи. В таких задачах может существовать множество различных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи).

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

Рассмотрим схему работы жадных алгоритмов на конкретных примерах.


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


Читайте в этой же книге: Исторический обзор | Теорема | Теорема |
<== предыдущая страница | следующая страница ==>
Формализация понятия алгоритма| Теорема

mybiblioteka.su - 2015-2017 год. (0.01 сек.)