Хочешь уверенно проходить IT-интервью?
Мы понимаем, как сложно подготовиться: стресс, алгоритмы, вопросы, от которых голова идёт кругом. Но с AI тренажёром всё гораздо проще.
💡 Почему Т1 тренажёр — это мастхэв?
- Получишь настоящую обратную связь: где затык, что подтянуть и как стать лучше
- Научишься не только решать задачи, но и объяснять своё решение так, чтобы интервьюер сказал: "Вау!".
- Освоишь все этапы собеседования, от вопросов по алгоритмам до диалога о твоих целях.
Зачем листать миллион туториалов? Просто зайди в Т1 тренажёр, потренируйся и уверенно удиви интервьюеров. Мы не обещаем лёгкой прогулки, но обещаем, что будешь готов!
Реклама. ООО «Смарт Гико», ИНН 7743264341. Erid 2VtzqwP8vqy
Асимптотическая сложность алгоритмов встречается повсеместно. Доступно рассказываем, что это такое, где и как используется.
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
Асимптотическая сложность алгоритмов представляет собой время и память, которые понадобятся вашей программе в процессе работы. Одно дело – знать, что существуют линейные или логарифмические алгоритмы, но совсем другое – понимать, что же за всем этим стоит.
С помощью Big O Notation можно математически описать то, как поведет себя программа в условиях наихудшего сценария при большом количестве входных данных. Например, если вы используете сортировку пузырьком, чтобы отсортировать элементы в целочисленном массиве по возрастанию, то худшим сценарием в этом случае будет отсортированный в убывающем порядке массив. При таком раскладе вашему алгоритму понадобится наибольшее количество операций и памяти.
Разобравшись в принципе работы Big O Notation, вы сможете решить проблему оптимизации ваших программ и добиться максимально эффективного кода.
Сложности О(1) и O(n) самые простые для понимания.
О(1) означает, что данной операции требуется константное время. Например, за константное время выполняется поиск элемента в хэш-таблице, так как вы напрямую запрашиваете какой-то элемент, не делая никаких сравнений. То же самое относится к вызову i-того элемента в массиве. Такие операции не зависят от количества входных данных.
В случае, если у вас не очень удачная хэш-функция, которая привела к большому количеству коллизий, поиск элемента может занять О(n), где n – это количество объектов в хэш-таблице. В худшем случае Вам понадобится сделать n сравнении, а именно пройтись по всем элементам структуры. Очевидно, что скорость линейных алгоритмов, то есть алгоритмов, работающих в О(n), зависит от количества входных данных. В случае с линейными алгоритмами в худшем случае вам придется провести какую-то операцию с каждый элементом.
Бинарный поиск является одним из классических примеров алгоритмов, работающих за O(log_2(n)). Каждая операция уменьшает количество входных данных вдвое.
Например, если у вас есть отсортированный массив, насчитывающий 8 элементов, в худшем случае вам понадобится сделать Log_2(8)=3 сравнений, чтобы найти нужный элемент.
Рассмотрим отсортированный одномерный массив с 16 элементами:
Допустим, нам нужно найти число 13.
Мы выбираем медиану массива и сравниваем элемент под индексом 7 с числом 13.
Так как наш массив отсортирован, а 16 больше, чем 13, мы можем не рассматривать элементы, которые находятся под индексом 7 и выше. Так мы избавились от половины массива.
Дальше снова выбираем медиану в оставшейся половине массива.
Сравниваем и получаем, что 8 меньше, чем 13. Уменьшаем массив вдвое, выбираем элемент посередине и делаем еще одно сравнение. Повторяем процесс, пока не останется один элемент в массиве. Последнее сравнение возвращает нужный элемент. Лучшее развитие событий – если первая выбранная медиана и есть ваше число. Но в худшем случае вы совершите log_2(n) сравнений.
Сложность O(n*log n) можно представить в виде комбинации O(log n) и O(n). Такую сложность можно получить, если в вашей программе есть один for-цикл, который содержит еще один for-цикл. То есть нестинг циклов, один из которых работает за O(log n), а другой – за O(n).
for(int i = 0; i < n; i++) //выполняется n раз
for(int j = 1; j < n; j = j * 2) // выполняется blogs раз
print “hello"; //константное время
Сложность O(n^2) встречается довольно часто в алгоритмах сортировки. Ее легко можно получить, если в программе имплементировать нестинг двух for-циклов, работающих в O(n).
Например:
for(int i = 0; i < n; i++) // выполняется n раз
for(int j = 0; j < n; j++) //выполняется n раз
print “hello”; // константно
То же самое произойдет, если вам надо будет пройтись по элементам двумерного массива.
Алгоритмы, которые можно описать с помощью нотации O(n^2 + n + 3) или O(n^2-100000), или даже O(n^2 + 100000000) все равно считаются квадратными. При большом количестве входных данных только наибольшая степень n является важной. Константы и коэффициенты обычно не берут во внимание. То же самое касается линейных и логарифмических функций. O( n +1000) и O(1000*n) все равно будут работать в O(n).
Использование алгоритмов, которые работают в O(n^2) и выше (например, экспоненциальная функция 2^n), является плохой практикой. Следует избегать подобных алгоритмов, если хотите, чтобы ваша программа работала за приемлемое время и занимала оптимальное количество памяти.
Комментарии