Как и временная сложность O (n ^ 2), потому что мы дважды перебираем массив длины n.
Временная сложность вашего кода не O(N²).
Перебор коллекции длиной N считается O(N) по временной сложности. Причина в том, что в нотации Big-Oh вас всегда интересует терм, который доминирует в функции. Когда вы достигаете достаточно большого значения N, константы начинают меньше влиять на общую производительность.
Это не означает, что они "не важны"; только то, что, поскольку N стремится к бесконечности, фактический эффект этих констант более аналогичен добавлению еще одной капли или ведра воды в океан. Это обозначение предназначено для того, чтобы дать вам приблизительное (не точное) представление о том, какое поведение следует ожидать от алгоритма, т.е. насколько хорошо он масштабируется по мере роста размера входных данных.
Это означает, что ваша функция может перебирать одну и ту же коллекцию 5 раз, и это будет O(5N), что по-прежнему равно O(N).
Но как тогда получить O(N²)? Вы начнете рассматривать их как начало вложения циклов друг в друга.
Пример A - O(N)
def linear(integers):
# no nesting
for i in integers: print(i)
for i in integers: print(i+1)
Пример B - O(N²)
def quadratic(integers):
# notice double nesting
for i in integers:
for j in integers:
print(i+j)
Пример C - O(N³)
def cubed(integers):
# notice triple-nesting
for i in integers:
for j in integers:
for k in integers:
print(i+j+k)
Вы найдете примеры O(N³) алгоритмов, если работаете с матрицами, по крайней мере, если используете наивные реализации. Если вам непонятно, это называется асимптотическая запись.
Также обратите внимание, что нотация Big-Oh выражает верхнюю границу времени работы алгоритма. Это означает, что это мера наихудшего сценария.
Например, линейный поиск несуществующего элемента в списке приведет к тому, что ваш алгоритм достигнет верхней границы O(N), потому что он должен проверять каждый элемент в списке.
или временная и пространственная сложность > O(n), поскольку первый цикл просто создает новую структуру данных в памяти?
То, что делает цикл, само по себе не имеет отношения к измерению в этом случае. Что важно, так это операция, которая здесь доминирует, а именно сравнения и приращения, которые заставляют циклы работать. Например, value % 2 != 0 — это операция с постоянным временем¹ или O(1), и она не окажет существенного влияния на время выполнения вашего кода.
Так что же такое космическая сложность?
Требуемое пространство также будет зависеть от размера и содержания входных данных. Наихудшим случаем для вашего алгоритма является массив различных целых чисел, что означает, что каждое значение уникально.
Если каждое значение уникально, то для каждого значения будет добавлена пара ключ/значение. Поэтому для алгоритма требуется O(N) места.
Обратите внимание, что это может быть меньше, но нотация big-O сообщает верхнюю границу.
Просто имейте в виду, что обычно существует компромисс между ограничениями времени/пространства, когда более быстрые алгоритмы могут потребовать больше памяти, а более эффективные альтернативы памяти могут потребовать больше времени.
¹Это предполагает, что мы определили арифметические операции, такие как +, -, /, *, % и т. д., как базовые операции, что обычно и делается.
12.11.2015
