Α. 1. Анализ сложности и система обозначений 0()

Специалистам в области компьютерных наук часто приходится решать задачу сравнения алгоритмов для определения того, насколько быстро они действуют или сколько памяти для них требуется. Для решения этой задачи предусмотрены два подхода. Первым из них является ^ применение эталонных тестов — прогон реализующих алгоритмы программ на компьютере и измерение быстродействия в секундах и потребления памяти в байтах. Верно, что в конечном итоге нас действительно интересуют именно такие практические характеристики, но эталонное тестирование может оказаться неприемлемым потому, что оно слишком узко направлено, — в нем измеряется производительность конкретной программы, написанной на конкретном языке, функционирующей на конкретном компьютере с конкретным компилятором и с конкретными входными данными. К тому же на основании единственного результата, полученного с помощью эталонного тестирования, трудно предсказать, насколько успешно этот алгоритм будет действовать в случае использования другого компилятора, компьютера или набора данных.