алгоритм информация сложность автор годы жизни

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

Введение

Для любого программиста важно знать основы теории алгоритмов, так как именно эта наука изучает общие характеристики алгоритмов и формальные модели их представления. Ещё с уроков информатики нас учат составлять блок-схемы, что, в последствии, помогает при написании более сложных задач, чем в школе. Также не секрет, что практически всегда существует несколько способов решения той или иной задачи: одни предполагают затратить много времени, другие ресурсов, а третьи помогают лишь приближённо найти решение.

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

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

Определения

Основным показателем сложности алгоритма является время, необходимое для решения задачи и объём требуемой памяти.
Также при анализе сложности для класса задач определяется некоторое число, характеризующее некоторый объём данных – размер входа.
Итак, можем сделать вывод, что сложность алгоритма – функция размера входа.
Сложность алгоритма может быть различной при одном и том же размере входа, но различных входных данных.

Существуют понятия сложности в худшем, среднем или лучшем случае. Обычно, оценивают сложность в худшем случае.

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

Порядок роста сложности алгоритмов

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

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

Виды асимптотических оценок

O – оценка для худшего случая

Рассмотрим сложность f(n) > 0, функцию того же порядка g(n) > 0, размер входа n > 0.
Если f(n) = O(g(n)) и существуют константы c > 0, n₀ > 0, то
0 n₀.

Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).

Данное выражение определяет класс функций, которые растут не быстрее, чем g(n) с точностью до константного множителя.

Примеры асимптотических функций

Ω – оценка для лучшего случая

Критерии оценки сложности алгоритмов

Равномерный весовой критерий (РВК) предполагает, что каждый шаг алгоритма выполняется за одну единицу времени, а ячейка памяти за одну единицу объёма (с точностью до константы).
Логарифмический весовой критерий (ЛВК) учитывает размер операнда, который обрабатывается той или иной операцией и значения, хранимого в ячейке памяти.

Временная сложность при ЛВК определяется значением l(O_p), где O_p – величина операнда.
Ёмкостная сложность при ЛВК определяется значением l(M), где M – величина ячейки памяти.

Пример оценки сложности при вычислении факториала

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

Временная сложность при равномерном весовом критерии

Достаточно просто определить, что размер входа данной задачи – n.
Количество шагов – (n — 1).

Таким образом, временная сложность при РВК равна O(n).

Временная сложность при логарифмическом весовом критерии

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

Итак, в данной задаче выделяется три операции:

Источник

Тест на соответствие «История информатики»

Счет с помощью палочек

Может ли машина мыслить

Кибернетика. Мышление. Жизнь

Алгоритм, информация, сложность

Словарь школьной информатики

Науки об искусственном

Кибернетика, или Управление и связь в живом и машине

Счет с помощью палочек

Об искусстве комбинаторики

Может ли машина мыслить

Теория самоопределяющихся автоматов

Теория релейно-контактных схем

Кибернетика. Мышление. Жизнь

Основы безбумажной информатики

Алгоритм, информация, сложность

Словарь школьной информатики

Математическая теория передачи информации

Науки об искусственном

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

Курс профессиональной переподготовки

Информатика: теория и методика преподавания в образовательной организации

Курс профессиональной переподготовки

Математика и информатика: теория и методика преподавания в образовательной организации

Онлайн-конференция для учителей, репетиторов и родителей

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

Номер материала: ДВ-220567

Международная дистанционная олимпиада Осень 2021

Не нашли то что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

В Москве увеличат зарплату педагогам

Время чтения: 1 минута

Рособрнадзор оставил за регионами решение о дополнительных школьных каникулах

Время чтения: 1 минута

В России пройдет эксперимент с электронными аттестатами

Время чтения: 1 минута

Рособрнадзор проведет исследование качества образования в школах

Время чтения: 2 минуты

В Москве подписан Меморандум о развитии и поддержке классного руководства

Время чтения: 1 минута

В Югре в 2022 году откроют школьный центр генетики

