Итак, за последнюю неделю я понял, насколько важно начать изучать структуры данных и алгоритмы. Одна из тем, которую я затронул в начале своего буткемпа, называется Big O Notation, о которой я собираюсь написать в сегодняшней статье. Существует множество способов расчета и решения множества различных задач в области мягкой инженерии и программирования, большая нотация O — это один из способов, с помощью которого мы можем найти наиболее эффективный способ решения проблемы. Большой О может показать и научить различиям между решением проблемы тем или иным способом. Мы пытаемся выяснить, насколько большие алгоритмы могут расти по отношению к размеру их входных данных. Результат - сколько времени требуется для
«Обозначение Big O, уравнение, которое описывает, как время выполнения масштабируется по отношению к некоторым входным переменным» — HackerRank, 2016.
Давайте упростим это.
Просматривая видео на YouTube, чтобы полностью понять эту концепцию, я наткнулся на комментарий от Кристин Хилл, который действительно дал мне лучшее понимание, надеюсь, он поможет и вам. Однако я собираюсь написать это так, как я его интерпретировал, чтобы убедиться, что я учусь, когда пишу этот пост в блоге.
Допустим, вы готовите ужин для своей семьи. «О» — это процесс следования рецепту определенного блюда, например спагетти. Количество раз, которое вы следуете этому рецепту, обозначается «n». Теперь, когда я готовлю, я готовлю по-семейному, а это означает, что для приготовления потребуется только одно большое блюдо из спагетти. Рецепт, как накормить пятерых одним блюдом, нужно выполнить один раз. Или O из 1, где n равно 1. Теперь предположим, что вместо того, чтобы быть дома, я шеф-повар в ресторане (очевидно, потому что мне действительно нравится готовить), и я готовлю для 10 разных людей. люди, я бы сделал 10 отдельных блюд, следуя рецепту 10 раз. Это приводит к O(n), когда вы следуете рецепту сверху вниз для разного количества людей, которых вы обслуживаете.
По сути большой O — отличный способ определить сложность кода с его отношением ко времени в алгебраической терминологии (Undefined Behavior, 2017). Big O(n) — это линейное уравнение, так что в основном это означает, что оно работает с одним и тем же постоянным временем и скоростью на протяжении вечности. Все наклонные линии попадают под один и тот же большой O. Большой O(n^k) известен как полиномиальное время, в течение длительных периодов времени линейные уравнения большого O иногда могут казаться более быстрыми, но в долгосрочной перспективе полиномиальное время всегда будет быстрее, чем линейное время.
Большой O лучше всего использовать для поиска наихудшего случая при определении и анализе проблемы, для большинства проблем идеально подходит определение наилучшего случая, среднего случая и худшего случая. Таким образом, мы можем быть готовы к тому, что может произойти или не произойти. Время выполнения алгоритма часто может зависеть от конкретного ввода, некоторые алгоритмы могут позволить коду работать лучше или хуже.
Большой О может помочь нам определить, сколько места использует алгоритм. Это помогает нам с большими наборами данных или устройствами с меньшими возможностями памяти. Большой O стирает постоянные переменные, но в некоторых случаях это важно. Когда нам нужна производительность, например, в видеоигре, нам может понадобиться сэкономить каждый бит вычислений, даже если это не изменит большое время выполнения O. Экспоненциальный рост не страшен постоянно, если исходные данные всегда малы. Иногда мы можем использовать более ужасную большую букву O, если другие компоненты более важны. Я надеюсь, вам понравился мой краткий рассказ о Big O, определенно есть еще что-то, так как я едва коснулась поверхности и, надеюсь, заинтересовала вас!
Как лучше всего заявили Джастин Чен, Брэндон Чен, Элейн Чанг, Закари Гринберг в «Неопределенном поведении»,
Иногда медленный и устойчивый не выигрывает гонку. — 2017 г.
