Основы алгоритмов и структур данных

Введение в алгоритмы

Алгоритм представляет собой последовательность шагов, которая призвана решить определенную задачу. Иными словами алгоритм - это способ решения этой задачи. В этом качестве алгоритм применяется для обозначения метода решения любых, в том числе и повседневных задач. Но в данном случае речь будет идти об алгоритмах компьютерных вычислений.

Сам термин "алгоритм" произошел от имени персидского математика Аль-Хорезми, труды которого сыграли важную роль на становление математики как науки.

Алгоритм может иметь входные данные, над которыми производятся вычисления, а также может иметь выходной результат - одно значение или набор значений. По сути задача алгоритма состоит в преобразовании входных значений в выходные.

Важным критерием алгоритма выступает эффективность. Алгоритм может прекрасно решать поставленную задачу, но при этом быть не эффективным. Как правило, под эффективностью алгоритма подразумевается время, за которое должен выполняться данный алгоритм.

Общее время выполнения программы зависит от двух факторов:

• времени выполнения каждого оператора

• частоты выполнения каждого оператора

Время выполнение каждого оператора зависит от среды выполнения, операционной системы и других системных характеристик.

В зависимости от эффективности существует много типов алгоритмов, среди которых можно выделить следующие типы алгоритмов (перечислены в порядке уменьшения эффективности):

• Константный (1)

  Приложение выполняет фиксированное количество операций, которые, как правило, требуют постоянного времени.

  Примером может служить следующий набор операций:

  int x = 10;
  if(x > 0)
  {	
  	x--;
  }
  else
  {
  	x++;
  }
  

• Логарифмический (logN)

  Выполняется медленнее, чем программы с постоянным временем. Примером подобного алгоритма может служить алгоритм бинарного поиска.

  public static int Rank(int key, int[] numbers)
  {
      int low = 0;
      int high = numbers.Length - 1;
      while (low <= high)
      {
          // находим середину
          int mid = low + (high - low) / 2;
          // если ключ поиска меньше значения в середине
          // то верхней границей будет элемент до середины
          if (key < numbers[mid]) high = mid - 1;
          else if (key > numbers[mid]) low = mid + 1;
          else return mid;
      }
      return -1;
  }
  

  К примеру, если у нас в массиве numbers 8 элементов, то чтобы найти нужный нам элемент, нам надо последовательно делить количество элементов на 2. То есть для поиска нужного элемента нам надо 3 выполнить цикл while. И данный результат, как раз описывается логарифмической функцией: log₂8 = 3;

  Рост времени выполнения при росте N будет увеличиваться на некоторую постоянную величину.

• Линейный (N)

  Как правило, встречается там, где метод основан на цикле. К примеру, функция факториала:

  private static int Factorial(int n)
  {
      int result = 1;
      for(int i=1; i<=n; i++)
      {
          result *= i;
      }
      return result;
  }
  

  Здесь выполнение метода зависит от n. Какое значение для n будет передано в метод, столько раз и будет выполняться цикл. То есть рост трудоемкости алгоритма для данного метода пропорционален значению n, поэтому его и называют линейный.

• Линейно-логарифмический (NlogN)

  Примером подобного алгоритма может служить сортировка слиянием (merge sort)

• Квадратичный (N²)

  Как правило, методы, которые соответствуют данному алгоритму, содержит два цикл - внешний и вложенный, которые выполняются для всех значений вплоть до N. В качестве примера можно привести программу сортировки пузырьком (bubble sort) массива из N элементов, в которой в худшем случае нам надо совершить обход N*N элементов с помощью двух циклов:

  private static void BubbleSort(int[] nums)
  {
      int temp;
      for (int i = 0; i < nums.Length - 1; i++)
  	{
  		for (int j = i + 1; j < nums.Length; j++)
  		{
  			if (nums[i] > nums[j])
  			{
  				temp = nums[i];
  				nums[i] = nums[j];
  				nums[j] = temp;
  			}
  		}
  	}
  }
  

• Кубический (N³)

  В программах, которые соответствуют этому алгоритму, используются три цикла, например:

  char[] chars = new char[] { 'A', 'B', 'C' };
  for(int i=0; i<chars.Length; i++)
  {
      for(int j=0; j<chars.Length;j++)
      {
          for(int k=0; k<chars.Length;k++)
          {
              Console.WriteLine($"{chars[i]}{chars[j]}{chars[k]}");
          }
      }
  }
  

Здесь рассмотрены только некоторые виды сложностей алгоритмов, которых на самом деле гораздо больше. Графически их можно представить следующим образом:

В то же время надо сделать несколько замечаний. В данном случае дана идеальная модель сложности алгоритма. Но в первую очередь надо отметить, что подразумевается, что воздействие окружения (операционной системы) на выполнение программы ничтожно мало. Хотя в реальности, естественно, окружение может привносить свой вклад в конечную производительность приложения.

Кроме того, в большинстве случаев сложность алгоритма зависит от наличия циклов. Метод без цикла с простыми выражениями имеет сложность O(1), тогда как метод с одним циклом - уже О(N), что, теоретически, хуже, чем O(1). Однако в реальности наличие простых операторов даже без цикла может меньшую производительность. Многое тут зависит опять же от конкретной логики программы.

И еще один аспект, который может повлиять на выполнение программы - это кэширование. Использование кэширования позволяет повторно выполнить операцию быстрее. Тем самым время выполнения одной и той же операции может быть непостоянным.