Понимание сложности времени и пространства с помощью Big O

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

Большой О

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

Следующий логический вопрос, который следует задать, будет заключаться в том, как нотация Big O сравнивает сложность различных алгоритмов? Big O сравнивает размер входных данных с количеством операций, необходимых алгоритму для выполнения своей задачи. Таким образом, вы, вероятно, можете догадаться, что для фиксированного размера ввода, если алгоритм 1 выполняет меньше операций, чем алгоритм 2 (для той же задачи), то алгоритм 1 быстрее и эффективнее, чем 2. Если мы подумаем об этом, размеры ввода в реальном мире равны редко бывает одинаковым, поэтому важнее понять, как алгоритм ведет себя при увеличении размера входных данных, поскольку два алгоритма могут работать одинаково при размере входных данных 100, но иметь совершенно разную эффективность при размере входных данных 100 000 000. Это именно то, что представляет график выше, здесь вы можете увидеть некоторые из наиболее распространенных тенденций, которым следуют алгоритмы, где функция внутри O («функция») представляет ось Y, а «n» представляет ось X.

Универсальное место для всех ваших больших потребностей нажмите здесь.

Сложность времени

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

Давайте кратко рассмотрим пример временной сложности в алгоритме. Циклы — очень полезный инструмент при программировании, они помогают нам перебирать структуры данных и получать доступ к данным. Таким образом, временная сложность цикла равна O(n), а это означает, что для вставки заданного количества элементов внутрь массива нам потребуется выполнить итерацию по всем n элементам, используя цикл. Это означает, что для n элементов у нас будет n операций. Теперь давайте подумаем о ситуации, когда внутри цикла есть цикл, в этом случае временная сложность равна O(n²), что означает, что для n элементов нам нужно будет выполнить n операций в квадрате (определенно не масштабируемое решение).

Космическая сложность

Объемная сложность алгоритма — это объем памяти, необходимый для выполнения данной задачи. Важным моментом, который следует понимать как программисту, является то, что у нас нет бесконечной памяти, поэтому, как и временная сложность алгоритма, мы также должны учитывать его пространственную сложность. Давайте продолжим наши приведенные выше примеры с одним циклом, здесь мы пытаемся использовать цикл для заполнения массива «n» элементами, поэтому наша пространственная сложность равна O (n), поскольку вновь созданный массив будет занимать n пробелов в памяти. .