Время чтения: 2 минуты

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Источник

Как я изучал структуры данных и алгоритмы для собеседования в FAANG

Продолжая тему устройства в FAANG, которую уже мы поднимали в нашем блоге, и специально к старту нового потока нашего курса по алгоритмам сегодня делюсь описанием пути Эско Обонга, старшего инженера-программиста Uber.

Эта история началась в 2015 году, когда стартап, к которому я присоединился как «сотрудник-основатель», закрылся через шесть месяцев после первого раунда инвестиций, и я искал новую работу. Первое моё собеседование было с Codecademy, где на этапе телефонного разговора меня заверили: «Не волнуйтесь, мы не задаём сумасшедших вопросов об алгоритмах или что-то в этом роде». И я им поверил…

Во время собеседования было два раунда вопросов об алгоритмах, которые в ретроспективе были чрезвычайно простыми. Я помню, как один из собеседников спросил, как пройти из точки A в точку И по сетке. Я понятия не имел, как это сделать, поэтому наделал какой-то ерунды. Написал на доске бесконечный цикл while:

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

Фиаско в Codecademy открыло мне глаза на пробелы в моих знаниях. Два с половиной месяца спустя я прошёл телефонный скрининг в Google, Uber, Shutterstock и Rent the Runway. Были собеседования на месте в Shutterstock, Rent the Runway и Uber – и я прошёл их все. Google перенёс моё собеседование на две недели вперёд в последнюю минуту. К тому времени у меня уже было три предложения, и я был в восторге от Uber, поэтому я нажал на спуск – присоединился к Uber.

Я прошёл с нуля до профессионального уровня всего за несколько месяцев, но не делал ничего особенного, только последовательно учился. Вот почему я твёрдо верю, что любой инженер может справиться с этими вопросами об алгоритмах и структурах данных и попасть в F.A.A.N.G. или на аналогичные должности с высокой зарплатой. Сначала казалось, что мне не хватает квалификации, потому что для собеседования приходилось усердно учиться. В 2019 году, после того как я управлял собственной консалтинговой фирмой и стартапом в течение почти двух лет, я решил вернуться к постоянной работе и оказался в том же положении, что и в 2015 году.

На этот раз у меня было больше друзей в Uber и других ведущих компаниях, таких как Google и Facebook, которые помогли мне понять суть дела. Так же усердно пришлось учиться им всем. Даже тем, кто не бросил колледж, как и я.

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

Я отказался от представления о мифическом инженере, который может по щелчку пальцев пройти техническое собеседование, и начал понимать реальность ситуации: технические собеседования похожи на SAT [прим. перев. — «Scholastic Aptitude Test» и «Scholastic Assessment Test», дословно «Академический оценочный тест») — стандартизованный тест для приема в высшие учебные заведения в США] в школе. Не важно, что вы потратили четыре года, чтобы изучить всё, чему учатся в старшей школе. Если вы хотите сдать экзамен, вам всё равно нужно подготовиться. Как и в случае с SAT, все ваши прошлые работы и оценки не влияют на результат. Ваш успех полностью зависит от того, насколько хорошо вы сдали тест.

Как только я понял истину, что учиться нужно всем, то обрёл достаточно мотивации, чтобы трудиться усердно. Я понял, что труд обучения – это именно то, чем заняты мои конкуренты. Это послужило толчком, чтобы сформировать процесс обучения, который помог мне пройти все технические тесты и собеседования в 2019 году. Я бросил колледж и прошёл технические тесты Stripe, Coinbase и Triplebyte. Прошёл скрины и собеседования на местах в Google, Amazon, Uber (снова), Reddit, Squarespace и Braze. Я не ждал, что пройду всё идеально, но считаю, мне помогло то, что я сосредоточился на основных принципах.

Google отправляет вам сувениры, когда вы проходите собеседование.

