Я видел, что в большинстве случаев сложность времени связана с пространственной сложностью и наоборот. Например, в траверсе массива:
for i=1 to length(v)
print (v[i])
endfor
в вышеупомянутом случае легко видеть, что сложность алгоритма по времени равна O (n), но для того, что я вижу, пространственная сложность также равна n (также можно представить O (n) также?)
Мой вопрос: возможно ли, что алгоритм имеет разную временную сложность от сложности пространства?
time и space не связаны друг с другом. Они используются для описания того, сколько пространства/времени выполняется вашим алгоритмом на основе ввода.
Например, если алгоритм имеет пробел сложность:
O(1) - константа - алгоритм использует фиксированное (малое) количество пространства, которое не зависит от ввода. Для каждого размера ввода алгоритм будет принимать одинаковое (постоянное) количество пространства. Это имеет место в вашем примере, поскольку вход не учитывается, и что имеет значение - время/пространство команды print.O(n), O(n^2), O(log(n))... - это указывает на то, что вы создаете дополнительные объекты в зависимости от длины ввода. Например, создавая копию каждого объекта v, сохраняя его в массиве и печатая его после этого, занимает пространство O(n) при создании дополнительных объектов n.В отличие от сложности время, сколько времени ваш алгоритм использует на основе длины ввода. Опять же:
O(1) - независимо от того, насколько велик вход, он всегда занимает постоянное время - например, только одна команда. Как
function(list l) {
print("i got a list");
}
O(n), O(n^2), O(log(n)) - снова он основан на длине ввода. Например
function(list l) {
for (node in l) {
print(node);
}
}
Обратите внимание, что оба последних примера занимают пространство O(1), поскольку вы ничего не создаете. Сравните их с
function(list l) {
list c;
for (node in l) {
c.add(node);
}
}
который занимает пространство O(n), потому что вы создаете новый список, размер которого зависит от размера ввода линейным способом.
В вашем примере показано, что сложность времени и пространства может отличаться. Для печати всех элементов требуется v.length * print.time. Но пространство всегда одно и то же - O(1), потому что вы не создаете дополнительных объектов. Итак, да, возможно, что алгоритм имеет разную временную и пространственную сложность, поскольку они не зависят друг от друга.
Сложность времени и пространства - это разные аспекты вычисления эффективности алгоритма.
Сложность времени связана с выяснением того, как вычислительное время алгоритм изменяется с изменением размера ввода.
С другой стороны, сложность пространства имеет дело с выяснением, насколько (дополнительного) пространства потребуется алгоритм с изменением размер ввода.
Чтобы вычислить временную сложность алгоритма, лучший способ - проверить, увеличиваем ли мы размер ввода, будет ли количество сравнений (или вычислительных шагов) увеличиваться, а для вычисления сложности пространства лучше всего увидеть дополнительные потребность в памяти алгоритма также изменяется с изменением размера ввода.
Хорошим примером может быть Bubble sort.
Предположим, вы попытались отсортировать массив из 5 элементов. В первом проходе вы сравните 1-й элемент со следующими 4 элементами. Во втором проходе вы сравните второй элемент со следующими тремя элементами, и вы продолжите эту процедуру до полного исчерпания списка.
Теперь, что произойдет, если вы попытаетесь отсортировать 10 элементов. В этом случае вы начнете с сравнения сравнения 1-го элемента со следующими 9 элементами, затем 2-го со следующими 8 элементами и так далее. Другими словами, если у вас есть массив элементов N, вы начнете с сравнения 1-го элемента с элементами N-1, затем 2-го элемента с элементами N-2 и так далее. Это приводит к сложности времени O(N^2).
Но как насчет размера. Когда вы отсортировали 5 элементов или 10 массивов элементов, вы использовали дополнительный буфер или пространство памяти. Вы могли бы сказать Да, я использовал временную переменную, чтобы сделать своп. Но изменилось ли количество переменных, когда вы увеличили размер массива с 5 до 10. Нет. Независимо от того, каков размер ввода, вы всегда будете использовать одну переменную для обмена. Ну, это означает, что размер ввода не имеет ничего общего с дополнительным пространством, которое вам потребуется, что приведет к O(1) или постоянной сложности пространства.
Теперь как упражнение для вас, исследование сложности времени и пространства слияние сортировки
Прежде всего, пространственная сложность этого цикла O(1) (вход обычно не включается при вычислении того, сколько памяти требуется алгоритму).
Итак, вопрос, который у меня есть, заключается в том, возможно ли, что алгоритм имеет разную временную сложность от пространственной сложности?
Да, это так. В общем, время и пространственная сложность алгоритма не связаны друг с другом.
Иногда можно увеличить за счет другого. Это называется коммьюнитом пространства-времени.
Да, это определенно возможно. Например, для сортировки n реальных чисел требуется O(n) пробел, но O(n log n) время. Это правда, что сложность пространства всегда является ограниченной по времени сложности, так как время инициализации пространства включено в время выполнения.
Существует известная связь между сложностью времени и пространства.
Прежде всего, время является очевидной привязкой к потреблению пространства: во времени t вы не можете достичь более O (t) ячеек памяти. Это обычно выражается по включению
DTime(f) ⊆ DSpace(f)
где DTime (f) и DSpace (f) - множество языков распознаваемые детерминированной машиной Тьюринга во времени (соответственно, пространство) O (f). То есть, если проблема может решается за время O (f), то оно также может быть решено в пространстве O (f).
Менее очевидно тот факт, что пространство обеспечивает привязку к времени. предполагать что на входе размера n вы имеете в своем распоряжении f (n) ячейки памяти, включая регистры, кеши и все такое. После написания этих ячеек всеми возможными способами вы можете в конечном итоге остановить свои вычисления, поскольку в противном случае вы повторно вводите конфигурацию, которую вы уже прошли, начав цикл. Теперь, на двоичном алфавите, f (n) могут быть записаны в 2 ^ f (n) разными способами, что дает нам временная верхняя граница: либо вычисление остановится в пределах этой границы, или вы можете принудительно завершить завершение, так как вычисление никогда не остановится.
Это обычно выражается в включении
DSpace(f) ⊆ Dtime(2^(cf))
для некоторой константы c. причина константы c состоит в том, что если L находится в DSpace (f), вы только знайте, что он будет распознан в пространстве O (f), а в предыдущем рассуждения, f была фактической границей.
Вышеуказанные соотношения включаются более сильными версиями, включая недетерминированные модели вычислений, то есть так, как они часто излагаются в учебниках (см., например, теорему 7.4 в Вычислительном Сложность по Papadimitriou).
Способ, которым объем пространства памяти, требуемый алгоритмом, зависит от размера проблемы, которую он решает. Сложность пространства обычно выражается как порядок величины, например. O (N ^ 2) означает, что если размер задачи (N) удваивается, тогда потребуется в четыре раза больше рабочего хранилища.
Иногда да, они связаны, а иногда нет, они не связаны, на самом деле мы иногда используем больше места для ускорения алгоритмов, как при динамическом программировании https://www.codechef.com/wiki/tutorial-dynamic-programming динамическое программирование использует memoization или снизу вверх, первый метод использует память для запоминания повторяющихся решений, поэтому алгоритм не должен перепрограммировать его, а просто извлекать из списка решений. и подход "снизу вверх" начинается с небольших решений и основывается на конечном решении. Здесь два простых примера: одна показывает связь между временем и пространством, а другая не показывает никакого отношения: предположим, что мы хотим найти суммирование всех целых чисел от 1 до заданного n целого числа: code1:
sum=0
for i=1 to n
sum=sum+1
print sum
Этот код использовал только 6 байт из памяти я = > 2, n = > 2 и sum = > 2 байта поэтому сложность времени O (n), а пространственная сложность O (1) code2:
array a[n]
a[1]=1
for i=2 to n
a[i]=a[i-1]+i
print a[n]
Этот код использовал как минимум n * 2 байта из памяти для массива поэтому сложность пространства равна O (n), а сложность времени также O (n)