Студопедия  
Главная страница | Контакты | Случайная страница

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

Анализ данных и алгоритмов

Читайте также:
  1. C. Ветвящихся алгоритмов
  2. Cохранение данных в двоичных файлах.
  3. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
  4. D. обобщение, сравнение анализ ,синтез
  5. I) Однофакторный дисперсионный анализ .
  6. I)Однофакторный дисперсионный анализ (выполняется с применением программы «Однофакторный дисперсионный анализ» надстройки «Анализ данных» пакета Microsoft Excel).
  7. Ii) Двухфакторный дисперсионный анализ
  8. II. Анализ деятельности педагога
  9. II. Анализ программ по чтению и литературной подготовке учащихся начальной школы и УМК к ним. Познакомьтесь с требованиями ФГОС.
  10. II. Анализ результатов учебной деятельности.

На всех этапах разработки программ необходимо анализированть их характеристики, к которым прежде всего относятся надежность и эффективность. Надежность программ тесно связана с их формальной корректностью.

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

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

В некоторых случаях для пояснения и обоснования алгоритма в учебнике приводится инвариант цикла - утверждение, соблюдаемое при каждом попадании управления в некоторую точку цикла. Формулирование инварианта цикла - наиболее трудная часть доказательства, проверить его правильность гораздо легче. Инвариант цикла выражает основную идею его построения и его удобно записывать в виде комментария в соответствующем месте цикла.

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

Эффективность программы определяется временем работы алгоритма и объемом памяти для алгоритма и данных. Важную роль в программировании играет пространственно-временная закономерность: уменьшение времени работы алгоритма приводит, как правило, к дополнительным затратам памяти и, наоборот, экономия памяти обычно приводит к замедлению работы программы. Таким образом, эти два параметра программы тесно взаимосвязаны. Изменяя один из них, можно в определенной степени управлять значением другого.

Под сложностью алгоритма в литературе обычно имеют в виду не трудность его разработки или понимания, а его вычислительную сложность, т.е. время и объем памяти, необходимые для решения задачи. В книге приводятся оценки сложности ряда алгоритмов и методов решения задач. Сложность алгоритма обычно оценивается асимптотически - по скорости роста необходимого времени и памяти при возрастании размера задачи.

Размер задачи n определяется количеством обрабатываемых данных: длиной входной последовательности, размером матриц, числом вершин или ребер графа и т. д. Время измеряется количеством основных элементарных операций, необходимых для решения задачи (пересылка, сложение, сравнение и т. п.).

Для сравнения скорости роста функций в литературе используются различные обозначения. Рассмотрим некоторые из них – так называемое О-обозначение, W-обозначение и Q-обозначение [21, 35].

Выражение f(n) = O(g(n)) читается "f(n) есть о большое от g(n)" (говорят также “f(n) имеет значение порядка g(n)”) и обозначает, что g(n) является верхней границей для f(n), то есть f(n) £ C×g(n) для некоторой константы C.

Выражение f(n) = W(g(n))читается "f(n) есть омега большое от g(n)" и обозначает, что g(n) может служить нижней границей для f(n).

Выражение f(n) = Q(g(n))читается "f(n) есть тета большое от g(n)" и обозначает, что g(n) является асимптотически точной оценкой для f(n).

Справедливы отношения: f(n) = W(g(n)) <==> g(n) = O(f(n)),

f(n) = Q(g(n)) ==> g(n) = Q(f(n)), f(n)=Q(g(n)) <==> f(n)=O(g(n)) и g(n)=O(f(n)).

 

Примеры: n5+6*n = O(n5), величина порядка О(1) не зависит от n (т. е. является константой).

 

Таким образом, утверждение, что время или память имеет значение порядка f(n) или О(f(n)) означает, что при увеличении размера задачи n эта величина не превышает C· f(n), C = const >0.


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




lektsii.net - Лекции.Нет - 2014-2019 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав