Все, что вам нужно знать о “Big O Notation”, чтобы сломать следующее интервью с кодировкой

1656600972 vse chto vam nuzhno znat o big o notation chtoby

автор Пол Рейл

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

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

Одно дело, с которым я столкнулся, работая над алгоритмами информатики, это то, что называется «Большое О».

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

Что нужно знать

Вот что я употребил, чтобы подготовиться

Чтобы создать сцену для Big O, нам сначала нужно это признать Программное обеспечение, конечно, во многом основано на данных. Огромные горы данных. И использование этих данных – это то, для чего требуется кодировка. Для того чтобы программа могла использовать данные, ей часто нужно начать с сортировки этих данных в логическом порядке. Или это в алфавитном, хронологическом порядке, по размеру, по дате и т.д.

Сортировка происходит постоянно, и в самом деле составляет большую часть всей компьютерной и интернет-активности. Я слышал, как программисты утверждали, что «Быстрая сортировка – это почти то, что управляет всем Интернетом».

Что они имеют в виду? Данные сортировки скважин являются отдельным подразделением по изучению информатики, и существует много четко определенных алгоритмов сортировки. существует Быстрая сортировка, пузырчатая сортировка, сортировка выделением, сортировка слиянием, сортировка в куче и многое другое. Каждый из них имеет разные подходы, чтобы получить одинаковые или подобные результаты.

ujZsW7PRqACIOFutozADQQaeD1dg8KTNwQdl
Источник: https://yourbasic.org/algorithms

Но какой из них самый лучший, если они (почти) дают одинаковый результат?

Лучшее обычно означает, что быстрее всего. Вот тут-то и вступил в игру «Большой О».

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

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

Обозначение большого O оценивает эффективность алгоритмов

Это делается относительно «О” и “п”, (пример: “O(log n)”)где

  • О относится к порядку функции или скорости ее роста, и
  • п длина массива, который нужно отсортировать.

Давайте поработаем на примере. Если алгоритм имеет количество необходимых операций, то формула:

f(n) = 6n^4 — 2n^3 + 5

Как «п” приближается к бесконечности (для очень больших наборов данных) трех присутствующих терминов, 6n^4 это единственное, что имеет значение. Следовательно, меньшие условия, 2n^3 и 5, на самом деле просто пропущены, поскольку они незначительны. То же касается и «6” в 6n^4на самом деле.

Следовательно, эта функция имела бы быстроту роста порядка или рейтинг «большой O» O(n^4) .

Рассматривая многие наиболее часто используемые алгоритмы сортировки, рейтинг O(n log n) в общем это лучшее, чего можно достичь. Алгоритмы, работающие с этим рейтингом, включают быструю сортировку, сортировку в памяти и сортировку слиянием. Быстрая сортировка стандарт и используется по умолчанию почти на всех языках программного обеспечения.

uKzmoTrYJbLljumcgitSieybiHBUBEasqyvd
Источник: http://bigocheatsheet.com/

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

Хотя быстрая сортировка является стандартом, она также конкурирует с сортировкой слияний и сортировкой в ​​куче, которые являются другими алгоритмами сортировки с рейтингом O(n log n). Есть сценарии, когда они используются вместо них.

Наиболее прямым конкурентом Quick Sort является Сортировка кучи. Время работы Heap Sort также равно O(n log n), но среднее время работы Heap Sort обычно считается более медленным, чем быстрая сортировка на месте.

Сортировка слиянием – это a стабильный сортчто означает, что он сохраняет порядок ввода равных элементов в выводе, в отличие от стандартной быстрой сортировки на месте и сортировки в куче.

Пузырь/Вставка/Выбор Сортировать по O(n²)что по количеству операций может занять гораздо больше времени чем перечисленные выше, оценены на O(n log n) при работе с действительно большими данными. Но могут быть сценарии, когда другие работают быстрее в зависимости от данных.

Бывают также случаи, когда что-то очень простое, например, Counting Sort, замечательно, потому что его гораздо быстрее писать и гораздо легче представить и понять.

Иногда вам нужно учитывать не только требования алгоритма ко времени, но и потребности в пространстве данных (или возможно даже больше). Некоторые алгоритмы работают с меньшим объемом памяти.

2srsSpuZG0821IdAizBRdVVivfdyTCpMwNnT
Источник: http://bigocheatsheet.com/

Зачем тебе это знать?

Итак, в конце концов, если вы всегда просто прибегаете к использованию встроенного в язык алгоритма сортировки (который основан на быстрой сортировке), то зачем заботиться об алгоритмах сортировки и «Большое О»? Почему компании спрашивают вас об этом на собеседовании?

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

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

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

Ваш адрес email не будет опубликован.