И почему вам должно быть до этого дело?
Проще говоря…
Big O Notation - это упрощенный анализ эффективности алгоритмов. Скорость его обработки зависит от того, насколько эффективно написан ваш код.
Простые времена
В 2009 году в Южной Африке была компания, у которой было два офиса, примерно в 50 милях друг от друга, и очень низкая скорость интернета. Компания организовала тест, в котором они будут передавать данные из одного офиса в другой через Интернет через своего очень медленного интернет-провайдера и одновременно через USB-накопитель, привязанный к почтовому голубю. Излишне говорить, что почтовый голубь победил (иначе эту историю не стоило бы рассказывать). Но насколько справедлив этот тест? И действительно, как такое вообще возможно?
В конце концов, это был своего рода глупый тест. Передача данных через Интернет занимает все больше и больше времени, в зависимости от того, сколько данных вы пытаетесь передать.
Допустим, на отправку 1 ГБ данных ушло 30 минут. Можно с уверенностью сказать, что отправка вдвое большего объема данных займет примерно в два раза больше времени, отправка втрое большего объема данных займет в три раза больше времени и так далее и тому подобное. С другой стороны, если голубь летит куда-нибудь с привязанным к его ноге 1 ГБ данных на USB-накопителе, ничем не отличается от того, что этот голубь где-то летает с 5 ГБ данных на USB-накопителе, привязанном к его ноге. Голубю просто нужно пролететь 50 миль, и он не осознает разницу в объеме передаваемых данных.
Другими словами, Интернет в этом примере отправляет данные в линейное время. Чем больше данных вы отправляете, тем больше времени требуется на их отправку. В Big O мы будем называть это O (N), где N = количество данных. Голубь в примере отправляет его в постоянное время в зависимости от размера данных. Это не займет больше времени в зависимости от объема данных. Это записывается как O (1).
Big O - это, по сути, уравнение, которое описывает, как время выполнения масштабируется по отношению к некоторым входным переменным.
Смотрим на эффективность алгоритмов
Рассматривая эффективность алгоритмов, вы можете изучить наихудший сценарий, лучший сценарий или средний сценарий. Возьмем следующий пример чрезвычайно низкого уровня различий в этих типах сценариев:
Когда мы вводим searchName для «Annarose», нам нужно только посмотреть на один элемент в этом массиве, прежде чем мы вернемся.
Коротко и мило - в лучшем случае.
Что, если бы мы использовали поисковый запрос «Люси»?
Здесь мы видим, что до нашего возврата потребовалось больше времени, потому что первые два элемента в массиве не удовлетворяли нашим условиям, установленным в операторе if. Не страшно, но могло быть и лучше - средний сценарий.
Что, если бы мы хотели найти «Чарли»?
Здесь нам пришлось просмотреть каждое имя в массиве имен, прежде чем найти то, что мы искали. Больше итераций означает больше работы для компьютера и больше времени, потраченного на эту работу - худший сценарий.
В этом примере, конечно, каждая функция почти не занимает времени, но на микроскопическом уровне вы можете увидеть, как bestCase самый быстрый, а худший - самый медленный.
С Big O нас больше интересует наихудший сценарий, потому что он действительно покажет нам, насколько эффективна наша работа, даже в худшем случае. Это не означает, что два других не важны, просто они не являются главной проблемой.
Big O Time Сложность
Я упоминал ранее концепции линейной и постоянной сложности времени. Линейный, я описал как O (N), и постоянный, O (1). Давайте углубимся в них немного подробнее и рассмотрим пару других распространенных порядков роста (O в Big O означает порядок).
O (1) - Постоянная
O (1) описывает алгоритм, который всегда будет выполняться в одно и то же время независимо от размера входного набора данных.
Примером этого может быть массив и простая функция, которая захватывает второй элемент этого массива. Это не требует итераций, и не имеет значения, насколько велик набор данных. Массив [1] - это массив [1].
O (N) - линейный
O (N) описывает алгоритм, производительность которого будет расти линейно и прямо пропорционально размеру входного набора данных. Как я упоминал ранее, Big O предпочитает наихудший сценарий производительности и всегда предполагает, что алгоритм выполнит максимальное количество итераций.
Предыдущий пример поиска имени в списке - хороший пример такой временной сложности. Количество операций напрямую влияет на количество времени, необходимое для выполнения вашей функции.
O (N²) - квадратичный
O (N²) представляет алгоритм, производительность которого прямо пропорциональна квадрату размера набора входных данных. Это обнаруживается в алгоритмах, которые включают вложенные итерации по набору данных. Более глубокие вложенные итерации приведут к O (N³), O (N⁴) и т. Д.
Это часто случается во вложенных циклах for, потому что внутренний цикл будет выполняться n раз при каждом запуске внешнего цикла. Это делает итоговую временную сложность n * n или n².
O(2^N)
O (2N) обозначает алгоритм, рост которого удваивается при каждом добавлении набора входных данных. Кривая роста функции O (2N) является экспоненциальной - сначала очень мелкой, а затем стремительно поднимающейся.
O (log n) - L огарифмический
O (log n) немного сложнее объяснить. При этом учитывается метод, называемый бинарным поиском. Это другой способ просмотра набора данных, чем простой просмотр каждого значения. Если вам нужно было найти определенное число в упорядоченном массиве чисел, вы могли просмотреть каждое из них и сравнить его с числом, которое вы ищете, пока не найдете желаемое число. К счастью, есть способ получше. Найдите минутку, чтобы просмотреть гифку ниже.
Здесь нам показывают двоичный поиск в сравнении со стандартным последовательным поиском. В примере двоичного поиска вы видите, что вместо того, чтобы смотреть на каждое число по порядку, мы просто разрезаем список пополам, смотрим на число в середине списка и спрашиваем, больше или меньше число, чем то, что мы ищем. Если число больше, мы делаем то же самое со второй половиной массива и продолжаем делать это до тех пор, пока не найдем наш номер или пока набор больше не может быть разделен.
Итеративное сокращение вдвое наборов данных дает кривую роста, которая достигает пика в начале и постепенно выравнивается по мере увеличения размера наборов данных. Например, если набор входных данных содержит 10 элементов, это может занять одну секунду. Если бы мы удвоили размер набора данных, это все равно заняло бы примерно такое же количество времени, потому что мы даем ему только одну дополнительную итерацию для завершения (20 сокращается до 10 на первой итерации). Если этот набор данных вместо этого содержит 100 элементов, это может занять две секунды, а если набор данных содержит 1000 элементов, это может занять три секунды. Увеличение размера набора входных данных мало влияет на его рост. Это делает такие алгоритмы, как двоичный поиск, чрезвычайно эффективными при работе с большими наборами данных.
Какая разница?
Это хороший вопрос. Ответ таков: большие компании заботятся, маленькие компании заботятся, а вам следует заботиться. Изучение нотации Big O поможет вам понять безумно важную концепцию повышения эффективности вашего кода. Когда вы работаете с большими наборами данных, вы быстро увидите разницу в выполнении эффективного кода и выполнения неэффективного кода.
Судя по всему, что я прочитал во время исследования этой темы, кажется, что расширение ваших знаний по таким концепциям, как нотация Big O и другим темам информатики, поможет вам получить преимущество в ваших интервью. Вы будете лучше подготовлены, чтобы продемонстрировать свой потенциал как потенциального сотрудника, продемонстрировав, что вы действительно заботитесь о качестве своего кода, а не просто заставляете ваш код делать то, что вы хотите, независимо от его эффективности.
