Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 1.4. Сравнение двух способов измерения времени выполнения 
алгоритма 
static void Main(string[] rags) 
{ 
int[] a = new int[n]; 
Random rend = new Random(); 
for (int I = 0; I < n; i++) 
a[i] = rnd.Next() % 500; 
Timing objT = new Timing(); 
Stopwatch stpWatch = new Stopwatch(); 
objT.StartTime(); 
stpWatch.Start(); 
SortInsertion(a); 
stpWatch.Stop(); 
objT.StopTime(); 
Console.WriteLine("StopWatch: " + 
stpWatch.Elapsed.ToString()); 
Console.WriteLine("Timing: " + 
objT.Result().ToString()); 
Console.ReadLine(); 
} 
На рисунке 1.2 показан результат этого сравнения для массива из 100 
тысяч целочисленных значений на процессоре с тактовой частотой в 2.4 ГГц. 
StopWatch: 00:00:16.7604719 
Timing: 00:00:16.1562500 
Рис. 1.2. Сравнение двух способов измерения 
времени выполнения алгоритма 
13 / 23

---

14 
Видно, что время, полученное вторым способом, заметно меньше изме-
ренного средствами класса Stopwatch, что подтверждает факт влияния си-
стемных процессов на результат измерения. 
В
ЫВОДЫ
 
Существует взаимосвязь между способом представления данных для 
решаемой задачи и алгоритмом ее решения. Для представления данных могут 
быть использованы различные структуры данных (массивы, списки, деревья 
и т. д.) [47]. Если рассматривать эти структуры на абстрактном уровне, как 
АДТ, очевидно, что для всех этих структур существует похожий набор опе-
раций, например, добавление, удаление и поиск элементов. Однако реализа-
ция этих операций может существенно отличаться для разных структур дан-
ных. Более того, даже для одной и той же структуры данных, зачастую, могут 
быть предложены разные алгоритмы выполнения операций. В данной главе 
это было продемонстрировано на примере операций сортировки и поиска в 
массивах. 
Наличие нескольких алгоритмов решения одной и той же задачи ставит 
вопрос о выборе лучшего из них. Наиболее часто используемым критерием 
выбора является скорость роста алгоритма – зависимость среднего времени 
его выполнения от размерности задачи, в качестве которой обычно выступает 
число элементов в обрабатываемой структуре данных (например, размер мас-
сива). Для обозначения скорости роста алгоритма используется так называе-
мая O-нотация. Большинство практически значимых алгоритмов имеют ско-
рость роста не выше O(N
k
) с небольшим значением k. 
Существует возможность экспериментальной проверки закона скоро-
сти роста алгоритма. Для этой цели можно использовать .Net-классы Stop-
watch
и Process.