1. Оценка сложности алгоритмов.Сложность базовых операций с одномерными массивами.

1. Оценка сложности алгоритмов.

Что мы хотим от алгоритма?

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

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

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

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

Пример:

Допустим, некоторому алгоритму нужно выполнить 4n^3+ 7nусловных операций, чтобы обработать nэлементов входных данных. При увеличении nна итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n. Тогда говорят, что временная сложность этого алгоритма равна О(n^3), то есть зависит от размера входных данных кубически.

Вывод:

При общей оценке сложности алгоритма константы (конкретные числа) и слагаемые, степень которых меньше максимальной, можно отбрасывать.

Время выполнения алгоритма с определённой сложностью в зависимости от размера входных данных при скорости 10^6 операций в секунду:

2. Сложность базовых операций с одномерными массивами.

O(1) - время работы алгоритма вообще не зависит от размера входных данных.

O(n) — линейная сложность. Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем nэлементам массива, чтобы понять, какой из них максимальный.

Базовые операции с элементами одномерного массива:

Обращение к i-му элементу – О(1)
Замена i-го элемента – О(1)
Поиск элемента по значению – О(n)
Вставка и удаление элементов – О(n)

Совет:

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

Задачи и примеры их решения

1. Поиск трех максимальных элементов на основе поиска максимума.

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

Идеи решения: можно три раза найти максимальный элемент в массиве (не забывая каждый раз его «удалять»).

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

Фрагмент кода:

Player max1 = new Player("", -1);
Player max2 = new Player("", -1);
Player max3 = new Player("", -1);

for (int i = 0; i < _players.Length; i++)
{
	if (_players[i].Score > max3.Score)
	{
		max3 = _players[i];
	}

	if (_players[i].Score > max2.Score)
	{
		Player temp = max3;
		max3 = max2;
		max2 = temp;
	}

	if (_players[i].Score > max1.Score)
	{
		Player temp = max2;
		max2 = max1;
		max1 = temp;
	}
}

Console.WriteLine("1 место: " + max1.Nickname + ", набравший " + max1.Score + " баллов!");
Console.WriteLine("2 место: " + max2.Nickname + ", набравший " + max2.Score + " баллов!");
Console.WriteLine("3 место: " + max3.Nickname + ", набравший " + max3.Score + " баллов!");

Вопрос: А что будет, если несколько игроков, претендующие на тройку лидеров наберут одинаковое количество баллов?

Вопросы к размышлению:

Как изменится алгоритм, если наградить надо 10 игроков? 100 игроков? Всех игроков в соответствии с рейтингом?

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

2. Перемещение элемента в отсортированном массиве.

Условие: В игре постоянно поддерживается в отсортированном порядке рейтинг игроков (набранные баллы – scoreи ники). Игрок под указанным номером заработал еще S баллов. Необходимо «поднять» его в рейтинге в соответствии с его суммой score.

Фрагмент кода:

Console.Write("Введите номер игрока: ");
int number = Convert.ToInt32(Console.ReadLine()) - 1;
Console.Write("Сколько он заработал баллов?: ");
int profit = Convert.ToInt32(Console.ReadLine());

_players[number].Score = _players[number].Score + profit;


for (int i = number; i > 0; i--)
{
	if (_players[i - 1].Score < _players[i].Score)
	{
		Player temp = _players[i];
		_players[i] = _players[i - 1];
		_players[i - 1] = temp;
	}
}

for (int i = 0; i < _players.Length; i++)
{
	Console.WriteLine(i + 1 + " место: " + _players[i].Nickname + ", набравший " + _players[i].Score + " баллов!");
}

Вопрос: Оцените сложность этого алгоритма.

Вопросы к размышлению:

Как изменится алгоритм, если необходимо предусмотреть возможность снятия баллов с игрока?

3. Подсчет в строке

Условие: Создатели игры решили определить, какую клавишу чаще нажимают игроки во время игры. Для этого они присвоили каждой используемой клавише код в виде маленькой английской буквы и записали log игры – последовательность нажатых клавиш. Необходимо в строке символов, состоящей из маленьких английских букв, определить, какой символ встречается чаще других и сколько раз (если таких символов несколько, вывести тот, который в строке впервые встретился раньше).

Фрагмент кода:

Console.Write("Введите строку: ");
string log = Console.ReadLine();
int[] quantity = new int[26];
for (int i = 0; i < log.Length; i++)
{
	quantity[(int) log[i] - (int) 'a'] += 1;
}

//Массив для проверки
for (int i = 0; i < quantity.Length; i++)
{
	Console.Write(quantity[i] + " ");
}

Console.WriteLine();

//Поиск максимума и вывод ответа
int maximum = quantity[0];
int number = 0;
for (int i = 1; i < quantity.Length; i++)
{
	if (quantity[i] > maximum)
	{
		maximum = quantity[i];
		number = i;
	}
}

Console.WriteLine("Чаще всего нажимается клавиша, обозначенная буквой " + (char) ((int) 'a' + number));

Вопрос: Оцените сложность этого алгоритма как можно точнее.

Вопросы к размышлению:

Как изменится алгоритм и его сложность, если в строку log могут быть записаны «любые» символы (в том числе русские буквы, знаки препинания, цифры, маленькие и большие буквы)?

Итоги занятия:

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

А на следующем занятии мы заставим компьютер основательно поработать и даже практически «зависнуть» на вычислениях.