Керимов В.А., Гаджиев Ф.Г.
О МЕТОДАХ ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ *
Аннотация:
в статье рассматриваются некоторые методы оценки сложности алгоритмов решения ряда задач. Крайне медленная работа некоторых алгоритмов доказывает актуальность выяснения практической значимости алгоритмов. Обозначение «Biq О» принято как наиболее актуальный способ оценки сложности алгоритма. Полиномиальные алгоритмы считаются более подходящими для практического использования
Ключевые слова:
сложность алгоритмов, Biq O нотация, Little o нотация, задача о загрузке, схема Горнера, задача o коммивояжере, методы сортировки информации
УДК 51
Керимов В.А.
канд. тех. наук, доцент кафедры «Общая и прикладная математика»
Азербайджанский государственный университет нефти и промышленности
(г. Баку, Азербайджан)
Гаджиев Ф.Г.
канд. тех. наук, доцент кафедры «Общая и прикладная математика»
Азербайджанский государственный университет нефти и промышленности
(г. Баку, Азербайджан)
О МЕТОДАХ ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ
Аннотация: в статье рассматриваются некоторые методы оценки сложности алгоритмов решения ряда задач. Крайне медленная работа некоторых алгоритмов доказывает актуальность выяснения практической значимости алгоритмов. Обозначение «Biq О» принято как наиболее актуальный способ оценки сложности алгоритма. Полиномиальные алгоритмы считаются более подходящими для практического использования.
Ключевые слова: сложность алгоритмов, Biq O нотация, Little o нотация, задача о загрузке, схема Горнера, задача o коммивояжере, методы сортировки информации.
В процессе решения различных вычислительных задач не трудно заметить, как медленно работают многие алгоритмы. Одной из основных причин замедления вычисления является колоссальное число сравнений, связанных с перебором вариантов. Поэтому очень актуален вопрос аналитической оценки практичности применяемого алгоритма. Ниже рассматриваются аналитические методы оценки сложности некоторых алгоритмов [1].
Оценка сложности умножения матриц. При умножении матриц A[1:m,1:k], B[1:k,1:p] строится матрица C[1:m,1:p], для построения каждой ячейки которой требуется k умножений и k-1 сложений. Таким образом, число элементарных операций вычисляется по формуле mp(2k-1). Обозначим, max(m,p,k)=n, то получим mp(2k-1) 2n3-n2=O(n3). Подобным анализом можно заключить, что сложность суммирования матриц A[1:m,1:k], B[1:m,1:k] выражается формулой O(n2). Эту оценку иногда называют «Biq O» нотацией. Наряду с этим иногда рассматривается нижняя оценка сложности, которая называется «Little o» нотацией. Пусть, min(m,k) = n, тo получим нижнюю оценку сложности о(n2). Как видно, классы для верхней и нижней оценки этой задачи совпадают.
Оценка сложности вычисления значения полинома в заданной точке общим методом. Для вычисления значения каждого одночлена требуется n-i операций. Для суммирования полученных одночленов потребуется n операций сложения. Таким образом, число всех операций оценивается по формуле: n+(n-1)+(n-2)+...+2+1+n= +n=0,5n2+1,5n=O(n2).
Оценка сложности вычисления значения полинома в заданной точке по схеме Горнера [3]. Покажем, что при применении схемы Горнера число вычислений значительно сокращается. Например, рассмотрим многочлен 3-го порядка: Нетрудно заметить, что для вычисления последнего выражения необходимо выполнить по три операции умножения и сложения. Если степень многочлена равна n, то применяя схему Горнера необходимо выполнить 2n вычислений, при этом сложность вычислений будет выражаться формулой O(n). Следовательно, метод Горнера лучше, чем общий метод.
Оценка сложности методов сортировки. Оценка практической сложности алгоритма представляется более трудной задачей в сравнении с теоретической сложностью [2,4]. Время работы алгоритма не только зависит от объема входной информации, но также от расположения входных данных, от их значений и т.д., например, скорость работы некоторых алгоритмов сортировки может значительно сократиться, если входной поток информации частично отсортирован. На практике рассматриваются следующие категории сложности алгоритмов сортировки:
1) Максимальная сложность – это оценка времени работы алгоритма в наиболее неблагоприятных условиях;
2) Минимальная сложность – это оценка времени работы алгоритма в наиболее благоприятных условиях;
3) Оценка сложности алгоритма в среднем, - это полусумма максимальной и минимальной сложностей.
Определение: Сложностью некоторого алгоритма А, выполняющего упорядочивание последовательности из n элементов называется количество всех сравнений в наихудшем случае расположения элементов.
В качестве функций временной сложности сортировки, как правило, рассматриваются следующие функции О(n2),О(nlogn),О(n).
Оценка сложности сортировки выбором осуществляется при помощи сравнения каждого элемента со всеми остальными элементами, число сравнений при определении равно ; при определении , и т.д. в результате сортировки по возрастанию получаем последовательность: при которой .
Для обозначения всех сравнений введем функцию = . Тогда для больших значений параметра функция приблизительно будет равно: .
Оценка сложности метода деления «пополам». В каждой последовательности можно найти упорядоченный фрагмент. Суть настоящего метода, взять каждый элемент из неупорядоченной части и привнести его в упорядоченную среду методом деления «пополам». Если в упорядоченной последовательности число элементов четное, метод деления пополам выполняется без проблемы, если же – нечетное при разбиении отрезка «пополам» в одной области будет на единицу больше элементов. Пусть, расставлены по возрастанию. Рассмотрим два случая: 1) k – четное число, тогда : ; 2) k – нечетное число, тогда для оценки р можно использовать альтернативные формулы:
, или . Допустим, - функция, которая оценивает количество сравнений при включении нового элемента в упорядоченную последовательность с к элементами. Выполним анализ функции с возрастанием аргумента k. При k=1, очевидно, . При k=2 количество максимальных сравнений равно 2. Вообще, анализ дает следующие результаты: U(2)=2, U(3)=1+U(1)=2, U(4)=1+U(2)=3,…
(1).
В формуле (1) запись показывает целую часть деления числа k на 2. Напимер, при i=35 для оценки максимального количества сравнений, находим отрезок 35 [2k,2k+1-1], отсюда заключаем:32<35<63. Следовательно, имеем:25<35<26-1. Наконец, заключаем U(i)=6. С другой стороны эту же оценку можно реализовать рекурсивно: U(35)=1+U(17)=2+U(8)=3+U(4)=4+U(2)=5+U(1)=6. Введем новую функцию T2(n) для оценки сложности рассматриваемого метода.
Выполним оценку T2(n) при наихудшем случае расположения элементов заданного массива, т.е. предполагаем, в массиве нет упорядоченного фрагмента. В этом случае возьмем любой элемент заданной последовательности, применяя метод деления «пополам» шаг за шагом постепенно расширяем упорядоченную область. Тогда для оценки количества сравнений в наихудшем случае можно использовать следующую формулу:
T2(n) U(1)+ U(2)+...+ U(n-1) (2).
Например, при n=5 по формуле (2) получаем:
С другой стороны при количество сравнений при обменной сортировке будет равно: . Сравнение результатов и показывает, что метод деления пополам является эффективным. Более того, с возрастанием числа n преимущество этого метода становится подавляющим. Например, при n=10 получаем: T(10) = а при n= 20 получаем:
Задача о загрузке — это задача о рациональной загрузке судна, которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в определении загрузки судна такими грузами, которые приносят наибольшую суммарную прибыль. Допустим, всего 3 вида грузов, грузоподъемность судна 10000 кг. Судно надо загрузить так, чтобы общий вес грузов был максимально близок к 10000 кг, но не завышал этот предел. Пусть веса грузов: холодильник (Х) – 100 кг, генератор (Г) -75 кг, кондиционер (К) – 50 кг. Ниже в скобках указаны количества грузов по выбранным наименованиям. При бинарном ветвлении дерева перебора получим следующие альтернативные планы загрузки: 1. Х(20),Г(50), К(85), 2. Х(20),Г(100), К(10), 3. Х(30),Г(70), К(35), 4. Х(30),Г(90), К(5). Таким образом, при каждом бинарном ветвлении количества холодильников и генераторов было построено 22=4 вариантов. Если грузов n наименований, при бинарном ветвлении количество вариантов будет 2n-1. Например, при n=101, число вариантов будет 2100≈1030 . Пусть коммпьютер за секунду выполняет 109 операций. Подсчитаем время, необходимое для сравнения вариантов и, следовательно, выбора оптимального из них: (1030 ⁄ 109) сек. = 1021 сек. ≈ 107 ∙ 3170978 год. Следовательно, при таком подходе задача практически неразрешима. Да, скорость света высочайшая, но в сравнении с размерами вселенной она мизерная!
СПИСОК ЛИТЕРАТУРЫ:
Kerimov V.A.
Candidate of Technical Sciences, Associate Professor
of the Department of General and Applied Mathematics
Azerbaijan State University of Petroleum and Industry
(Baku, Azerbaijan)
Hajiyev F.G.
Candidate of Technical Sciences, Associate Professor
of the Department of General and Applied Mathematics
Azerbaijan State University of Petroleum and Industry
(Baku, Azerbaijan)
METHODS FOR EVALUATING COMPLEXITY OF ALGORITHMS
Abstract: the article discusses some methods for estimating the complexity of algorithms for solving a number of problems. The extremely slow operation of some algorithms proves the relevance of finding out the practical significance of algorithms. The designation "Biq O" is accepted as the most relevant way to evaluate the complexity of the algorithm. Polynomial algorithms are considered more suitable for practical use.
Keywords: complexity of algorithms, Biq O notation, Little o notation, loading problem, Gorner scheme, traveling salesman problem, information sorting methods.
Номер журнала Вестник науки №4 (61) том 1
Ссылка для цитирования:
Керимов В.А., Гаджиев Ф.Г. О МЕТОДАХ ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ // Вестник науки №4 (61) том 1. С. 299 - 304. 2023 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/7678 (дата обращения: 24.04.2024 г.)
Вестник науки СМИ ЭЛ № ФС 77 - 84401 © 2023. 16+