В очередном занятии курса “Php Professional“ от Otus мы постараемся получить фундаментальные знания о классических алгоритмах; использовать деревья, графы и алгоритмы их обработки. Как результат — научимся применять оценки сложности относительно их кода; работать с графовыми структурами.

/**/

Цели занятия

• получить фундаментальные знания о классических алгоритмах;

• использовать деревья, графы и алгоритмы их обработки.

Краткое содержание

• алгоритмы и структуры данных;

• детальный асимптотический анализ;

• алгоритмы сортировки, в частности: сортировка Шелла,

• быстрая сортировка и сортировка слиянием;

• стек и очередь на примере реализаций из SPL;

• детальный анализ связанных списков и способы их обхода;

• структуры данных как двоичные и сбалансированные деревья поиска;

• хеш-таблицы и способы борьбы с коллизиями;

• алгоритмы на графах — поиск в ширину и алгоритм Дейкстры.

Результаты

• применять оценки сложности относительно их кода;

• работать с графовыми структурами.

Преподаватель

• Дмитрий Кириллов, тех. диор 1С-Старт

Дата и время

• 5 мая, четверг в 20:00

• Длительность занятия: 90 минут

---

Тезисы из лекции

Пример алгоритмической задачи

Решаем задачку: перевод строки в верхний регистр

Мое решение:

<?php

/**
 * Convert string to upper case
 * @param $str
 * @return string
 */
function to_upper($str)
{
	$delta = 32;

	$ret = "";

	for($i = 0; $i < strlen($str); $i++) {
		$chr = $str[$i];
		$ord = ord($chr);
		if($ord >= 97 && $ord <= 122) {
			$str[$i] = chr($ord - $delta);
		}
	}

	return $str;
}

print "n'" . to_upper("79879 abc xyz 2345") . "'n";

Алгоритмическая сложность

Вычислительная сложность алгоритмов — О(1)

Пример задачи

Пример ввода/вывода

Ограничения

Решение:

function isAlive($n, $m , $k) {
    return $n * $m >= $k;
}

Вычислительная мощность O(N)

Пример задачи — поиск самого легкого арбуза (….)

Решение:

Вычислительная мощность O(N)

Пример задачи

можно решить за разное время, в т.ч. за линейное

“Грязное решение“ за О(n^2)

Домашнее задание: решить эту задачу с хешами за О(N)

---

Хеш-таблицы

Пример задачи

Пример данных

Грязное решение:

Сложность: по скорости O(n * m), по памяти О(1)

Решение с хеш-таблицами

в худшем случае О(N)

Решение с хешами

для нашей задачи, будет максимум 52 элемента в хеш-таблице , т.к. букв 26 + 26 в алфавите, т.е. сложность по памяти О(52), т.е. О(1), по скорости — О (N+M), т.е. О(N)

---

Задача №2: Анаграммы

Является ли одна строка анаграммой другой

Пример ввода:

Решения (варианты):

• (мое): удалять буквы из второй строки, найденные в 1й, в итоге строка №2 д.б. пустой

• отсортировать строки по символам и сравнить

• с хешами (ниже)

Сложность: скорость О(N), память О(26) , т.е. О(1) если только лат буквы в нижнем регистре

Большинство задач на собеседованиях решается на хешах (пример: является ли одна строка частью другой?)

---

Бинарный поиск

Пример задачи

Решения

Моя ремарка (верная): просто найти номер первого неуспешного заказа и далее кол-во заказов после него это ответ; соотв. решение:

Грязное решение

• Сложность: O(N) по скорости, O(1) по памяти

Минус в том, что если сбой был в последнем заказе или не было вообще, прийдется все заказы до него проверить, т.е. О(N)

Эффективное решение: бинарный поиск

Будем искать с середины , и каждый раз делить отрезок с ИД пополам

Сложность по скорости: O(log N): степень двойки

Еще один эффективный вариант решения: через бинарный поиск

Монотонность для бинарного поиска

здесь (1) и (2) монотонные, а (3) для бинарного поиска не подходит, еще примеры:

Предикат бинарного поиска

Задача на бинарный поиск: Дипломы

Нужно рассчитать минимальный размер доски

Решение: Предикат

Решение: Бинарный поиск

---

Итоги

Например, полезно спросить про ограничения, можно ли писать “грязно“ (с @)

---

Мой отзыв о занятии

хотелось бы аналогичное занятие по архитектуре/проектированию систем,

например на highload и т.п., с анализом и обоснованием эффективности решений

в описании занятия — другие темы: “стек и очередь на примере реализаций из SPL;”,

“детальный анализ связанных списков и способы их обхода;“, “алгоритмы на графах — поиск в ширину и алгоритм Дейкстры.“ и т.п.

Дополнительные материалы

• Книга “Грокаем алгоритмы“ (с примерами кода на Питоне)

• Книга “Гид по Computer science”

• Книга “Cracking the coding interview” | Карьера программиста

• Книга Элдер (..)

• Книга Дональд Кнут — “Искусство программирования“

• Книга “Алгоритмы — рук-во по разработке (красная)”

• Книга “Алгоритмы — построение и анализ”

• Книга “Алгоритмические трюки для программистов“