Структуры данных и алгоритмы - самые важные и базовые концепции информатики. Большинство крупных компаний нанимают своих сотрудников на основе знаний DSA (структур данных и алгоритмов). Изучая DSA, вы не только получаете работу в крупных компаниях, но и учитесь эффективно кодировать.
В этой статье я расскажу вам о самой базовой концепции DSA, которая представляет собой нотацию Big O с использованием Javascript.
Структуры данных - это программный способ хранения данных, позволяющий эффективно использовать данные. Существует несколько типов структур данных, таких как массивы, связанный список, стек, очередь, двоичное дерево, куча, хеширование, граф, матрица, строки и расширенные структуры данных.
Например, мы можем сохранить список элементов с одинаковым типом данных, используя структуру данных array.
Алгоритмы? Это просто конечный набор последовательностей или, можно сказать, четко определенный компьютерный набор инструкций для решения проблемы или выполнения вычислений.
Для любой заданной проблемы может быть N решений. В целом это так. Если у меня есть проблема, и я обсуждаю ее со всеми своими друзьями, все они предложат мне разные решения. И я тот, кто должен решить, какое решение является лучшим, исходя из обстоятельств.
Точно так же для любой проблемы, которую необходимо решить с помощью программы, может быть бесконечное количество решений. Давайте рассмотрим простой пример, чтобы понять это.
Проблема:. Создайте функцию для сложения n чисел.
Решение 01:
Решение 02:
В приведенных выше решениях мы можем получить желаемый результат, но какое решение лучше для больших значений n. Как определить, какое решение лучше?
Чтобы проверить это, мы можем использовать performance.now (). Он покажет нам, сколько времени требуется нашему решению для выполнения проблемы.
Давайте разберемся.
Сначала для решения 01:
Для решения 02:
На двух снимках экрана выше вы можете увидеть разницу во времени, затраченном на выполнение фрагмента кода.
Второе решение намного быстрее, чем первое. Даже при более высоком значении n второй более надежен.
Из вышеупомянутой проблемы я хочу сказать, что именно так DSA помогает нам сделать наш код более эффективным и быстрым. Поэтому для анализа алгоритма мы используем нотацию Big-O.
Обозначение Big-O
Алгоритм является O (f (n)), если количество простых операций, которые должен выполнить компьютер, в конечном итоге меньше, чем постоянная величина, умноженная на f (n), по мере увеличения n.
- f (n) может быть линейным, f (n) = n
- f (n) может быть квадратичным, f (n) = n²
- f (n) может быть постоянным, f (n) = 1
- f (n) может быть чем-то совершенно другим
Сложность времени
Временная сложность алгоритма определяется как время, необходимое нашей программе или набору конечного фрагмента кода для выполнения данной задачи.
Временная сложность алгоритма чаще всего выражается с помощью нотации большой O . Это асимптотическая запись для представления временной сложности.
Полезные правила:
- Арифметические операции постоянны, O (1).
например: либо вы добавляете 2 +2, либо миллион + миллиардов, время, затрачиваемое на арифметические операции, одинаково в обоих случаях, то есть O (1). - Присвоение переменной постоянно.
- Доступ к элементу в массиве (по индексу) или объекту (по ключу) является постоянным.
- В цикле сложность - это длина цикла, умноженная на сложность того, что происходит внутри цикла.
Пример временной сложности уже объяснен выше. Задача нахождения суммы n чисел - лучший пример того, что нужно знать о временной сложности алгоритма.
В решении 01, когда мы выполняем выполнение с использованием цикла, временная сложность стала O (n), тогда как в решении 02 мы вернули сумму, только выполнив арифметическую операцию, временная сложность которой была O (1), что является постоянным.
Вот почему, если мы используем большое число для нахождения его суммы, решение 01 не лучший выбор.
Космическая сложность
Проще говоря, сложность пространства определяет дополнительную память, которую нам нужно выделить для выполнения кода в нашем алгоритме.
Иногда вспомогательное пространство путают с пространственной сложностью. Но вспомогательное пространство - это дополнительное пространство, или, можно сказать, временное пространство, используемое алгоритмом.
Сложность пространства = вспомогательное пространство + пространство, используемое входом
Вот список входов вместе с памятью, которую они потребляли:
- bool, char, unsigned char, signed char, __int8: 1 байт
- __int16, short, unsigned short, wchar_t, __wchar_t: 2 байта
- float, __int32, int, unsigned int, long, unsigned long: 4 байта
- double, __int64, long double, long long: 8 байт
Полезные правила:
- Большинство примитивных типов, таких как логические, числовые, неопределенные и нулевые, занимают постоянное пространство, O (1).
- Для строк требуется пространство O (n) (где n - длина строки)
- Типы ссылок обычно O (n), где n - длина (для массивов) или количество ключей (для объектов).
Итак, чтобы объяснить порядок сложности пространства, взгляните на два примера, показанных ниже. Здесь вы можете легко определить, что первый пример имеет постоянный порядок пространственной сложности, а второй пример - n-го порядка пространственной сложности.
Пример:
- Пространственная сложность O (1):
2. Пространственная сложность O (n):
Мне нравится, как нотация Big O помогает нам оптимизировать наш код javascript. Благодаря этому мы можем сделать наш код более эффективным и оптимизированным. На данный момент это все, чем я могу с вами поделиться, но еще кое-что о порядке сложности. Я поделюсь этим с вами в своих следующих статьях. А пока продолжайте изучать структуры данных и алгоритмы и улучшать свои логические навыки.
Посетите сайт FreeCodeCamp и перейдите в раздел узнать, это лучший бесплатный источник для изучения DSA для начинающих.
Пока вы изучаете DSA, вы можете судить или измерять свой потенциал DSA с помощью HackerRank, LeetCode, Codewars и CodeChef.
Удачного кодирования !! :)
