Вычислительная сложность алгоритма (количество "времени", необходимое для его выполнения) - это приблизительное число операций, выполняемых алгоритмом.
Точное знание количества операций каждого типа, выполненных алгоритмом, не играет существенной роли в его анализе. Интересен только общий характер поведения алгоритмов, а не его подробности.
Точное знание количества операций каждого типа, выполненных алгоритмом, не играет существенной роли в его анализе. Интересен только общий характер поведения алгоритмов, а не его подробности.
Ключевую роль играет скорость роста числа операций - зависимость числа операций конкретного алгоритма от размера входных данных. Она называется скоростью роста алгоритма. При анализе алгоритмов интересен класс скорости роста, к которому относится алгоритм.
Алгоритмы сравниваются по скорости роста числа операций.
Небольшие объёмы входных данных не столь интересны, как то, что происходит при возрастании этих объёмов, поскольку на малых объёмах принципиальная разница оказывается скрытой. При небольшом размере входных данных алгоритм A может требовать меньшего количества операций, чем алгоритм B, но при росте объема входных данных ситуация может поменяться на противоположную.
Алгоритмы сравниваются по скорости роста числа операций.
Небольшие объёмы входных данных не столь интересны, как то, что происходит при возрастании этих объёмов, поскольку на малых объёмах принципиальная разница оказывается скрытой. При небольшом размере входных данных алгоритм A может требовать меньшего количества операций, чем алгоритм B, но при росте объема входных данных ситуация может поменяться на противоположную.
Комментарии
Отправить комментарий