Всякий раз, когда вы решаете проблему в коде, есть большая вероятность, что решение, которое вы придумаете, не будет идентично решениям, предложенным другими разработчиками. Возможно, одному разработчику нравится создавать карты персонажей, а другому нравится сортировать пузырьками. В зависимости от того, над чем вы работаете, это МОЖЕТ (обратите внимание на заглавные буквы) не иметь большого значения. Однако во многих случаях вам НУЖНО обратить внимание на то, какое именно решение вы выберете. Почему? Разве смысл не в том, чтобы просто решить проблему, независимо от того, как это делается? Очевидно, что, поскольку я задаю вопрос, ответ явно отрицательный… вы не просто пытаетесь решить проблему. Вы ищете, как ЛУЧШЕ решить проблему.

Так как же разработчики определяют, какое решение является «лучшим»? Введите что-то под названием «Сложность времени выполнения», которая используется для описания производительности алгоритма. Всякий раз, когда вы определяете, как решить проблему кодирования, вы стремитесь выбрать САМОЕ ЭФФЕКТИВНОЕ решение с точки зрения производительности. Вы всегда должны спрашивать себя: насколько больше вычислительной мощности потребуется для запуска выбранного мной алгоритма или решения, если количество входных данных в этот алгоритм увеличится?

Хороший пример того, как думать о сложности среды выполнения, можно найти в простом алгоритме, в котором вам нужно перевернуть строку.

Для каждого дополнительного элемента в строке вам придется повторить цикл еще раз… поэтому ОДИН дополнительный ввод требует ОДНОГО дополнительного шага. Вот почему мы говорим, что существует соотношение 1:1 между объемом требуемой работы и входным набором. Таким образом, это пример линейной сложности времени выполнения, которая является одним из наиболее распространенных типов алгоритмических сложностей.

Давайте рассмотрим еще один пример, который иллюстрирует, что происходит на другом конце спектра сложности, где требуется больше вычислительной мощности. Я видел это, называемое проблемой «шагов», где вам дано положительное целое число, N. Ваша задача — написать функцию, которая принимает N, и консоль записывает форму шага с N уровнями, используя символ «#»… там должны быть пробелы с правой стороны для всех шагов, содержащих менее N символов '#'.

Вот итеративное решение этого алгоритма:

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

В этом решении мы видим два цикла for, один из которых вложен в другой. Когда мы начали увеличивать значение, которое мы вводим в наш алгоритм, нам приходилось делать гораздо больше действий каждый раз, когда n увеличивалось на 1. Это хороший пример квадратичной сложности выполнения или n².

Таким образом, эти два примера (которые, по сути, находятся на разных концах спектра сложности) действительно могут помочь нашему мозгу установить некую структуру, на основе которой мы можем построить наше понимание сложности среды выполнения. К сожалению, не существует волшебной формулы, которая в 100% случаев всегда определяет правильную сложность среды выполнения, а также не существует каких-либо жестких и быстрых правил относительно того, как именно это делается. Использование различных алгоритмов и отработка лучших решений — единственный способ получить полное представление о требуемой вычислительной мощности. При этом полезно знать некоторые распространенные среды выполнения и примеры этих сред выполнения.

Некоторые общие среды выполнения и примеры… и, о да, нотация Big(O).

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

Хорошо, теперь перейдем к некоторым распространенным типам сложностей среды выполнения и примерам.

Постоянная. Независимо от того, что мы вводим, это всегда будет занимать одинаковое количество времени. Это «Святой Грааль» кода, но почти никогда не происходит. В качестве примера вы можете представить себе необходимость всегда выводить только первый элемент коллекции, независимо от того, насколько длинна коллекция. В нотации Big(O) это представлено как O(1).

Логарифмический. Этот тип сложности обнаруживается, если мы удваиваем входные данные, но объем выполняемой нами работы точно не удваивается. Примером этого может быть поиск в отсортированных данных. В нотации Big(O) это представляется как O(log(n)).

Линейный. Это самый распространенный тип сложности. Вы увидите это, если перебираете один фиксированный набор данных; например, если вы используете цикл for, который проходит от нуля до array.length. В нотации Big(O) это представляется как O(n). Кроме того, если вы перебираете две разные коллекции с отдельными циклами for, вы можете выразить это как: O (n + m).

Квазилинейный. Этот тип сложности наблюдается, если при увеличении ввода на 1 объем работы увеличивается на 1 плюс некоторая небольшая сумма (то есть не линейная, но не совсем удвоенная). Это сложность, демонстрируемая многими различными алгоритмами сортировки. В нотации Big(O) это представляется как O(n*log(n)).

Квадратичный. Вы увидите эту сложность, когда каждый элемент в коллекции будет сравниваться с каждым другим элементом. Другими словами, чем больше вы вводите, тем больше времени уходит на выполнение алгоритма. Помните наше решение алгоритма «шагов»… этот тип сложности наблюдается, когда у вас есть два вложенных цикла for, перебирающих одну и ту же коллекцию. В нотации Big(O) это представляется как O(n²).

Экспоненциальный. Наконец, этот тип сложности наблюдается, если для каждого добавленного элемента вычислительная мощность Удваивается. Это, очевидно, значительное увеличение вычислительной мощности, и вы ДЕЙСТВИТЕЛЬНО этого не хотите. В нотации Big(O) это представляется как O(2^n).

Как я упоминал выше, чем больше вы привыкнете думать о сложности фрагментов кода во время выполнения, тем быстрее вы научитесь определять наиболее эффективное решение для использования. Поначалу к этому определенно нужно привыкнуть, но со временем вы обнаружите, что автоматически спрашиваете: «У какого из этих потенциальных решений лучшее время выполнения?»

Удачного кодирования!