Итак, рассмотрены различные варианты вычислительных машин от простейшей машин Тьюринга до однородной вычислительной среды. Все они могут быть использованы для решения тех задач, для которых существует алгоритм. На основе этих моделей строятся более специализированные модели вычислений, а именно: неветвящиеся арифметические программы, битовые вычисления, вычисления с двоичными векторами и деревья решений.
Алгоритмы имеют следующие характеристики:
а) сложность;
б) трудоемкость;
в) надежность, и др.
Для оценки сложности алгоритмов существует много критериев. Чаще всего нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении количества входных данных. Свяжем с каждой конкретной задачей некоторое число, называемое ее размером . Например, размером задачи умножения матрицы может быть наибольший размер матриц - сомножителей; размером задачи на графе может быть число ребер данного графа, и т.п.
Время, затрачиваемое алгоритмом, как функция размера задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью . Аналогично определяются емкостная сложность и асимптотическая емкостная сложность .
Важным мотивом, побуждающим рассматривать формальные модели вычислений, является желание раскрыть вычислительную сложность различных задач с целью получить нижние оценки на время вычисления. Чтобы показать, что не существует алгоритма, выполняющего данное задание менее, чем за определенное время, необходимо точное и подчас высоко специализированное определение того, что есть алгоритм. Одним из примеров такого определения служат машины Тьюринга.
4.1.1. Машины рам и рам*
Рассмотрим две машины:
1. Машины с произвольным доступом к памяти равнодоступная адресная машина - РАМ) моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя.
2. Модель с хранимой программой - это машина с произвольным доступом к памяти и возможностью модификаций команд (РАМ*).
Рис.2.9 Структура машин РАМ (РАМ*)
Для РАМ программа не записывается в память, поэтому программа не изменяет саму себя. Программа - последовательность помеченных команд. Имеются арифметические команды, команды ввода-вывода, команды косвенной адресации и команды разветвления. Все вычисления производятся в регистре r 0 (сумматор), который, как и любой другой регистр памяти, может хранить произвольное целое число. Каждая команда состоит из двух частей - кода операции и адреса. РАМ-команды являются подмножеством команд языка Ассемблер; это подмножество можно по желанию расширить, но при этом порядок сложности задач не изменится.
Операнд может быть одного из следующих типов:
1. =i означает само целое число i и называется литералом;
2. i - содержимое регистра i (i должно быть неотрицательным);
3. *i означает косвенную адресацию, то есть значением операнда служит содержимое регистра j ,где j - целое число, которое находится в регистре I ;если j<0, машина останавливается.
Можно определить значение программы Р с помощью двух объектов: отображения c из множества неотрицательных целых чисел в множество целых чисел и “счетчика команд”, который определяет очередную выполняемую команду. Функция c есть отображение памяти, а именно с(i)- целое число, содержащееся в регистре с номером I (содержимое регистра I ).
Вначале с(i)=0 для всех i 0 , счетчик команд установлен на первую команду в Р, а выходная лента пуста. После выполнения k -й команды из Р счетчик автоматически переходит на (k+1) -ю (то есть на очередную) команду, если k -я команда не была командой вида JUMP, HALT, JGTZ и тому подобное.
РАМ*-программа находится в регистрах памяти. Каждая РАМ*-команда занимает два последовательных регистра памяти: первый регистр содержит код операции, второй - адрес. Набор команд для РАМ* совпадает с соответствующим набором для РАМ во всем, кроме косвенной адресации, которая исключена: РАМ* может моделировать косвенную адресацию путем изменения команд в процессе выполнения программы.
Алгоритм - набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.
ВременнАя эффективность
является индикатором скорости работы алгоритма
оценивается по количеству основных операций, которые должен выполнить алгоритм при обработке входных данных размера n
Важен порядок роста времени выполнения алгоритма в зависимости от n
Пространственная эффективность показывает, сколько дополнительной оперативной памяти нужно для работы алгоритма. Эффективность оценивают в наихудшем, наилучшем и среднем случаях.
Виды анализа: математический и эмпирический
Измерение времени выполнения алгоритма
1. Непосредственное (эмпирический анализ)
2. Определение количества базовых операций, которые должен выполнить алгоритм при обработке входных данных размера n (математический анализ)
Порядок роста
При малых размерах входных данных невозможно заметить разницу во времени выполнения между эффективным и неэффективным алгоритмом. Для больших значений n вычисляют порядок роста функции.
Эффективность алгоритма в разных случаях
Существует большое количество алгоритмов, время выполнения которых зависит не только от размера входных данных, но и от конкретных особенностей входных данных (пример – поиск).
Эффективность измеряют для:
Пример: среднее количество операций сравнения при поиске:
Итак:
При разработке алгоритмов очень важно иметь возможность оценить ресурсы, необходимые для проведения вычислений, результатом оценки является функция сложности (трудоемкости). Оцениваемым ресурсом чаще всего является процессорное время (вычислительная сложность) и память (сложность алгоритма по памяти). Оценка позволяет предсказать время выполнения и сравнивать эффективность алгоритмов.
Эффективность алгоритма - это свойство алгоритма , которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако, различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности.
Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы , оптимизирующий компилятор , оптимизация циклов , оптимизатор объектного кода , и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».Энциклопедичный YouTube
1 / 5
✪ CS50. Асимптотические обозначения
✪ 1. Алгоритмы и структуры данных. Введение | Технострим
✪ Алгоритмическая эффективность
✪ Алгоритм Кнута-Морриса-Пратта
✪ 2. Алгоритмы и структуры данных. Списки, стек, очередь, дек | Технострим
Субтитры
Вы, вероятно, слышали как люди говорят о быстрых или эффективных алгоритмах для выполнения той или иной задачи, но что именно понимают под быстротой и эффективностью в случае алгоритмов? В действительности говорят не об измерениях реального времени в секундах или минутах. Потому что компьютерное оборудование и программное обеспечение весьма разнообразно. Моя программа может работать медленнее вашей из-за того, что я запустил её на более старом компьютере, или из-за того, что я одновременно играю в сетевую игру какую-нибудь, которая съедает у меня всю память. Или же я запустил свою программу через другое программное обеспечение, которое по-своему взаимодействует с оборудованием на низком уровне. Это всё равно что сравнивать тёплое с мягким. Только то, что у моего более медленного компьютера уходит больше времени на поиск ответа, ещё не значит, что ваш алгоритм более эффективный. Раз мы не можем напрямую сравнивать время исполнения программ в секундах или минутах, то как нам сравнить два разных алгоритма без зависимости от оборудования или программного обеспечения? Чтобы унифицировать способ измерения алгоритмической эффективности, математики и специалисты в области информатики нашли решение в измерении асимптотической сложности программы и так называемой записи "О большое" для её описания. Формальное определение звучит так: Функция f(x) имеет порядок g(x), если существует такое значение "x", "x₀" и некоторая константа "C", для которых f(x) меньше или равно этой константе, умноженной на g(x) для любого "x" большего, чем "x₀". Однако, не пугайтесь формального определения. Что же это значит на самом деле в менее теоретических терминах? Ну, попросту говоря, это способ анализа того, насколько быстро растёт асемптотическое время исполнения программы. То есть по мере увеличения размера входных данных в сторону бесконечности. Скажем, мы сортируем массив из 1000 элементов и массив из 10. Как вырастет время исполнения программы? Например, представьте подсчёт числа символов в строке простейшим способом, проходом всей строки буква за буквой и добавлением единицы к счётчику каждый раз. Говорят, что алгоритм выполняется за линейное время от количества символов (n) в строке. Или кратко, выполняется за O(n). Почему так? Ну, при таком подходе время, требующееся для прохода всей строки, пропорционально числу символов в ней. Подсчёт числа символов в 20-символьной строке займёт вдвое больше, чем подсчёт в 10-символьной строке, потому что придётся посмотреть на все символы, а просмотр каждого символа занимает одинаковое время. По мере увеличения числа символов время исполнения будет увеличиваться вместе с длиной исходных данных. Теперь, допустим, вы решаете, что линейное время, O(n), -- это не достаточно быстро. Возможно, вы храните огромные строки и не можете позволить себе дополнительное время на проход по всем символам, подсчитывая их один за другим. И вы решаете попробовать кое-что другое. Что если число символов для строки уже будет храниться в переменной, скажем, "len". Оно сохраняется в программе раньше, ещё до того, как вы сохранили самый первый символ своей строки. Тогда всё, что вам нужно будет сделать для нахождения длины строки -- это прочитать значение этой переменной. Вам не пришлось бы вообще смотреть на саму строку, а чтение значения переменной "len" предпологается операцией, выполняющейся за асимптотически постоянное время, или O(1). Почему так? Вспомним, что значит асимптотическая сложность. Как время исполнения изменяется по мере роста размера входных данных? Допустим, вы получаете количество символов в более длинной строке. В общем-то, совершенно не важно, насколько она длинная. Хоть миллион символов. Всё, что нужно будет сделать при таком подходе, чтобы найти длину строки -- это прочитать значение переменной "len", которую вы уже получили. Размер входных данных, в нашем случае строки, длину которой мы хотим найти, вообще не будет влиять на то, как быстро выполняется программа. Эта часть вашей программы будет одинаково быстро выполняться на строке из одного символа и на строке из тысячи символов. И вот поэтому программа будет считаться исполняющейся за постоянное время относительно размера входных данных. Конечно же, есть и недостатки. Вы тратите дополнительную память вашего компьютера для хранения переменной, а также дополнительное время, чтобы заполнить её значение. Но смысл в этом всё равно есть. Время получения количества символов в строке вообще не зависит от длины строки. Итак, оно исполняется за O(1) или за постоянное время. Само собой это не обязательно значит, что ваш код выполняет только один шаг. Однако, не важно сколько будет шагов, если их число не меняется при изменении размера входных данных. Оно будет асимптотически постоянным, что мы обозначаем как O(1). Как вы, возможно, предположили есть много различных "больших О" для измерения времени исполнения алгоритмов. Алгоритмы O(n²) асимптотически медленнее алгоритмов O(n). Это значит, что по мере увеличения количества элементов, n, алгоритмы O(n²), в конечном итоге потребуют больше времени, чем алгоритмы O(n). Это не значит, что алгоритмы O(n) всегда выполняются быстрее, чем алгоритмы O(n²), даже в одинаковом окружении на одинаковом оборудовании. Может быть так, что для небольших входных данных алгоритм O(n²) будет и в самом деле работать быстрее, однако, со временем, по мере увеличения размеров входных данных в сторону бесконечности, время исполнения алгоритма O(n²) будет в конце концов затмевать время исполнения алгоритма O(n). Также как и любая квадратичная математическая функция будет в конечном счёте обгонять любую линейную функцию. И не важно насколько велика фора у значения линейной функции в самом начале. Если вы работаете с большими объёмами данных, то алгоритмы, выполняющиеся за O(n²), в итоге замедляют вашу программу, но на небольших размерах входных данных вы этого даже не заметите, скорее всего. Ещё один вид асимптотической сложности -- это логарифмическое время, O(log n). Примером алгоритма, который выполняется так быстро, служит классический алгоритм двоичного поиска для нахождения элемента в предварительно отсортированном наборе. Если вы не знаете, как выполняется двоичный поиск, я сейчас быстренько всё объясню. Скажем, вы ищете число 3 в массиве целых чисел. Берём центральный элемент массива и спрашиваем: "Нужный мне элемент больше, меньше или равен этому?" Если равен -- отлично. Мы нашли нужный элемент, на этом всё. Если больше, то понятно, что наш элемент должен быть в массиве где-то справа, и дальше можно смотреть только в правую часть. Если меньше, тогда понятно, что элемент где-то слева. Затем повторяем этот процесс со всё более короткими массивами, пока не найдём нужный элемент. Этот мощный алгоритм уменьшает размер массива в два раза после каждой операции. То есть для нахождения элемента в отсортированном массиве длины 8 нужно не более (log₂8) или трёх таких операций проверки центрального элемента и выбора нужной половины. В то же время для массива длины 16 понадобится (log₂16) или четыре операции. А это всего одна дополнительная операция при удвоении длины массива. Удвоение размера увеличивает время исполнения всего на один кусок кода. Ещё раз -- проверяем центральный элемент и делим массив. Итак, это называют логарифмическое время, O(log n). Но погоди-ка, скажете вы, а не зависит ли он от того, где в массиве находится искомый элемент? Что если первый же элемент, который мы проверим окажется тем самым? Тогда это займёт всего одну операцию, и не важно насколько большой массив. Именно поэтому в информатике существуют ещё другие понятия для асимптотической сложности, которые отражают производительность в лучшем и худшем случае. Или более строго -- верхнюю и нижнюю границы времени исполнения алгоритма. В наилучшем случае для двоичного поиска наш элемент находится прямо тут -- в центре. Мы находим его за постоянное время вне зависимости от величины остального массива. Для этого используют символ Ω. То есть говорят, что алгоритм выполняется за Ω(1). В лучшем случае он находит элемент очень быстро. Не важно насколько большой массив. Но вот в худшем случае понадобится выполнить (log n) проверок и разделений массива, чтобы найти нужный элемент. Верхняя граница для худшего случая обозначается "большим О", как вы уже знаете. Таким образом получается O(log n), но Ω(1). Для сравнения линейный поиск, в котором мы просматриваем каждый элемент в массиве, чтобы найти нужный, в лучшем случае Ω(1). То есть снова первый элемент оказывается тем самым, что мы ищем. Поэтому не важно насколько большой у нас массив. В худшем случае искомый элемент находится в самом конце. И придётся пройти через все n элементов массива, чтобы его найти. Вот так, если мы ищем 3. То есть его время исполнения O(n), так как оно пропорционально числу элементов массива. Ещё используется символ Θ. С его помощью описываются алгоритмы, у которых лучшее и худшее время одинаковое. Как в случае алгоритма поиска длины строки, о котором мы говорили ранее. Того, где мы сохраняем длину в переменной заранее, а в последствии просто читаем её за постоянное время. Без разницы, какое именно число мы сохраняем в этой переменной, мы будем на него смотреть. В лучшем случае мы смотрим значение и получаем длину строки. То есть Ω(1) или постоянное время для лучшего случая. В худшем случае мы смотрим значение и получаем длину строки. То есть O(1) или постоянное время для худшего случая. Таким образом лучший и худший случаи одинаковые. И можно сказать, что алгоритм исполняется за время Θ(1). Подводя итог, у нас есть хорошие способы рассуждения об эффективности кода без выяснения того, сколько реального времени он потребует для выполнения. Такое время зависит от большого числа внешних факторов, таких как аппаратное и программное обеспечение, а также специфика самого кода. А ещё мы можем чётко рассуждать о том, что будет, когда размер входных данных возрастёт. Если у нас есть алгоритм O(n²), или ещё хуже алгоритм O(2ⁿ), то есть один из самых быстро возрастающих видов, тогда замедление действительно будет трудно не заметить при работе с увеличивающимися объёмами данных. Это и есть асимптотическая сложность. Спасибо за внимание.
История вопроса
Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа :
«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь - выбор конфигурации, котрая приведёт к минимизации времени, необходимого для выполнения вычисления» .
Ранние электронные компьютеры были очень ограничены как по скорости, так и по памяти. В некоторых случаях было осознано, что существует компромисс времени и памяти , при котором задача должна либо использовать большое количество памяти для достижения высокой скорости, либо использовать более медленный алгоритм, использующий небольшое количество рабочей памяти. В этом случае использовался наиболее быстрый алгоритм, для которого было достаточно имеющейся памяти.
Современные компьютеры много быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:
«В установившихся технических дисциплинах улучшение на 12% легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании»
Обзор
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.
Производители компьютеров периодично выпускают новые модели, зачастую более мощные . Стоимость программного обеспечения может быть достаточно велика, так что в некоторых случаях проще и дешевле для достижения лучшей производительности купить более быстрый компьютер, обеспечивающий совместимость с существующим компьютером.
Существует много путей измерения используемых алгоритмом ресурсов. Два наиболее используемых измерения - скорость и используемая память. Другие измерения могут включать скорость передачи, временное использование диска, долговременное использование диска, потребление энергии, совокупная стоимость владения , время отклика на внешние сигналы и так далее. Многие из этих измерений зависят от размера входных данных алгоритма (то есть от количеств требующих обработки данных). Измерения могут также зависеть от способа, в котором данные представлены (например, некоторые алгоритмы сортировки плохо работают на уже сортированных данных или когда данные отсортированы в обратном порядке).
На практике существуют и другие факторы, влияющие на эффективность алгоритма, такие как требуемая точность и/или надёжность. Как объяснено ниже, способ реализации алгоритма может также дать существенный эффект на фактическую эффективность, хотя многие аспекты реализации относятся к вопросам оптимизации.
Теоретический анализ
В теоретическом анализе алгоритмов обычной практикой является оценка сложности алгоритма в его асимптотическом поведении, то есть для отражения сложности алгоритма как функции от размера входа n используется нотация «O» большое . Эта оценка, в основном, достаточно точна при большом n , но может привести к неправильным выводам при малых значениях n (так, сортировка пузырьком, считающаяся медленной, может оказаться быстрее «быстрой сортировки», если нужно отсортировать лишь несколько элементов).
Некоторые примеры нотации «O» большое:
| Обозначение | Название | Примеры |
|---|---|---|
| O (1) {\displaystyle O(1)\,} | постоянное | Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хэш-функции для выбора элемента. |
| O (log n) {\displaystyle O(\log n)\,} | логарифмическое | Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева , как и операции в биномиальной куче . |
| O (n) {\displaystyle O(n)\,} | линейное | Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n -битных чисел с использованием сквозного переноса . |
| O (n log n) {\displaystyle O(n\log n)\,} | квазилинейное , логарифмически линйное | Вычисление быстрого проеобразования Фурье , пирамидальная сортировка , быстрая сортировка (лучший и средний случай), сортировка слиянием |
| O (n 2) {\displaystyle O(n^{2})\,} | квадратное | Умножение двух n -значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла , быстрая сортировка (худший случай), сортировка выбором , сортировка вставками |
| O (c n) , c > 1 {\displaystyle O(c^{n}),\;c>1} | экспоненциальное | Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования . Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора |
Проверочные испытания: измерение производительности
Для новых версий программного обеспечения или для обеспечения сравнения с соперничающими системами иногда используются тесты , позволяющие сравнить относительную производительность алгоритмов. Если, например, выпускается новый алгоритм сортировки , его можно сравнить с предшественниками чтобы убедиться, что алгоритм по меньшей мере столь же эффективен на известных данных, как и другие. Тесты производительности могут быть использованы пользователями для сравнения продуктов от различных производителей для оценки, какой продукт будет больше подходить под их требования в терминах функциональности и производительности.
Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как например Roy Longbottom’s PC Benchmark Collection , а The Computer Language Benchmarks Game сравнивает производительность реализаций типичных задач в некоторых языках программирования.
Вопросы реализации
Вопросы реализации могут также повлиять на фактическую эффективность. Это касается выбора языка программирования и способа, каким алгоритм фактически закодирован, выбора транслятора для выбранного языка или используемых опций компилятора, и, даже, используемой операционной системы. В некоторых случаях язык, реализованный в виде интерпретатора , может оказаться существенно медленнее, чем язык, реализованный в виде компилятора
Есть и другие факторы, которые могут повлиять на время или используемую память, но которые оказываются вне контроля программиста. Сюда попадает выравнивание данных , детализация данных , сборка мусора , параллелизм на уровне команд и вызов подпрограмм .
Некоторые процессоры имеют способность выполнять векторные операции , что позволяет одной операцией обработать несколько операндов. Может оказаться просто или непросто использовать такие возможности на уровне программирования или компиляции. Алгоритмы, разработанные для последовательных вычислений могут потребовать полной переработки для использования параллельных вычислений .
Другая проблема может возникнуть с совместимостью процессоров, в которых команды могут быть реализованы по другому, так что команды на одних моделях могут быть относительно более медленными на других моделях. Это может оказаться проблемой для оптимизирующего компилятора.
Измерение использования ресурсов
Измерения обычно выражаются как функция от размера входа n .
Два наиболее важных измерения:
- Время : как долго алгоритм занимает процессор.
- Память : как много рабочей памяти (обычно RAM) нужно для алгоритма. Здесь есть два аспекта: количество памяти для кода и количество памяти для данных, с которыми код работает.
Для компьютеров, питающихся от батарей (например, лэптопов) или для очень длинных/больших вычислений (например, на суперкомпьютерах), представляют интерес измерения другого рода:
- Прямое потребление энергии : энергия, необходимая для работы компьютера.
- Косвенное потребление энергии : энергия, необходимая для охлаждения, освещения, и т.п.
В некоторых случаях нужны другие, менее распространённые измерения:
- Размер передачи : пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие . Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
- Внешняя память : память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
- Время отклика : параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
- Общая стоимость владения : параметр важен, когда предназначен для выполнения одного алгоритма.
Время
Теория
Этот вид тестов существенно зависит также от выбора языка программирования, компилятора и его опций, так что сравниваемые алгоритмы должны быть реализованы в одинаковых условиях.
Память
Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ пространственной сложности алгоритма , чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое .
Существует четыре аспекта использования памяти:
- Количество памяти, необходимой для хранения кода алгоритма.
- Количество памяти, необходимое для входных данных.
- Количество памяти, необходимое для любых выходных данных (некоторые алгоритмы, такие как сортировки, часто переставляют входные данные и не требуют дополнительной памяти для выходных данных).
- Количество памяти, необходимое для вычислительного процесса во время вычислений (сюда входят именованные переменные и любое стековое пространство, необходимое для вызова подпрограмм, которое может быть существенным при использовании рекурсии).
Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.
Современные компьютеры могут иметь относительно большое количество памяти (возможно, гигабайты), так что сжатие используемой алгоритмом памяти в некоторое заданное количество памяти требуется меньше, чем ранее. Однако, существование трёх различных категорий памяти существенно:
- Кэш (часто, статическая RAM) – работает на скоростях, сравнимых с ЦПУ
- Основная физическая память (часто, динамическая RAM) – работает чуть медленнее ЦПУ
- Виртуальная память (зачастую, на диске) – даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.
Алгоритм, необходимая память которого укладывается в кэш компьютера, работает много быстрее, чем алгоритм, умещающийся в основную память, который, в свою очередь, будет много быстрее алгоритма, который использует виртуальное пространство. Усложняет ситуацию факт, что некоторые системы имеют до трёх уровней кэша. Различные системы имеют различное количество этих типов памяти, так что эффект памяти для алгоритма может существенно отличаться при переходе от одной системы к другой.
В ранние дни электронных вычислений, если алгоритм и его данные не помещались в основную память, он не мог использоваться. В наши дни использование виртуальной памяти обеспечивает огромную память, но за счёт производительности. Если алгоритм и его данные умещаются в кэш, можно получить очень высокую скорость, так что минимизация требуемой памяти помогает минимизировать время. Алгоритм, который не помещается полностью в кэш, но обеспечивает локальность ссылок может работать сравнительно быстро.
В заключении дается последовательное, логически стройное изложение полученных итогов и их соотношение с общей целью (гипотезой) и задачами исследования, делаются обобщенные выводы, формулируются взгляды и предложения автора по совершенствованию изучаемой проблемы. Объем текста заключения в выпускной квалификационной работе строго не регламентирован - обычно он составляет 1,5 - 3 страницы.
Всписке использованных источников в обязательном порядке указываются те документы, материалы, периодическая печать, литература, которые использованы в исследовании. Не следует делать список слишком большим; недопустимо также включать в него тексты, не имеющие отношения к исследуемой проблеме.
Составление списка использованных источников и литературы – один из важнейших этапов работы над исследованием, поскольку отражает самостоятельный, творческий подход ее автора к отбору научной литературы и изучению избранной проблемы и позволяет судить о степени серьезности и обоснованности проведенного исследования.
При необходимости в библиографическом списке могут быть, например, такие разделы, как:
1. Документы государственных органов и общественных организаций;
2. Документы архивов;
3. Справочные и статистические издания;
4. Учебные и учебно-методические издания;
5. Научные монографии и статьи;
7. Периодическая печать;
Список периодических и учебных изданий, литературы, диссертаций и авторефератов формируется по алфавиту фамилий авторов и заглавийкниг/статей.
Число источников в библиографическом списке выпускной квалификационной работы не может быть меньше 25-30 наименований.
Оформляется в соответствии с ГОСТ 2003 или ГОСТ Р 7.0.5-2008 «Библиографическая ссылка».
Примеры библиографического описания цитируемых источников
1. Турута Е.Ф. Активные SMD–компоненты: маркировка, характеристики, замена. – СПб.: Наука и техника, 2006. – 544с.
2. Ульрих В.А. Микроконтроллеры PIC16X7XX. – СПб.: Наука и техника, 2002. – 320 с.
Книга имеет редактора
1. Ремизевич Т.В. Микроконтроллеры для встраиваемых приложений: от общих переходов – к семействам HC05 и HC08 фирмы Motorola. /под ред. Кирюхина И.С. – М.: ДОДЭКА, 2000. – 272 с.
Определенный вид работы (учебник, справочник, энциклопедия и.т.п.)
1. Финкельштейн М.И. Основы радиолокации: Учеб. для вузов. – М.: Радио и связь, 1983. – 536 с.
2. Гук М. Аппаратные средства IBM PC: Энциклопедия. – СПб.: Изд-во «Питер», 1999. – 816 с.
1. Игловский И.Г. Слаботочные электрические реле: Справочник / И.Г. Игловский, Г.В. Владимиров. – М.: КУбК-а, 1996. – 560 с.
2. Романычева Э.Т. Инженерная и компьютерная графика / Э.Т. Романычева, Т.Ю. Соколова, Г.Ф. Шандурина. – М.: ДМК Пресс, 2001. – 592 с.
Если книга написана четырьмя авторами и издание имеет редактора, то все они перечисляются за косой чертой (/). Если книга имеет более четырех авторов, то после заглавия за косой чертой (/) перечисляются первые три и добавляются слова «и др».
3. Радиотехнические системы: Учеб. для вузов по спец. «Радиотехника» / Ю.П. Гришин, В.П. Ипатов, Ю.М. Казаринов и др.; Под ред. Ю.М. Казаринова. – М.: Высш. шк., 1990. – 496 с.
Ели редактора у издания нет, то блок «; Под ред. Ю.М. Казаринова.», отсутствует.
Книга переведена с другого языка и не имеет автора
1. Ресурсы Microsoft Windows Server 4.0. Книга 1: пер. с англ. – СПб.: BHV – Санкт-Петербург, 1997. – 408 с.
Статьи из журнала
1. Однобоков В.В. Обоснование магистрального метода оптимального распределения ресурсов // Научно-технические ведомости. - СПб.: Изд-во СПБГПУ, 2003. – вып. 4. – С.55-62.
Статьи из сборника
1. Глазырин Б. Э. Автоматизация выполнения отдельных операций в Word 2000 // Office 2000: 5 кн. в 1 – М., 2002. – Т. 3, Гл. 14. – С. 281–298.
Описание статьи дается на заглавие, если книга написана четырьмя и более авторами. Если статья написана четырьмя авторами, то все они перечисляются за косой чертой (/).
1. Боголюбов А. Н. О вещественных резонансах в волноводе с неоднородным заполнением / А. Н. Боголюбов, А. Л. Делицын, M. Д. Малых // Вестн. Моск. ун-та. Сер. 3, Физика. Астрономия. – 2001. – № 5. – С. 23–25.
Стандарты
1. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения: ГОСТ 19.701–90 (ИСО 5807–85). – Введ 1992–01–01. – М.: Госстандарт СССР: Изд-во стандартов, 1991. – 26 с.
2. Аппаратура радиоэлектронная бытовая. Входные и выходные параметры и типы соединений. Технические требования: ГОСТ Р 51771–2001. – Введ 2002–01–01. – М.: Госстандарт России: Изд-во стандартов, 2001. – 27 с.
Патентные документы
1. Приемопередающее устройство: пат. 2187888 Рос. Федерация / Чугаева В.И.; заявитель и патентодатель Воронеж. науч.-исслед. ин-т связи. – № 2000131736/09; заявл. 18.12.00; опубл. 20.08.02, Бюл. № 23 (II ч.). – 3 с.
Электронные ресурсы удаленного доступа
1. Ю. А. Кочетов. Теория принятия решений / Новосибирский гос–ный ун–т. – Режим доступа: http://math.nsc.ru/LBRT/k5/or.html
2. М. Перов. Организация работы с древовидными списками // Мир ПК – Электрон. журнал. – Изд-во "Открытые системы", 2008. –№ 1. – Режим доступа к журн.: http://www.osp.ru
3. Исследовано в России: многопредмет. науч. журн. / Моск. физ.-техн. ин-т. – Электрон. журн. – Долгопрудный: МФТИ, 1998. – Режим доступа к журн.: http://zhurnal.mipt.rssi.ru. – № гос. регистрации 0329900013.
Электронные ресурсы локального доступа
1. Internet шаг за шагом. – Электрон. дан. и прогр. – СПб. : ПитерКом, 1997. – 1 электрон. опт. диск (CD-ROM) + прил. (127 с.)
2. Большой толковый словарь английского и русского языков: 2 в 1. – Электрон. дан. и прогр. – Maccelesfield (UK): Europa House, 1999. - 1 электрон. опт. диск (CD-ROM).
3. Visio Professional: библиотека инженера–конструктора 5.0. – Электрон. дан. и прогр. – 1997. – 1 электрон. опт. диск (CD-ROM).
В список включаются 2 статьи на русском (обязательные) + 2 переводные на англ. (необязательные), написанные с участием соискателя.
Приложения
Приложениявключаются только в том случае, если имеются дополнительные и вспомогательные материалы, загромождающие текст основной части ВКР и на них есть ссылки в самой работе.
В качестве приложений возможно включать следующие материалы:
– акт внедрения результатов исследования в производство или в учебный процесс;
– заявка на патент или полезную модель;
– отчет о НИР, представленный на конкурс студенческих работ;
– макеты устройств, пакеты прикладных программ, информация о докладах на конференциях по теме ВКР и др.
– протоколы проведенных исследований и т.д..
3.3 Подготовка и оформление окончательного варианта ВКР
Требования к оформлению
Текст ВКР должен быть выполнен печатным способом с использованием компьютера и принтера на одной стороне белой бумаги формата А4 по ГОСТ 9327-60.
Основной текст работы печатается через 1,5 интервал (27-30 строк на странице) и через 1 интервал (ссылки и сноски) шрифтом Times New Roman, размером 14 (основной текст), 12 – текст в ссылках, сносках и таблицах. Размер левого поля 30 мм, правого – 10 мм, верхнего и нижнего – по 20 мм. Текст работы выравнивается по ширине.
Качество напечатанного текста и оформления иллюстраций, таблиц должно удовлетворять требованию их четкого воспроизведения. В ВКР должны быть четкие линии, буквы, цифры и знаки.
Опечатки, описки и другие неточности, обнаруженные в тексте, допускается исправлять подчисткой или закрашиванием белой краской с последующим нанесением исправленного текста (графики) машинным или рукописным способом. Наклейки, повреждения листов ВКР, помарки не допускаются.
Фамилии, названия учреждений и другие имена собственные в тексте ВКР приводят на языке оригинала. Допускается транслитерировать имена собственные и приводить названия учреждений в переводе на русский язык с добавлением (при первом упоминании) оригинального названия. Имена следует писать в следующем порядке: фамилия, имя, отчество или – фамилия, инициалы через пробелы, при этом не допускается перенос инициалов отдельно от фамилии на следующую строку.
Сокращение русских слов и словосочетаний в тексте ВКР выполняется по ГОСТ 7.12-93, сокращение слов на иностранных европейских языках – по ГОСТ 7.11-2004. Не допускаются сокращения следующих слов и словосочетаний: «так как», «так называемый», «таким образом», «так что», «например». Если в ВКР принята особая система сокращения слов и наименований, то перечень принятых сокращений должен быть приведен в структурном элементе ВКР «Определения, обозначения и сокращения». В тексте ВКР, кроме общепринятых буквенных аббревиатур, допускается использовать введенные их авторами буквенные аббревиатуры, сокращённо обозначающие какие-либо понятия из соответствующих областей знания. При этом первое упоминание таких аббревиатур указывается в круглых скобках после полного наименования, в дальнейшем они употребляются в тексте без расшифровки.
Нумерация разделов, подразделов, пунктов, подпунктов
Наименования структурных элементов «СОДЕРЖАНИЕ», «ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ», «ВВЕДЕНИЕ», «ЗАКЛЮЧЕНИЕ», «СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ» являются заголовками структурных элементов ВКР.
Заголовки структурных элементов ВКР пишутся в середине строки прописными буквами без точки, не подчёркиваются, например:
ВВЕДЕНИЕ
Каждый структурный элемент ВКР следует печатать с нового листа (страницы), в том числе разделы основной части.
Разделы, подразделы, пункты и подпункты следует нумеровать арабскими цифрами и записывать с абзацного отступа. Разделы должны иметь порядковую нумерацию в пределах всего текста, за исключением приложений. Пример – 1, 2, 3 и т. д. Например:
3 Исследование эффективности полученных решений
Подразделы нумеруются в пределах раздела. Номер подраздела включает номер раздела и подраздела, разделённые точкой. Например, 1.1, 1.2, 1.3 и т.д.
Пункты должны иметь порядковую нумерацию в пределах каждого подраздела. Номер пункта включает номер раздела и порядковый номер подраздела и пункта, разделённые точкой. Например, 1.1.1, 1.1.2 и т.д.
Номер подпункта включает номер раздела, подраздела, пункта и порядковый номер подпункта, разделённые точкой. Например, 1.1.1.1, 1.1.1.2 и т. д. Если раздел состоит из одного подраздела, то подраздел не нумеруется. Если подраздел состоит из одного пункта, то пункт не нумеруется. Если пункт состоит из одного подпункта, то подпункт не нумеруется. После номера раздела, подраздела, пункта и подпункта в тексте точку не ставят.
Пример непосредственно СОДЕРЖАНИЯ
ВВЕДЕНИЕ5
1 Обзор задач и работ по теме исследования 7
2 Проектирование информационных моделей и разработка алгоритмов10
2.1 Выбор методов и средств проектирования10
2.2 Логическое проектирование системы11
2.3 Физическое проектирование системы13
2.4 Проектирование макета пользовательского интерфейса15
2.5 Алгоритмы работы18
3 Технология программной реализации разработанных моделей и алгоритмов25
4.1 Выбор средств программной реализации25
4.2 Программная реализация пользовательского интерфейса системы29
4.3 Обеспечение эксплуатационной и информационной безопасности разработанной системы33
4.4 Обоснование и экономический расчет затрат на разработку системы39
4 Исследование эффективности полученных решений43
4.1 Исследование эффективности проектных решений43
4.2 Исследование эффективности технологических решений48
4.3 Исследование эффективности разработанных алгоритмов51
ЗАКЛЮЧЕНИЕ55
СПИСОК ЛИТЕРАТУРЫ57
ПРИЛОЖЕНИЯ59
П.1 Графический материал к пояснительной записке59
П.2 Листинг подпрограммы фильтрации и группировки данных 61
П.3 Акт внедрения разработки 65
Разделы, подразделы должны иметь заголовки. Заголовки должны четко и кратко отражать содержание разделов, подразделов.
Заголовки разделов, подразделов следует печатать с абзацного отступа с прописной буквы без точки в конце, не подчеркивая. Если заголовок состоит из двух предложений, их разделяют точкой. Переносы слов в заголовках не допускаются. Заголовок подраздела не должен быть последней строкой на странице.
Перед каждым элементом перечисления следует ставить дефис. При необходимости ссылки в тексте ВКР на один из элементов перечисления вместо дефиса ставятся строчные буквы в порядке русского алфавита, начиная с буквы а (за исключением ё, з, й, о, ч, ъ, ы, ь). Для дальнейшей детализации перечислений необходимо использовать арабские цифры, после которых ставится скобка, а запись производится с абзацного отступа.
Например,
Нумерация страниц
Страницы ВКР следует нумеровать арабскими цифрами, соблюдая сквозную нумерацию по всему тексту. Номер страницы проставляют в центре нижней части листа без точки.
Титульный лист, задание на ВКР и содержание включают в общую нумерацию страниц ВКР, номера страниц на них не проставляют.
Иллюстрации и таблицы, размещенные в тексте ВКР на отдельных листах, включают в общую нумерацию страниц. Иллюстрации и таблицы на листе формата А3 (297×420) учитывают как одну страницу.
Нумерация страниц ВКР и приложений, входящих в состав ВКР, должна быть сквозная.
Формулы
Формулы набираются с использованием редактора формул MicrosoftEquation (входит в состав MS Office). При этом под «формулой» понимается любая последовательность не менее чем двух символов, не являющаяся словом (названием, аббревиатурой) в русском или каком-либо другом языке.
Нумерация формул осуществляется строго последовательно (в порядке расположения в тексте пояснительной записки), в круглых скобках, арабскими цифрами, начиная с 1. Номера формул проставляются строго по правому краю. При этом нумеруются только те формулы, на которые имеются ссылки в тексте. Формулы, на которые не содержатся ссылки в тексте статьи, не нумеруются.
Текст формулы выравнивается по левой стороне на расстоянии 1.25 сантиметра от левого края текста (с красной строки) независимо от того, нумеруется данная формула или нет:
Если формула не умещается на строке, то она переносится на следующую строку после знака «=» или после математических знаков «+», «–», и др. При этом выравнивание второй строки формулы остается прежним – 1,25 сантиметра от левого края текста статьи, как это показано в примере с формулой (2):
| (2) |
Между текстом и следующей за ним формулой, в многострочных формулах и между формулой и следующим за ней текстом оставляются пустые строки.
Пояснение значений символов и числовых коэффициентов следует приводить непосредственно под формулой, в той же последовательности, в которой они даны в формуле. Значение каждого символа и числового коэффициента следует давать с новой строки. Первую строку пояснения начинают со слова "где", без двоеточия после него. Например:
Абсолютное снижение трудовых затрат (DТ):
DТ = Т0 - Т1,
где Т0 – трудовые затраты на обработку информации по базовому варианту;
Т1 – трудовые затраты на обработку информации по предлагаемому варианту.
Для набора переменных (букв) следует использовать шрифт Times, курсив, не жирный (устанавливается в настройках MicrosoftEquation): например, t, V, s, U. Для набора цифр следует использовать шрифт Times, не курсив (!), не жирный (устанавливается в настройках MicrosoftEquation): например, 1, 2, 15. Размер шрифта для переменных и цифр – 14 пунктов. Размеры остальных элементов формул (устанавливаются в настройках MicrosoftEquation):
Крупный индекс – 8 пунктов;
Мелкий индекс – 6 пунктов;
Крупный символ (знаки суммы, интеграла) – 18 пунктов;
Мелкий символ – 12 пунктов.
Для обозначения векторов, матриц допустимо использование других элементов стилистического оформления шрифтов, например, не курсивных, жирных букв, шрифта Arial и т.п.
Для стандартных функций (тригонометрических, логарифмических и т.п.), а также для специальных символов (sup, inf и т.п.) следует использовать шрифт Times, не жирный, не курсив (что соответствует стандартным настройкам MicrosoftEquation), например,
Иллюстрации
Иллюстрации (чертежи, графики, диаграммы, схемы), помещаемые в ВКР, должны соответствовать требованиям государственных стандартов Единой системы конструкторской документации. 9.9.2 Все иллюстрации в тексте ВКР (графики, чертежи, схемы, диаграммы и др.) размещают непосредственно после первой ссылки на них (или на следующей странице) и обозначают словом «Рисунок».
В тексте пояснительной записки может быть некоторое количество иллюстраций, которые могут представлять собой схемы алгоритмов, структуры вычислительных центров, макеты обрабатываемых программой производственных документов, графики и т. д. Все рисунки оформляются на чертежной бумаге (формат А4) на отдельных листах. Надписи на рисунках также должны быть выполнены стандартным шрифтом.
Иллюстрации за исключением иллюстраций приложений, следует нумеровать арабскими цифрами сквозной нумерацией. Допускается нумеровать иллюстрации в пределах раздела. В этом случае номер иллюстрации состоит из номера раздела и порядкового номера иллюстрации, разделенных точкой. Например – Рисунок 1.1. При ссылках на иллюстрации следует писать "... в соответствии с рисунком 2" при сквозной нумерации и "... в соответствии с рисунком 1.2" при нумерации в пределах раздела.
Иллюстрации, при необходимости, могут иметь наименование и пояснительные данные (подрисуночный текст). Слово "Рисунок" и наименование помещают после пояснительных данных и располагают образом: Рисунок 1 - Детали прибора.
Рисунок 1 - Подпись к рисунку выравнивается по центру, печатается нежирным шрифтом размером 12 пунктов и при необходимости может быть
продолжена на следующей строке
После подрисуночной подписи оставляется одна пустая строка и продолжается печать текста статьи.
Таблицы
Каждая таблица должна иметь нумерационный и тематический (желательно) заголовок.
Нумерационный заголовок нужен для того, чтобы упростить связь таблицы с текстом; при ссылке в тесте достаточно указать: табл. 1. Таблицы нумеруются последовательно в порядке расположения в тексте пояснительной записки, арабскими цифрами. Слово «Таблица» (с заглавной буквы) и ее номер печатаются курсивом, и выравнивается по правому краю. Между словом «Таблица» и предшествующим абзацем оставляется одна пустая строка. После номера таблицы точка не ставится.
Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.
Память или время
Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.
Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.
Оценка порядка
При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A находит максимальный элемент в каждой строке.
for i:=1 to N do
begin
max:=A;
for j:=1 to N do
begin
if A>max then
max:=A
end;
writeln(max);
end;
В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2).
Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.
При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.
Определение сложности
Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше.
В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2).
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2)*O(N^3)=O(N^5).
Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2)+O(N^3)=O(N^3). Следующий фрагмент имеет именно такую сложность:
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
{какое-то действие}
end;
procedure Both;
begin
Fast;
Slow;
end;
Сложность рекурсивных алгоритмов
Простая рекурсия
Напомним, что рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя.Рассмотрим рекурсивную реализацию вычисления факториала:
function Factorial(n: Word): integer;
begin
if n > 1 then
Factorial:=n*Factorial(n-1)
else
Factorial:=1;
end;
Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).
Многократная рекурсия
Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее.Рассмотрим такую процедуру:
procedure DoubleRecursive(N: integer);
begin
if N>0 then
begin
DoubleRecursive(N-1);
DoubleRecursive(N-1);
end;
end;
Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.
Объёмная сложность рекурсивных алгоритмов
Для всех рекурсивных алгоритмов очень важно понятие объёмной сложности. При каждом вызове процедура запрашивает небольшой объём памяти, но этот объём может значительно увеличиваться в процессе рекурсивных вызовов. По этой причине всегда необходимо проводить хотя бы поверхностный анализ объёмной сложности рекурсивных процедур.Средний и наихудший случай
Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A.function Locate(data: integer): integer;
var
i: integer;
fl: boolean;
begin
fl:=false; i:=1;
while (not fl) and (i<=N) do
begin
if A[i]=data then
fl:=true
else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.
С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).
Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).
В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.
Общие функции оценки сложности
Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой.1. C – константа
2. log(log(N))
3. log(N)
4. N^C, 0
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).
Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.
