Примеры проверки времени работы алгоритмов с разной асимптотической оценкой

Complexity.cs

using System;

namespace CSComplexity
{
    class Program
    {
        //Тест вычислений с константной асимптотической оценкой времени выполнения
        public static void O1(int length)
        {
            int[] array = new int[length];
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            int l = array.Length;
            sw.Stop();
            Console.WriteLine("n="+length+"; Constant time:\t"+((double)sw.ElapsedTicks/ System.Diagnostics.Stopwatch.Frequency)*1000);
        }

        //Тест вычислений с логарифмической асимптотической оценкой времени выполнения
        public static void Ologn(int length)
        {
            int[] array = new int[length];
            var r = new Random();
            for (var i = 0; i < length; i++)
                array[i] = r.Next();
            Array.Sort(array);
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            int l = Array.BinarySearch(array, r.Next());
            Console.WriteLine("n="+length+"; Logarithmic time:\t"+ ((double)sw.ElapsedTicks / System.Diagnostics.Stopwatch.Frequency) * 1000);
        }

        //Тест вычислений с линейной асимптотической оценкой времени выполнения
        public static void On(int length)
        {
            int[] array = new int[length];
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            int s = 0;
            foreach (var x in array)
                s += x;
            sw.Stop();
            Console.WriteLine("n="+length+"; Linear time:\t"+ ((double)sw.ElapsedTicks / System.Diagnostics.Stopwatch.Frequency) * 1000);
        }

        //Тест вычислений с асимптотической оценкой времени выполнения nlogn
        public static void Onlogn(int length)
        {
            int[] array = new int[length];
            var r = new Random();
            for (var i = 0; i < length; i++)
                array[i] = r.Next();
            Array.Sort(array);
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            int s = 0;
            sw.Start();
            for(int i=0; i<length; i++)
                s+=Array.BinarySearch(array, r.Next());
            Console.WriteLine("n=" + length + "; Linearithmic time:\t" + ((double)sw.ElapsedTicks / System.Diagnostics.Stopwatch.Frequency) * 1000);
        }

        //Тест вычислений с квадратической асимптотической оценкой времени выполнения
        public static void On2(int length)
        {
            int[] array = new int[length];
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            int s = 0;
            for(int i=0; i<length; i++)
                for (int j = 0; j < length; j++)
                    s += array[i];
            sw.Stop();
            Console.WriteLine("n=" + length + "; Quadratic time:\t" + ((double)sw.ElapsedTicks / System.Diagnostics.Stopwatch.Frequency) * 1000);
        }


        static void Main(string[] args)
        {
            O1(10000000);
            Ologn(10000000);
            On(10000000);
            Onlogn(10000000);
            On2(100000);
        }
    }
}