Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
|
1.2. А
ЛГОРИТМЫ , АНАЛИЗ АЛГОРИТМОВ Как известно, алгоритм представляет собой описание способа решения некоторой задачи [12-14]. Но обычно для решения одной и той же задачи может быть предложено несколько способов, т.е. алгоритмов. Соответствен- но возникает проблема выбора наилучшего из них. Такой выбор возможен, если определены оцениваемые характеристики и степень значимости каждой из них. Главной оцениваемой характеристикой алгоритма является, очевидно, обеспечиваемая им скорость решения задачи (временная эффективность) [27]. Вторая важная характеристика – это сложность реализации. Очевидно, не при всех обстоятельствах следует отдавать предпочтение более быстрому, но и более сложному алгоритму. Если скорость выполнения не является кри- тически важной, то менее сложный в реализации алгоритм упростит процесс отладки из-за меньшей вероятности возникновения ошибки. Наконец, неко- торые алгоритмы для своей реализации могут требовать использования до- полнительного объема памяти для хранения промежуточных данных. Каким же образом сравнить алгоритмы по скорости выполнения. Наи- более очевидный способ – реализовать их и выполнить на одном и том же компьютере с одним и тем же набором данных. Но сразу же возникает во- прос: зачем мне реализовывать несколько алгоритмов, если в конечном счете нужен только один? Кроме того, где гарантия, что выбранный для тестирова- ния набор данных не является в каком-то смысле «плохим» для некоторых 5 / 23 6 алгоритмов. Использование же нескольких тестовых наборов делает проце- дуру выбора неприемлемо трудной. Поэтому для анализа алгоритмов используют теоретические методы, главным из которых является метод асимптотической оценки временной эффективности [2, 27]. Суть этого метода заключается в установлении функциональной зависимости числа выполняемых алгоритмом действий от объема исходных данных в предельном случае больших объемов этих дан- ных. Уточним понятия выполняемого алгоритмом действия и объема исход- ных данных, называемого также размерностью задачи. Будем исходить из того, что алгоритм записан на языке C#. Тогда под действием алгоритма будем понимать выражение, не содержащее вызова ме- тодов. Такие выражения содержат небольшое число операций и время их вы- числения (выполнения действия алгоритма) можно считать примерно одина- ковым. Что касается объема исходных данных, то поскольку речь в основном будет идти о работе со структурами данных, в качестве такового естественно выбрать число элементов в структуре. Рассмотрим в качестве примера алгоритм поиска наибольшего значе- ния в массиве, содержащем N целых чисел. В этом случае размерностью за- дачи является размер массива N. Download 1.85 Mb. Do'stlaringiz bilan baham: 
|