Материал: для поступления в магистратуру
106
Применяется для вставки элементов массива на «свое место». Сортировка
вставками представляет собой простой метод сортировки и используется для раскладки колоды во время игры в бридж.
Каждый элемент массива вставляется на правильное (относительно остальных) место в новом, отсортированном массиве.
Так как кроме обхода всех элементов массива, для каждого элемента нужно найти место в новом массиве и сдвинуть некоторые элементы (после вставки, но до старого расположения элемента), сложность задачи – O(n2 )
Сортировка
вставками
Следует принципу «разделяй и властвуй», согласно которому массив данных
разделяется на равные части, которые сортируются по-отдельности. После они сливаются, в результате получается отсортированный массив.
Сортируемый массив разбивается на две части, каждая из которых сортируется отдельно (возможно, этим же самым алгоритмом), а потом результаты сортировок объединяются в один. Это – рекурсивный алгоритм.
Главный принцип этого алгоритма: массив из одного элемента уже отсортирован.
Сортировка
слиянием
Анализ сложности и эффективности алгоритмов поиска и сортировки
Критериями оценки эффективности алгоритма сортировки является пространственная и временная сложность.
Пространственная сложность
Означает количество памяти, затраченной на выполнение алгоритма. Пространственная сложность включает вспомогательную память и память для хранения входных данных.
Временная сложность
Означает время, за которое алгоритм выполняет поставленную задачу с учетом входных
данных.
107
В таблице представлена оценка сложности алгоритмов
Алгоритм |
Время работы в |
Время работы в |
Время работы в |
Пространственная |
|
сортировки |
худшем случае |
среднем случае |
лучшем случае |
сложность |
|
Сортировка |
n2 |
n2 |
n |
1 |
|
пузырьком |
|||||
|
|
|
|
||
Сортировка |
n2 |
n2 |
n2 |
1 |
|
выбором |
|||||
|
|
|
|
||
Быстраясортировка |
n2 |
n log n |
n log n |
n log n |
|
Сортировка кучей |
n log n |
n log n |
n log n |
1 |
|
|
|
|
|
|
|
Сортировка |
n2 |
n2 |
n |
1 |
|
вставками |
|||||
|
|
|
|
||
Сортировка |
n log n |
n log n |
n log n |
n |
|
слиянием |
|||||
|
|
|
|
У каждого алгоритма сортировки своя временная и пространственная сложность. Использовать можно любой из представленных алгоритмов в зависимости от поставленных задач. Но по моему субъективному мнению лучшим алгоритмом является быстрая сортировка. Она позволяет выбрать опорный элемент и разделяет массив на 3 части: меньше, равно и больше опорного элемента.
108
Современные технологии разработки программного обеспечения Управление версиями Документирование
Современные технологии разработки программного обеспечения, постановка задачи, оценка осуществимости
Технологияразработкипрограммногообеспечения– этосовокупностьпроцессовиметодов создания программного продукта в заданные сроки и с заданными характеристиками качества.
Данная деятельность включает в себя несколько этапов, с которыми так или иначе придётся столкнуться при разработке достаточно крупного ПО.
Любой этап жизненного цикла имеет четко определенные критерии начала и окончания. Состав этапов жизненного цикла, а также критерии, в конечном итоге определяющие последовательность этапов жизненного цикла, определяется коллективом разработчиков и/или заказчиком. В настоящее время существует несколько основных моделей жизненного цикла, которые могут быть адаптированы под реальную разработку.
1.3.1. Каскадный жизненный цикл Каскадный жизненный цикл (иногда называемый водопадным) основан на постепенном
увеличении степени детализации описания всей разрабатываемой системы. Каждое повышение степени детализации определяет переход к следующему состоянию разработки (Рис. 1.1).
Рис. 1.1. Каскадная модель жизненного цикла На первом этапе составляется концептуальная структура системы, описываются общие
принципы ее построения, правила взаимодействия с окружающим миром, - определяются системные требования.
На втором этапе по системным требованиям составляются требования к программному обеспечению - здесь основное внимание уделяется функциональности программной компоненты, программныминтерфейсам. Естественно, все программные комплексы выполняются на какой-либо аппаратной платформе. Если в ходе проекта требуется также разработка аппаратной компоненты, параллельно с требованиями к программному обеспечению идет подготовка требований к аппаратному обеспечению.
На третьем этапе на основе требований к программному обеспечению составляется детальная спецификация архитектуры системы - описываются разбиение системы по конкретным модулям, интерфейсы между ними, заголовки отдельных функций и т.п.
На четвертом этапе пишется программный код, соответствующий детальной спецификации, на пятом этапе выполняется тестирование - проверка соответствия программного кода требованиям, определенным на предыдущих этапах.
Особенность каскадного жизненного цикласостоит втом, что переход к следующему этапу происходит только тогда, когда полностью завершены все работы предыдущего этапа. То есть сначала полностью готовятся все требования к системе, затем по ним полностью готовятся все требования к программному обеспечению, полностью разрабатывается архитектура системы и так далее до тестирования.
Естественно, что в случае достаточно больших систем такой подход себя не оправдывает. Работа на каждом этапе занимает значительное время, а внесение изменений в первичные документы либо невозможно, либо вызывает лавинообразные изменения на всех других этапах.
Как правило, используется модификация каскадной модели, допускающая возврат на любой из ранее выполненных этапов. При этом фактически возникает дополнительная процедура
109
принятия решения.
Действительно если тесты обнаружили несоответствие реализации требованиям, то причина может крыться: (а) в неправильном тесте, (б) в ошибке кодирования (реализации), (в) в неверной архитектуре системы, (г) в некорректности требований к программному обеспечению и т.д. Все эти случаи требуют анализа, для того чтобы принять решение о том, на какой этап жизненного цикла надо возвратиться для устранения обнаруженного несоответствия.
1.3.2. V-образный жизненный цикл
В качестве своеобразной "работы над ошибками" классической каскадной модели стала применяться модель жизненного цикла, содержащая процессы двух видов - основные процессы разработки, аналогичные процессам каскадной модели, и процессы верификации, представляющие собой цепь обратной связи по отношению к основным процессам (Рис. 1.2).
Рис. 1.2. V-образный жизненный цикл
Таким образом, в конце каждого этапа жизненного цикла разработки, а зачастую и в процессе выполнения этапа, осуществляется проверка взаимной корректности требований различных уровней. Данная модель позволяет более оперативно проверять корректность разработки, однако, как и в каскадной модели, предполагается, что на каждом этапе разрабатываются документы, описывающие поведение всей системы в целом.
1.3.3. Спиральный жизненный цикл Оба рассмотренных типа жизненных циклов предполагают, что заранее известны все
требования пользователей или, по крайней мере, предполагаемые пользователи системы настолько квалифицированы, что могут высказывать свои требования к будущей системе, не видя ее перед глазами.
Естественно, такая картина достаточно утопична, поэтому постепенно появилось решение, исправляющее основной недостаток V-образного жизненного цикла - предположение о том, что на каждом этапе разрабатывается очередное полное описание системы. Этим решением стала
спиральная модель жизненного цикла (Рис. 1.3).
Рис. 1.3. Спиральный жизненный цикл В спиральной модели разработка системы происходит повторяющимися этапами - витками
110
спирали. Каждый виток спирали - один каскадный или V-образный жизненный цикл. В конце каждого витка получается законченная версия системы, реализующая некоторый набор функций. Затем она предъявляется пользователю, на следующий виток переносится вся документация, разработанная на предыдущем витке, и процесс повторяется.
Таким образом, система разрабатывается постепенно, проходя постоянные согласования с заказчиком. На каждом витке спирали функциональность системы расширяется, постепенно дорастая до полной.
1.3.4. Экстремальное программирование Реалии последних лет показали, что для систем, требования к которым изменяются
достаточночасто,необходимоещебольшеуменьшитьдлительностьвиткаспиральногожизненного цикла. В связи с этим сейчас стали весьма популярными быстрые жизненные циклы разработки, например, жизненный цикл в методологии eXtreme Programming (XP).
Основная идея жизненного цикла экстремального подхода - максимальное укорачивание длительности одного этапа жизненного цикла и тесное взаимодействие с заказчиком. По сути, на каждом этапе происходит реализация и тестирование одной функции системы, после завершения которых система сразу передается заказчику на проверку или эксплуатацию.
Основная проблема данного подхода - интерфейсы между модулями, реализующими эту функцию. Если во всех предыдущих типах жизненного цикла интерфейсы достаточно четко определяются в самом начале разработки, поскольку заранее известны все модули, то при экстремальном подходе интерфейсы проектируются "на лету", вместе с разрабатываемыми модулями.
При формулировании цели и задач проекта должен быть создан документ, дающий ответы на следующие вопросы:
•Как определяется предметная область для данного проекта? Какие термины используются в предметной области? Какие бизнес-процессы, затрагиваемые проектом, протекают
впредметной области?
•Какая цель у проекта? Какой эффект должна оказать разрабатываемая система на бизнес-процессы предметной области?
•Какие задачи требуется решить, чтобы достичь поставленной цели? По каким критериям будет оцениваться качество решения поставленных задач? Каковы функциональные и нефункциональные показатели качества разрабатываемой системы?
•Какие ограничения на сроки выполнения, ресурсы, бюджет накладываются на реализацию проекта?
Планирование, тестирование, обеспечение оценки качества
Планирование является целью каждого вида деятельности, когда мы хотим обнаружить то, что относится к проекту. Важной задачей при создании программного обеспечения является извлечение требований или анализ требований. Клиенты обычно имеют абстрактное представление о том, чего они хотят в конечном результате, но не знают, что должно делать программное обеспечение.
Тестирование – это процесс, содержащий в себе все активности жизненного цикла, как динамические, так и статические, касающиеся планирования, подготовки и оценки программного продукта и связанных с этим результатов работ, с целью определить, что они соответствуют описанным требованиям, показать, что они подходят для заявленных целей и для определения дефектов. Качество же – это способность ПОпри заданных условиях удовлетворять установленным или предполагаемым потребностям.
Верификация - это процесс определения, выполняют ли программные средства и их компоненты требования, наложенные на них в последовательных этапах жизненного цикла разрабатываемой программной системы.
Основная цель верификации состоит в подтверждении того, что программное обеспечение соответствует требованиям. Дополнительной целью является выявление и регистрация дефектов и ошибок, которые внесены во время разработки или модификации программы.
Понятие качества ПС.
Качество ПС - это совокупность его черт и характеристик, которые влияют на его