Переход не был плавным. Когда я только начал готовиться к собеседованию, мне потребовалось более 2 часов, чтобы почти решить задачу, которую теперь можно было бы назвать «leetcode easy», а в то время это казалось невозможным! Я искренне верил, что просто недостаточно умён от природы и мне придётся учиться ещё усерднее, чтобы достичь уровня, на котором смогу решить задачу с той же скоростью, что и инженер Google. Я понял одно: мне нужно практиковаться.

Чего я не понимал, так это того, что такого уровня сложности и разочарования вначале следует ожидать всем начинающим, включая инженеров Google.

Я всё тот же человек. Единственная разница между мной тогда и сейчас – практика, практика, практика. У людей часто возникает вопрос: «Как мне учиться?» Трудно понять, с чего начать, что делать дальше, добиваетесь ли вы прогресса, и ещё труднее оставаться на верном пути. Чтобы решить многие из этих вопросов, когда я учился, я создал доску Trello со всеми темами, которые хотел охватить. Доска помогла мне сосредоточиться на самых важных темах и управлять временем, чтобы прогресс был стабильным.

Я написал пост о доске Trello в LinkedIn, этот пост стал вирусным. Менеджер Trello связался со мной по поводу создания для него официального шаблона Trello, который теперь находится здесь: Interview Study Tracker.

Чтобы учиться, в трекере есть шаблон. Он требует определения списка тем и двух или более ресурсов, которые могут научить чему-то по теме. Затем нужно задать себе 2–3 практических задачи, чтобы укрепить понимание. Задачи могут быть из любого источника, главное – это сам контент. Я нашёл большую часть своего контента с помощью простого поиска в Google, темы были ключевыми словами.

Изучайте одно и то же с разных точек зрения, это поможет лучше понять тему. Например, о двоичных деревьях поиска я бы прочитал статью на geeksforgeeks.org, а также главы о них в Cracking the Coding Interview. Затем я задал бы себе 2–3 практических задачи, или достаточно задач, чтобы почувствовать себя комфортно, прежде чем двигаться дальше.

Мой экземпляр «Cracking The Coding Interview 6th Edition», подписанный Гэйл Лакман Макдауэлл

Список тем для изучения

Ниже привожу список почти всех структур данных и алгоритмов, с которыми вы можете столкнуться во время технического собеседования, а также очень краткое описание и некоторые ресурсы – с их помощью можно приступить к составлению плана обучения. Цель списка – дать вам отправную точку, чтобы вы разработали план, а не подробно объяснять, что представляет собой каждая тема. Часть вашего плана – найти ресурсы, чтобы узнать больше о каждой теме с разных точек зрения.

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

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

Базовые структуры данных

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

Продвинутые структуры данных

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

Кучи, также известные как очереди приоритетов, – это тип дерева, которое ведёт себя как очередь. Бинарное дерево поиска (BST) – это дерево, которое ускоряет поиск узлов. AVL и красно-чёрные деревья – два популярных специфических типа сбалансированных BST. Кэш LRU – это кэш с эффективным использованием памяти, он создаётся объединением Hashmap [прм. перев. — хэшмэпы — специфический тип хэш-таблицы] со связным списком. Trie – это ещё один тип дерева, который ускоряет поиск по подстроке. Непересекающиеся множества – это особый тип множества, которые разделяют элементы на неперекрывающиеся подмножества, полезные для алгоритма поиска объединения. Skip List – это оптимизированный LinkedList, он сокращает время поиска определённых узлов.

Основные алгоритмы поиска и обхода

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

Продвинутые алгоритмы поиска и обхода

В этой области проводится много исследований, но для целей технического собеседования наиболее продвинутые алгоритмы поиска, с которыми вы, вероятно, столкнётесь:

Алгоритмы сортировки

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

Важные темы

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

Распространённые шаблоны

Эти шаблоны можно использовать, чтобы разобраться со многими алгоритмами:

Математические задачи

Другие общие задачи

Практика

Самостоятельная практика

