Сложность и эффективность алгоритмов

Сложность алгоритмов

представлена статья Е.В. Разовой, (ВГГУ, Киров) о сложности алгоритмов.

Эффективные алгоритмы

В тексте задачи C4 ЕГЭ по информатике стоит требование: «Напишите эффективную программу…». Здесь требование эффективности не является синонимом рабочая, правильная. Даже правильно работающая программа может быть неэффективной и как следствие вы можете потерять далеко не лишние баллы. Давайте разбираться...

Вначале теория

Во времена, когда деревья были маленькими, а ваши родители молодыми и беспечными ресурсы компьютера были крайне малы и дорогостоящи. Прежде всего компьютеры обладали малым размером оперативной памяти и относительно медленными процессорами. Поэтому перед программистами стояла задача писать не просто  рабочую программу, а код, который сможет выполниться в этих ограниченных ресурсах. Создавая код вы должны продемонстрировать умения распоряжаться ресурсами компьютера.

Ограничение «по памяти».

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

Размер ячейки зависит от типа переменных и от компилятора. Например, в классическом паскале переменная типа Integer занимает 2 байта памяти, переменная типа real занимает 6 байт памяти и т.д. Если вы задаете массив из десяти элементов типа integer, то в оперативной памяти выделяется  40 байт для его хранения.

Рассчитаем сколько памяти будет использовано в классическом паскале для следующих переменных:

type
student = record
    name:  string[50];
    class_st: string[4];
   mark: integer;
end;
   var i,n:integer;
   avg: real;
   r:student;
   m:array[1..100] of student;

В этом фрагменте описывается тип student, который хранит запись. Ее размер: 50*8 + 4*8 + 2 = 434 байта.

r:student	432
m:array[1..100] of student;	432*100
avg: real;	6
i,n:integer	2*2
итого	43844 байта

Из всего это следует, что вы должны не инициализировать без необходимости лишние переменные, а при инициализации уметь объяснить, в том числе и на апелляции, почему вы использовали их.

Ограничение «по времени»

Ограничение «по времени» связано с тем, что каждая операция занимает процессорное время. Если операций много, это время может быть значительным.

Например, для того чтобы найти наибольший элемент в массиве из N элементов, нужно выполнить N операций сравнения. Сложность такого алгоритма будет (обозначается T) будет линейно зависеть от количества элементов (T~N).

Если нам нужно отсортировать массив из N элементов, то при использовании «метода пузырька» сложность алгоритма уже потребуется N² шагов, (T~N²).

Это означает, что не нужно без необходимости проходить массивы, выполнять операции с ним.

А теперь практика

В демонстрационной версии ЕГЭ по информатике за 2012 год предложена задача:

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

На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.

Пример входных данных:

6
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель

Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.

Пример выходных данных для приведённого выше примера входных данных:

А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1

анализ текста

В этом длинном тексте есть несколько ключевых фраз-подсказок, на которые нужно обратить внимание:

Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет	Это означает, что хранить в массиве результаты каждой команды не нужно.
Длина строки не превосходит 100 символов	100 символов – максимальная длина названия одной задачи

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

Для хранения данных нам потребуется два массива:

Первый массив из одиннадцати элементов будет хранить названия одиннадцати задач.

var qwest: array[1..11] of string[100];

Эта строка выделяет 8*100*11 = 8800 байт.

Также нам потребуется массив из 11 элементов, в котором будут «накапливаться» количество каждой из решаемых задач.

var count: array[1..11] of integer;

Эта строка выделяет 2*11 = 22 байта.

алгоритм программы:

1) узнать количество запросов

2) в цикле:

• извлекать каждую из N строк
• проверять встречается ли эта строка в первом массиве если да – определять номер задачи, если нет – записывать задачу под новым номером
• увеличивать ячейку с количеством решенных задач данного номера на единицу

3) для вывода трех наиболее популярных задач нужно отсортировать второй массив по убыванию, одновременно заменяя элементы в первом массиве, чтобы индексы остались неизменными.

4) вывести первые три строки (предусмотреть, что разные задачи могут иметь одинаковую популярность

текст программы:

program c4_2012;
var
  qwest: array[1..11] of string[100];
  count: array[1..11] of integer;
  i,n,j,n_qwest,curr:integer;
  st:string[100];
  z:boolean;
begin
  write('n=');read(n);
  n_qwest := 0; // количество различных задач, решенных участниками
  for i:=1 to n do
  begin
    read(st);
    // ищем полученную строку в первом массиве
    // причем, ищем не во всем массиве, а лишь в первых n_qwest-строках
    // там где заданы названия задач
    z:=false; // изначально предполагаем, что задача еще ни разу не встречалась
    for j:=1 to n_qwest do
    begin
      if( qwest[j] = st ) then
        begin
        // Если такое название задачи уже встречалось, то увеличиваем элемент массива
        // на единицу, тем самым накапливая количество решаемых задач
        // найдя нужную задачу прерываем цикл, чтобы не выполнять лишних операций
        count[j] := count[j]+1;
        z:=true;
        break;
        end;
    end;
    // если название не найдено, увеличиваем количество уже распознанных названий на единицу
    // записываем название задачи в первый массив
    // увеличиваем соответствующий элемент во втором массиве на единицу.
    if(z=false) then
      begin
        n_qwest := n_qwest + 1;
        qwest[n_qwest] := st;
        count[n_qwest] := count[n_qwest]+1;
      end;
  end;

  // сортируем второй массив "методом пузырька"
  for i:=2 to n_qwest do
    for j:=1 to i do
    if count[i] > count[j] then
      begin
      curr := count[j]; // временное значение перемещаемого элемента массива
      count[j] := count[i];
      count[i] := curr;

      // меняем местами элементы во втором массиве
      // для того, чтобы сохранить целостность индексов
      st := qwest[j];
      qwest[j] := qwest[i];
      qwest[i] := st;
      end;

   if n_qwest >= 3 then j:=3 else j:=n_qwest;
   i := 1;
   while (i <= n_qwest) and (count[i] >= count[j]) do
    begin
    writeln(qwest[i], ' ', count[i]);
    i := i + 1;
  end;
end.

анализ эффективности:

• Для выполнения условия эффективности использовано минимальное значение переменных.
• Некоторые переменные используются многократно, выполняя различные функции, например, переменная st в начале программы – это вводимая строка, а второй части – изменяемая переменная.
• В ходе выполнения программы используется несколько циклов, причем в каждом перебираются только существующие значения, например, при вводе значения поиск идет не по всем элементам, а только по заданным. Сортировка выполняется не среди 11 элементов, а среди количества различных задач.
• В любом случае общее количество операций не превысит N² для ввода значений и заполнения массива и N² для сортировки  массива.

в написании статьи использовались материалы с сайта http://www.titorov.ru