В очередном занятии курса “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)

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


Хеш-таблицы

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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


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

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

Решения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Итоги

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tags

Нет комментариев

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.