Методы сортировок и их реализации. Беляева И.В - 7 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

поскольку
они
очень
сильно
зависят
от
стиля
программирования
и
не
позволяют
определить,
какой
из
алгоритмов
эффективнее.
2.
На
каком
компьютере
должны
выполняться
программы?
Особенностей
конкретного
компьютера
также
не
позволяют
сравнить
эффективность
алгоритмов.
Один
компьютер
может
работать
намного
быстрее
другого,
поэтому
для
выполнения
программ
необходимо
применять
один
и
тот
же
компьютер.
Какой
компьютер
выбрать?
Конкретные
операции,
составляющие
основу
алгоритма
А 1
на
одном
из
компьютеров
могут
выполняться
быстрее,
чем
операции
алгоритма
А
2
,
а
на
другом
компьютере
-
наоборот.
Сравнение
эффективности
алгоритмов
не
должно
зависеть
от
особенностей
конкретного
компьютера.
3.
Какие
данные
вводятся
в
программы?
Возможно,
наиболее
сложной
проблемой
является
выбор
тестовых
данных.
Всегда
существует
опасность,
что
при
выборе
конкретной
тестовой
задачи
алгоритмы
окажутся
эффективнее,
чем
на
самом
деле.
Например,
сравнивая
между
собой
последовательный
и
бинарный
поиск
элемента
в
упорядоченном
массиве,
можно
предложить
алгоритмам
найти
наименьший
элемент.
В
этом
случае
алгоритм
последовательного
поиска
сразу
найдет
искомый
элемент.
Следовательно,
анализ
эффективности
не
должен
зависеть
от
выбора
конкретных
данных.
Чтобы
преодолеть
эти
трудности,
специалисты
в
области
компьютерных
наук
разработали
математические
методы
анализа
алгоритмов, не
зависящие
от
их
конкретных
реализаций,
компьютеров
и
выбора
тестовых
данных.
Как
показано
в
следующем
разделе,
эти
методы
начинаются
с
подсчета
основных
операций,
выполняемых
при
решении
задачи.
Бытродействиеe
алгоритмов
Быстродействие
алгоритма
связано
с
количеством
выполняемых
операций,
поэтому
оценить
его
эффективность
можно
путем
их
простого
подсчета.
Рассмотрим
несколько
примеров.
Связанный
список,
допускающий
обход.
Содержимое
связанного
списка,
на
который
ссылается
указатель
head,
можно
вывести
на
экран
с
помощью
следующего
фрагмента
программы.
N
ode
*
сцг
==
head;
<-
1
присваивание
while
(cur
!==
NULL
<-
п+
1
сравнений
{
cout
«
cur->itetn
«
endl
·
<-
n
операций
записи
cur
==
cur->next;
<-
n
присваиваний
} //
Конец
цикла
while
6

Страницы