Структуры данных и модели вычислений

         

Эта команда выполняется раз. При




Таблица 12.2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22


Когда команда выполняется -й раз, сумматор содержит , а содержит . Эта команда выполняется раз. При равномерном весовом критерии суммарное время — . При логарифмическом весовом критерии суммарное время равно , где суммирование ведется по . Поскольку , получаем

Емкостная сложность программы при равномерном критерии равна , при логарифмическом — .


Содержание  Назад  Вперед