ВУЗ:
Составители:
Рубрика:
В
предположении,
что
связанный
список
состоит
из
п
узлов,
эти
операторы
выполняют
n+ 1
присваивание,
n+ 1
сравнение
и
п
операций
записи.
Если
каждое
присваивание,
сравнение
и
операция
записи
выполняется
за
а,
Ь
и
с
единиц
времени,
то
на
выполнение
данного
фрагмента
программы
уйдет
(n+ 1)
*(а+с)
+n
*и>
единиц
времени.
Итак,
можно
интуитивно
догадаться,
что
вывод
на
экран
содержимого
100
узлов
связанного
списка
будет
выполняться
дольше,
чем
вывод
содержимого
1
О
узлов.
Вложенные
циклы.
Рассмотрим
алгоритм,
содержащий
вложенные
циклы.
[о«
(!
==
1
до
n)
[о»
(j
==
1
до
')
[о»
(k
==
1
до
5)
Задача
Т
Если
задача
Т
решается
за
t
единиц
времени,
то
на
выполнение
наиболее
глубоко
вложенного
цикла
по
переменной
k
уйдет
5 * t
единиц
времени.
Цикл
по
переменной
j
затратит
5 * t * i
единиц
времени,
а
внешний
цикл
по
переменной
i
будет
выполняться
за
L(
5 * t * i)
==
5 * t * (1 + 2
+...
+ n)
==
5 *t *
п
* (n +1)/2
единиц
времени.
Степень
роста
временных
затрат
Описанные
выше
примеры
демонстрируют,
что
время
выполнения
алгоритма
выражается
функцией,
зависящей
от
размера
задачи.
Способ
измерения
размера
задачи
зависит
от
конкретного
приложения
-
количества
узлов
связанного
списка,
размера
массива
или
количества
элементов
стека.
Итак,
мы
приходим
к
следующим
выводам.
Для
решения
задачи,
имеющей
размер
п,
алгоритм
А
2
затрачивает
n
/
i
единиц
времени.
Для
решения
задачи,
имеющей
размер
п,
алгоритм
В
затрачивает
5*
п
единиц
времени.
Единицы
времени,
используемые
при
оценке
эффективности
этих
алгоритмов,
должны
быть
одинаковыми.
Например,
утверждение
может
выглядеть
так.
Для
решения
задачи,
имеющей
размер
n,
алгоритм
А
затрачивает
С'/5секунд.
n
Выше
мы
уже
перечислили
трудности,
возникающие
на
этом
пути.
2/5
На
каком
компьютере
алгоритм
будет
выполнен
за
n
секунд?
Какая
реализация
этого
алгоритма
выполняется
за
п:
)
/5
секунд?
При
каких
данных
алгоритм
выполнится
за
n
2
/5
секунд?
7
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
