. Такая оценка может быть сделана только для конкретной реализации алгоритма и на практике обычно не требует

Работа добавлена: 2018-07-05






Временная сложность алгоритмов.

Временная сложность (ВС) – зависимость времени выполнения алгоритма от количества обрабатываемых входных данных. Здесь представляет интерес среднее и худшее время выполнения алгоритма. ВС можно установить с различной точностью. Наиболее точной оценкой является аналитическое выражение для функции:t=t(N), где t – время, N – количество входных данных (размерность). Данная функция называетсяфункцией временной сложности(ФВС).

Например: t = 5N2+ 3*2N + 1. Такая оценка может быть сделана только для конкретной реализации алгоритма и на практике обычно не требуется. Часто бывает достаточно определить лишь порядок функции временной сложности t(N).

Две функцииf1(N)иf2(N)одного порядка, если

Иначе это записывается в виде:f1(N)=О(f2(N))  (Читается " О большое ").

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

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

Примеры определения порядка ВС для некоторых алгоритмов:

  1. Алгоритм линейного поиска. Этот алгоритм может быть использован как для упорядоченного, так и для неупорядоченного массива ключей. Работа алгоритма заключается в том, что при просмотре всего массива, начиная с первого и до последнего элемента, ключ из массива сравнивается с искомым ключом. Если результат сравнения положительный – ключ найден. Если же ни одно сравнение не выполнилось с положительным результатом, то ключа в массиве нет.

ФВС для алгоритма линейного поиска:tл. п.= k1* N =O(N). Действительно, для отыскания ключа в худшем случае придется просмотреть все элементы массива. При этом время проверки каждого элемента одинаково и не зависит от конкретной вычислительной системы.

Оценим среднее время алгоритма, при этом будем исходить из следующего: пусть P– вероятность того, что будет осуществляться поиск элемента с ключомki; при этом предположим, что  , т.е. ключ со значениемki не будет отсутствовать (в таблице обязательно есть элемент, поиск которого осуществляется). Среднее время (), как следует из алгоритма, пропорционально среднему числу операций сравнения () и равно ~=. Если ключи имеют одинаковую вероятность P1=P2=...PN=P, а также учитывая, что,N*P=1, P=1/N, тогда  ,

т.е. при линейном поиске в среднем необходимо просмотреть половину массива.

Рассмотрим упорядоченную таблицу, у которой элементы упорядочены по частоте обращений (по вероятности). Если имеем такую таблицу, то время – худшее:  = О(N).

Распределение осуществляется по закону Зипфа:Pi= c / i,  i = 1, 2, … , N,тогда ~=,

причем ,   (N®¥)

,  ln N – постоянная Эйлера.

Исходя из этого получили:с = 1 / ln N.

  1. Алгоритм бинарного (двоичного) поиска.В словесной форме алгоритм двоичного поиска можно записать следующим образом:

1. Определить середину массива.

2. Если ключ, находящийся в середине массива, совпадает с искомым, поиск завершен.

3. Если ключ из середины массива больше искомого, применить двоичный поиск к первой половине массива.

4. Если ключ из середины массива меньше искомого, двоичный поиск необходимо применить ко второй половине массива.

5. Пункт 1-4 повторять, пока размер области поиска не уменьшается до нуля. Если это произойдет, то ключа в массиве нет.

ФВС для алгоритма бинарного поиска:tб. п.=O(log2N).Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не болееlog2N таких уменьшений, т.е. выполняется не болееlog2N шагов алгоритма.

Изобразим графически функции ВС для линейного и двоичного поиска. Из графика видно, что для малыхN нужно использовать линейный поиск, а для больших N —двоичный поиск.Nкр находятся в пределах 10 .. 1000 в зависимости от характеристик используемого оборудования.

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

Алгоритмы поиска в неупорядоченных массивах

Алгоритм1.алинейного поиска

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

Алгоритм1.б быстроголинейного поиска

Любой алгоритм поиска содержит блок проверки на окончание массива. В алгоритме линейного поиска эта проверка осуществляется каждый раз перед обращением очередному элементу. Однако проверка на окончание массива может осуществляться не при каждом сравнении. Для этого в конец массива включается (N+1)-й элемент, равный искомому. Тогда проверка на окончание массива осуществляется лишь при совпадении очередного элемента с искомым. Если этот элемент находится внутри массива, то поиск заканчивается удачно и элемент считается найденным. Если же этот элемент оказался (N+1)-ым, то искомого элемента в массиве нет.

Анализ алгоритмовлинейного поиска

Для отыскания искомого элемента с использованием алгоритмов линейного поиска в худшем случае придется просмотреть все N элементов массива, следовательно порядок функции ВС будет O(N). В лучшем случае, когда искомый элемент равен первому элементу массива, число сравнений не зависит от количества элементов в массиве  и порядок функции ВС будет O(N).

