Теория алгоритмов. Зюзысов В.М. - 59 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

может находиться в отношении Q с несколькими элементами множества S (если
кратчайших путей между данными вершинами несколько).
Нам бы хотелось связать с каждым частным случаем проблемы некоторое число,
называемое его размером, которое выражало бы меру количества входных данных.
Например, размером задачи умножения матриц может быть наибольший размер матриц-
сомножителей. Размером
задачи о графах может быть число ребер данного графа.
Решение задачи на компьютере можно осуществлять с помощью различных
алгоритмов. Прежде чем подавать на вход алгоритма исходные данные (то есть элемент
множества I), надо договориться о том, как они представляются «в понятном для
компьютера виде»; мы будем считать, что исходные данные закодированы
последовательностью битов. Формально говоря, представлением элементов некоторого
множества M называется отображение e из M во множество битовых строк. Например,
натуральные числа 0, 1, 2, 3, … обычно представляют битовыми строками 0, 1, 10, 11,
100, … (при этом, например, e(17) = 10001).
Фиксировав представление данных, мы превращаем абстрактную задачу в
строковую, для которой входным данным является битовая строка, представляющая
исходное данное абстрактной задачи
. Естественно считать размером строковой задачи
длину строки.
Асимптотическая временная сложность
Будем говорить, что алгоритм решает строковую задачу за время Ο(T(n)), если на
входном данном битовой строки длины n алгоритм работает время Ο(T(n)).
В качестве временной оценки работы алгоритма вместо общего числа шагов мы
можем подсчитывать число шагов некоторого вида, таких как арифметические операции
при алгебраических вычислениях, число сравнений при сортировке или число обращений
к памяти.
Можно было подумать, что колоссальный рост скорости вычислений, вызванный
появлением нынешнего поколения компьютеров, уменьшит значение эффективных
алгоритмом
. Однако происходит в точности противоположное. Так как компьютеры
работают все быстрее и мы можем решать все большие задачи, именно сложность
алгоритма определяет то увеличение размера задачи, которое можно достичь с
увеличением скорости машины.
Следуя [8], рассмотрим это более подробно. Допустим, у нас есть пять алгоритмов
A
1
–A
5
со следующими временными сложностями:
Алгоритм Асимптотическая временная
сложность
A
1
Ο(n)
A
2
Ο(n log n)
A
3
Ο(n
2
)
A
4
Ο(n
3
)
A
5
Ο(2
n
)
Пусть единицей времени будет одна миллисекунда и мультипликативные
константы в точных оценках временной сложности во всех алгоритмах равны 1. Тогда
алгоритм A
1
может обработать за одну секунду вход размера 1000, в то время как A
5
–
вход размера не более 9. В таблице 1 приведены размеры задач, которые можно решить за
одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.

Страницы