Я помню, как я был очень взволнован, просто увидев, как я работаю над кодом. Это дало желаемый результат. Это была первая метрика, которую я использовал для оценки своего кода, и она остается самой важной, но с тех пор было добавлено много других уровней оценки: длина кода, удобочитаемость, условность; а теперь сложность.
Нотация Big O - это сокращенный способ записать верхнюю границу или в худшем случае скорость, для которой алгоритм будет усложняться по мере роста его входных данных. Итак, если функция имеет на входе массив с n числовыми элементами, и она может выполнять все свои операции с этим массивом за x время, что произойдет, когда мы удвоим длина входного массива? Бежать нужно вдвое дольше? Меньше? Более? Намного больше? Обозначение Big O указывает, какова эта скорость изменения.
Большой O помечается заглавной O, за которой следуют круглые скобки, содержащие математическое соотношение. Таким образом, функция с линейным временем обозначается как O (n), а функция с квадратичным временем обозначается как O (n²).
Снижение временной сложности алгоритма - это, как правило, хорошая вещь, хотя стоит отметить, что алгоритмы, как правило, становятся более сложными с точки зрения логики для реализации, чтобы обеспечить более эффективное выполнение. Повышение логической сложности имеет свои собственные затраты, которые часто включают добавление большего количества строк кода, что создает возможность для ошибок и увеличивает сложность устранения неполадок. Помимо этого, по-прежнему важно понимать, какую среду выполнения вы можете ожидать от своих алгоритмов и как можно реорганизовать эти алгоритмы, чтобы сократить это время выполнения.
Имея это в виду, я хочу обсудить основы сложности Big O применительно к javascript. Я собираюсь рассказать о том, как общие операции JS связаны со сложностью, и расскажу о некоторых основных стратегиях уменьшения сложности.
Операции с постоянным временем O (1) являются самыми простыми и добавляют небольшую сложность алгоритму. Термин «постоянный» в этом контексте означает, что сложность остается неизменной и не увеличивается пропорционально входу. Когда вводимые данные становятся достаточно большими, их влияние становится незначительным, поэтому оно обозначено цифрой «1». Эти виды операций включают выполнение математических операций, таких как сложение и умножение, операции сравнения, присвоение переменных и индексов массивов или свойств объекта. Методы массива .push () и .pop () также имеют постоянное время.
Операции линейного времени O (n) масштабируются прямо пропорционально размеру входных данных. Функция, которая перебирает каждый элемент в массиве, имеет линейную временную сложность. Циклы For и while - это распространенные способы, которыми функция может перебирать каждый элемент во входных данных, таких как массив.
Имейте в виду, что нотация Big O указывает на взаимосвязь между входом и алгоритмом, но тот факт, что алгоритм имеет линейное время, не обязательно означает, что его входные данные представляют собой массив или некоторую структуру данных с элементами. Выполнение цикла количество раз, равное длине входного массива, является линейной зависимостью, но выполнение цикла количество раз, равное простому введенному целому числу, также создает линейную взаимосвязь.
Многие методы массива имеют линейную связь с длиной массива. Обратный. (), Sort. (), .Filter (), .map (), .reduce (), .find () и т. Д .; все они имеют время O (n), поскольку они могут выполнять операцию с каждым элементом в массиве. Даже если такой метод, как .includes (), прекращает итерацию после того, как находит первое истинное значение, он все равно имеет потенциал для наихудшего случая, связанного с необходимостью сравнения всего пути до последнего элемента, и поскольку Big O заботится о верхней границе или в худшем случае у него еще есть время O (n).
Методы .shift () и .unshift () также имеют отношение O (n), поскольку удаление или добавление в начало массива требует сдвига индекса каждого последующего элемента в массиве. Фактически, вставка данных в массив в любом месте, кроме конца, требует сдвига всех последующих значений индекса. Между тем, как упоминалось ранее, .push () и .pop () имеют O (1).
Линейное время в алгоритмах… нормально. Обычно это результат итерации, а повторение - неизбежная часть программирования. При итерации следует помнить, что любые операции, которые вы включаете в блоки итеративного кода, будут создавать мультипликативную связь со всем алгоритмом, поскольку этот код будет запускать каждую итерацию. Это приводит к алгоритмам с квадратичным временем или хуже.
Квадратичное время или O (n²) экспоненциально масштабируется с размером входных данных и чаще всего возникает из-за наличия вложенных линейных операций. Вы можете не заметить время выполнения между линейной и квадратичной операциями для небольших входных данных, но по мере роста входных данных разница становится резкой. Вложенность циклов for может вызывать квадратичные временные отношения, но то же самое может быть и вложение любой линейной операции времени внутри цикла; использование .shift () или .includes () внутри цикла также может вызывать квадратичное время. Если вы вкладываете цикл внутри цикла в цикл, тогда вы можете получить время O (n³) и так далее для каждого слоя вложения.
Квадратичное время или экспоненциальное время… менее точно, чем линейное. Я не думаю, что нужно избегать вложенности итеративного кода любой ценой. Просто поймите, что для итеративного кода существует мультипликативная стоимость, и что если вы обнаружите, что реализуете вложенные циклы или квадратично сложный код, вам следует искать способы рефакторинга и оптимизации ваших циклов.
Когда дело доходит до оптимизации алгоритмов, включающих циклы, если вы можете избежать использования линейно сложных операций внутри циклов, это прекрасно. Руководства по структурам данных и алгоритмам научат вас, как использовать различные концепции, такие как указатели, для отслеживания ключевых значений в структурах, чтобы избежать необходимости повторять их извне. Кроме того, научившись делать разумные предположения о своих данных, чтобы вы могли либо уменьшить объем данных, которые вам нужно перебрать, либо знать, когда вы можете безопасно выйти из итерации, вы сэкономите на времени выполнения.
Большой O и временная сложность - это концепции, с которыми многие инженеры-программисты сталкиваются впервые, когда узнают о структурах данных и алгоритмах, которые они обычно начинают изучать при подготовке к собеседованию. Но понимание структур данных и алгоритмов - это невероятно глубокая тема, которая имеет широкое значение, помимо хороших результатов на собеседованиях, и по мере того, как вы продолжаете изучать эту тему, я призываю вас сосредоточиться на разработке прочной основы для анализа производительности вашего кода. не только для собеседований, но и для себя. Просто постарайтесь не усложнять его больше, чем нужно.
