Оценки времени исполнения
Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный –просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения.
Другой способ – оценить время исполнения. Например, мы можем утверждать, что время поиска есть O(n) (читается так: о большое от n). Это означает, что при больших n время поиска не сильно больше, чем количество элементов. Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите таблицу 1.1, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций. Скорость роста O(lg n) характеризует алгоритмы типа двоичного поиска. Логарифм по основанию 2, lg, увеличивается на 1, когда n удваивается. Вспомните – каждое новое сравнение позволяет нам искать в вдвое большем списке. Именно поэтому говорят, что время работы при двоичном поиске растет как lg n.
| n | lg n | n lg n | n1.25 | n2 |
| 1 | 0 | 0 | 1 | 1 |
| 16 | 4 | 64 | 32 | 256 |
| 256 | 8 | 2,048 | 1,024 | 65,536 |
| 4,096 | 12 | 49,152 | 32,768 | 16,777,216 |
| 65,536 | 16 | 1,048,565 | 1,048,476 | 4,294,967,296 |
| 1,048,476 | 20 | 20,969,520 | 33,554,432 | 1,099,301,922,576 |
| 16,775,616 | 24 | 402,614,784 | 1,073,613,825 | 281,421,292,179,456 |
Таблица 1.1: Скорость роста нескольких функций
Если считать, что числа в таблице 1.1 соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму с временем работы O(lg n) потребуется 20 микросекунд, алгоритму с временем работы O(n1.25) – порядка 33 секунд, алгоритму с временем работы O(n2) – более 12 дней. В нижеследующем тексте для каждого алгоритма приведены соответствующие O-оценки.
Более точные формулировки и доказательства можно найти в приводимых литературных ссылках.Итак¼
Как мы видели, если массив отсортирован, то искать его элементы нужно с помощью двоичного поиска. Однако, не забудем, массив кто-то должен отсортировать! В следующем разделе мы исследует разные способы сортировки массива. Оказывается, эта задача встречается достаточно часто и требует заметных вычислительных ресурсов, поэтому сортирующие алгоритмы исследованы вдоль и поперек, известны алгоритмы, эффективность которых достигла теоретического предела.
Связанные списки позволяют эффективно вставлять и удалять элементы, но поиск в них последователен и потому отнимает много времени. Имеются алгоритмы, позволяющие эффективно выполнять все три операции, мы обсудим из в разделе о словарях.
Еще по теме Оценки времени исполнения:
- Технологическая оценка зданий в монолитном исполнении
- Концепция и методический инструментарий оценки стоимости денег во времени.
- Лабораторная работа М 13 Изучение индивидуальных особенностей восприятия и оценки времени
- [34] Исполнение обязательств. Требования, предъявленные к исполнению обязательств. Ответственность сторон при просрочке исполнения.
- Исполнение обязательств. Требования, предъявленные к исполнению обязательств. Ответственность сторон при просрочке исполнения.
- 522. Отвечает ли банк, принявший к исполнению платежное поручение, за нарушение сроков его исполнения вследствие действий банков-посредников, привлеченных им для исполнения поручения?
- Учет факторов времени, неопределенности и риска при оценке выгод и издержек использования общественных средств
- Глава 3 Разработка регуляризирующего алгоритма получения навигационной оценки на заданный момент времени
- 43. Глагол. Катег-я времени. Знач-е, образ-е и употр-е форм глаг-ного времени. Соотнош-е категории вида и времени.
- 2.2 Использование сглаживающего алгоритма для получения оценки вектора состоянии НКА на момент времени, удаленный от последнего измерения