Оценим среднее время алгоритма, при этом будем исходить из следующего:

пусть P– вероятность того, что будет осуществляться поиск элемента со значениемki; предположим, что  , т.е. элемент со значениемki не будет отсутствовать (в массиве обязательно есть элемент, поиск которого осуществляется).

Среднее время (), как следует из алгоритма, пропорционально среднему числу операций сравнения () и равно ~=. Если ключи имеют одинаковую вероятность P1=P2=...PN=P, а также учитывая, что,N*P=1, P=1/N, тогда  ,

т.е. при линейном поиске в среднем необходимо просмотреть половину массива.

Для экспериментального определения среднего числа сравнений необходимо найти суммарное число сравнений при поиске всех элементов массива и разделить на количество элементов.

Алгоритмы поиска в упорядоченных массивах

Алгоритм2.а быстроголинейного поиска

Применяя алгоритм быстрого линейного поиска для поиска элемента в упорядоченном массиве, поиск можно прекратить, если очередной элемент массива будет больше искомого. Это будет означать, что искомого элемента в массиве нет. В случае поиска элемента, который есть в массиве, этот алгоритм аналогичен алгоритму быстрого линейного поиска в неупорядоченном массиве.

Алгоритм2.б бинарногопоиска

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

Алгоритм бинарного поиска.

1. Определить середину массива.

2. Если элемент, находящийся в середине массива, совпадает с искомым, поиск завершен.

3. Если ключ из середины массива больше искомого, применить бинарный поиск к первой половине массива.

4. Если ключ из середины массива меньше искомого, бинарный поиск необходимо применить ко второй половине массива.

5. Пункт 1-4 повторять, пока размер области поиска не уменьшается до нуля. Если это произойдет – ключа в массиве нет.

Анализ алгоритмабинарного поиска

Порядок функции ВС алгоритма бинарного поиска равен O(log2N). Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не более log2N таких уменьшений, т.е. выполняется не более log2N шагов алгоритма. В лучшем случае, когда искомый элемент находится в середине массива, число сравнений не зависит от количества элементов в массиве  и порядок функции ВС будет O(N).

Определим среднее число шагов при поиске элементов в массиве из N элементов. Для этого подсчитаем суммарное число шагов S при поиске каждого элемента массива. Исходя из алгоритма, не более чем N/2 элементов ищется за log2N шагов,N/4  элементов – за (log2N)-1 шагов, и т.д. Отсюда

S=((N/2)*log2N)+((N/4)*((log2N)-1)+…+1.

Среднее число шагов равно S/N, что составляет O(log2N).

Алгоритм2.в блочногопоиска

Блочный поиск состоит в том, что массив, упорядоченный по возрастанию, разбивается на определённое число блоков. В процессе поиска искомый элемент последовательно сравнивается с последним элементом блоков. Если искомый элемент меньше последнего элемента очередного блока, то искомый элемент может находиться только внутри этого блока. Для поиска элемента в блоке можно применить линейный поиск.

Анализ алгоритма блочного поиска

Пусть массив состоит из N элементов и при поиске разбивается на X равных блоков. Тогда в каждом блоке будет не более N/X элементов. В худшем случае, если искомый элемент окажется в последнем блоке, то для поиска блока потребуется просмотреть X элементов массива. Выполнить линейный поиск в блоке можно, просмотрев не более чем N/X элементов. Следовательно, общее число обрабатываемых элементов не превышает X+N/X. Эта величина зависит от числа блоков и будет минимальна, когда её производная равна нулю, т.е. при X=ÖN. Число записей в блоке так же равноÖN. При таком разбиении массива на блоки в худшем случае понадобиться обработать не более чем 2*ÖN элементов массива, а в среднем -ÖN элементов.




Возможно эти работы будут Вам интересны.

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

2. При этом потребителем изделия может быть как отдельный человек так и коллективы людей предприятия орган

3. Базовые формы База – простая сложен.форма,котор.может быть развита во множество различ.фигурок

4. . За каждым звуком должна быть закреплена определенная буква не должно быть букв не обозначающих звуков.

5. -во и право отдельных стран мира принципа становления и развития в определенной конкретной исторической обс

6. тематичного и многосложного характера требует формирования -целенаправленность усидчивость самоконтроль .

7. Процесс осуществления власти Российского народа необходимо требует гарантии его обеспечения.

8. -либо признака то такая таблица называетсяупорядоченной иначе таблицанеупорядоченная.

9. Реализация идей реформирования высшей школы требует адекватного изменения типов высших учебных заведений

10. Для успешной защиты проекта необходима такая рецензия которая создаст самое благоприятное в.