Сложность алгоритмов
представлена статья Е.В. Разовой, (ВГГУ, Киров) о сложности алгоритмов.
Эффективные алгоритмы
В тексте задачи 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 = 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 элементов, то при использовании «метода пузырька» сложность алгоритма уже потребуется N2 шагов, (T~N2).
Это означает, что не нужно без необходимости проходить массивы, выполнять операции с ним.
А теперь практика
В демонстрационной версии ЕГЭ по информатике за 2012 год предложена задача:
В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.
На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.
Пример входных данных:
6
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель
Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.
Пример выходных данных для приведённого выше примера входных данных:
А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1
Простой делитель 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;
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;
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;
// для того, чтобы сохранить целостность индексов
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.
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 элементов, а среди количества различных задач.
- В любом случае общее количество операций не превысит N2 для ввода значений и заполнения массива и N2 для сортировки массива.
в написании статьи использовались материалы с сайта http://www.titorov.ru
Комментариев нет:
Отправить комментарий