Обучение ничего не значит без практики. Каждый раз, когда вы изучаете новую тему из своего учебного плана, вы должны использовать знания из неё. Это поможет вам лучше запомнить тему, даст понимание глубже. Задайте самому себе несколько практических задач по каждой завершённой теме. На таких сайтах, как leetcode.com, можно найти практические вопросы, воспользовавшись тегами «trees» или «graphs».

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

Во время собеседования вы должны решить задачу за 15–45 минут в зависимости от сложности. Вначале вам, скорее всего, понадобится несколько часов, чтобы решить первую задачу. В первые несколько недель это время должно начать сокращаться. Через месяц или два месяца постоянной практики (а не просто времени) вы должны научиться решать приличное количество задач вовремя. Иногда ваша задача – реализовать единственную структуру данных, например LRU-кэш или Trie. В других случаях нужно выполнить только одну операции над структурой данных, например удаление элемента в двоичном дереве.

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

Практика с ассистентом (имитация собеседования)

Одной практики по темам и вопросам недостаточно. Во время собеседования вы будете общаться с реальным человеком, который оценивает ваши навыки прямо здесь и сейчас. Это ситуация более напряжённая, чем когда вы учитесь дома. Чтобы обойти неловкость и беспокойство настоящего собеседования, заранее проведите много имитационных собеседований. Это поможет вам чувствовать себя комфортно и сосредоточиться на вопросе собеседования, а не отвлекаться на что-то нетехническое. Вы можете попросить друга помочь вам или найти в Интернете сервис, который подберёт вам человека, чтобы пройти имитационное собеседование.

Когда вы будете готовы?

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

Очень важно отслеживать прогресс и получать обратную связь, чтобы знать, когда вы действительно готовы выступить на настоящем собеседовании, не полагаясь только на эмоции. Следите за временем выполнения, когда вы задаёте себе практические задачи, и старайтесь не более 40 минут на ответы на большинство вопросов среднего уровня и 1 час на ответы на сложные вопросы на leetcode.com или hackerrank.com.

Большая часть кода на собеседовании оценивается на небольшом наборе крайних случаев, и небольшие ошибки всегда пропускаются или считаются несущественными. Люди не ждут совершенства, но они должны увидеть достаточно «сигналов», чтобы убедиться в том, что вы подходите. Пройдите как минимум три фиктивных собеседования, прежде чем идти на настоящее. Двигайтесь вперёд только в момент, когда сможете стабильно хорошо работать во время тренировки.

Крупные технологические компании нанимают сотрудников постоянно, поэтому они могут очень гибко планировать или переносить дату собеседования. Я перенёс свои собеседования в Google и Uber на 2 и 1 месяц соответственно, потому что не был готов. В прошлом я делал ещё более длительные переносы. Чтобы перенести собеседование, не нужно никаких особых оправданий. Я просто говорил: «Мне нужно больше времени на подготовку». Эти компании тратят много денег на ваше собеседование. 5–6 штатным сотрудникам платят за собеседование в течение 4–5 часов с последующей оценкой результатов. Учитывайте зарплаты рекрутеров, они нашли время, чтобы найти вас и обработать лишь небольшой процент заявок от людей, которые прошли через них, и это как минимум несколько тысяч долларов за собеседование. Компании хотят, чтобы люди приходили подготовленными. Они будут ждать, а не тратить время, деньги (и не только их) на отказ от инженера, который мог бы подойти, если бы они просто подождали ещё месяц или два. Так что отложите мероприятие, если не готовы. Никогда не идите на собеседование, не будучи готовым!

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

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

Книги

Сайты

Буткэмпы

Практика

Самостоятельная работа

Надеюсь, данная статья была вам полезна. Главная мысль, которую я хотел донести — чтобы устроиться на работу в ведущую технологическую компанию, вам не нужно специальное высшее образование (хотя оно будет полезно), гены счастливчика или длинный послужной список. Единственное, что вам нужно, – это уделять время последовательному обучению и практике и не забывать про промокод HABR, который добавит дополнительно 10% к скидке на баннере.

Источник