Что значит писать эффективный код?
Эффективно: достижение максимальной производительности с минимальными затратами усилий и затрат.
Добро пожаловать в мой скромный блог. Так рада, что вы здесь! Присоединяйтесь ко мне в небольшом исследовании основ нотации Big O и эффективности кода.
Что такое эффективность кода…
Это модный термин, который часто используют на встречах, лекциях и блогах. Широко используется для описания скорости и надежности кода, он тесно связан с алгоритмической эффективностью и скоростью выполнения программного обеспечения во время выполнения. В то время, когда ИИ, масштабируемость и машинное обучение находятся на переднем крае разработки программного обеспечения, эта тема возникает снова и снова.
Что такое нотация Big O…
Это инструмент, используемый в компьютерных науках для описания производительности и эффективности алгоритма, а также для анализа общей производительности. Он используется для определения наихудшего сценария в отношении необходимого времени или пространства, используемого для завершения выполнения алгоритма. Big O - ценный инструмент для определения наилучшей реализации функции на основе производительности и дает нам возможность формально говорить о том, как время выполнения алгоритма изменяется в зависимости от входных данных.
Сложность времени vs сложность пространства
Обозначение Big O используется для измерения временной и пространственной сложности. Сложность времени: количество небольших операций, которые необходимо выполнить для завершения операции.
Сложность пространства: количество дополнительной памяти, которая должна быть выделена для выполнения кода в алгоритме. Часто упоминается как сложность вспомогательного пространства, что означает, что это относится к пространству, занимаемому алгоритмом, не включая пространство, занимаемое входами.
Типы сложности
Сложность времени может относиться к нескольким различным типам. Вот несколько наиболее распространенных типов.
1. Константа / O (1): всегда будет выполняться в одно и то же время или в одном и том же пространстве, независимо от размера набора входных данных.
2. Логарифмический / O (log n): степень, до которой фиксированное число должно быть увеличено для получения данного числа
3. Линейное / O (n ): сложность будет расти прямо пропорционально размеру входных данных
4. Линейноарифмический / O (nlog n): выполняет O (log n) операция для каждого элемента во входных данных.
5. Quadratic / O (n²): производительность прямо пропорциональна квадрату размера входных данных.
Некоторые полезные общие правила при определении сложности времени и пространства…
Отказ от ответственности: это общие правила, которые могут оказаться полезной отправной точкой, но они не всегда будут работать.
Сложность времени
- Арифметические операции постоянны
- Присвоение переменной является постоянным
- Доступ к элементам в массиве (по индексу) или к объекту (по ключу) является постоянным
- В цикле сложность - это длина цикла, умноженная на сложность того, что происходит внутри этого цикла.
Космическая сложность
- Большинство примитивов - это постоянное пространство. (логические, числа, неопределенное, нулевое)
- Для строк требуется пространство O (n), где n - длина строки.
- Типы ссылок обычно O (n), где n - длина массива или количество ключей для объектов.
Давайте разберемся с примерами!
В приведенном выше примере количество операций растет примерно пропорционально n. Таким образом, если n равно 100, то i будет добавлено к общему количеству раз 100.
Сложность времени для addUpToN будет линейной / O (n)
Что касается сложности пространства, addUpToN имеет 2 назначения переменных (всего и я). Эти переменные переназначаются, когда цикл завершает свою работу, но пространство, занимаемое этими переменными, остается неизменным независимо от размера входного набора данных.
Сложность пространства будет постоянной / O (1)
Здесь у нас есть 3 простые операции (умножение, сложение, деление). Независимо от размера n количество операций остается неизменным.
Время Сложность addUpToNAgain постоянна / O (1)
Будет возвращено только одно значение. Входное значение не изменяет пространство, выделяемое для этой функции. следовательно, сложность пространства также линейна / O (1)
Здесь у нас есть линейная операция O (n), вложенная в другую операцию O (n). По мере масштабирования входного n время выполнения возводится в квадрат.
Сложность времени для sumEachPair является квадратичной / O (n²)
Если мы помним из полезных общих правил ранее, ссылочные типы обычно равны O (n), что в это правда. Объем пространства, который необходимо выделить, напрямую зависит от входного значения.
Сложность пространства линейна / O (n).
Резюме…
Понимание временной и пространственной сложности кода, который мы пишем, является важным инструментом, который мы можем использовать, чтобы обеспечить максимально быстрое время выполнения и максимально быстрое выполнение, при этом оставаясь в пределах физической памяти системы, в которой он предназначен для работы.
1. Для анализа производительности алгоритма мы используем нотацию Big O
2. Нотация Big O может дать нам понимание на высоком уровне требований алгоритма к пространству и времени.
