Различия между временной сложностью и сложностью пространства?

Ответ 1

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), потому что вы не создаете дополнительных объектов. Итак, да, возможно, что алгоритм имеет разную временную и пространственную сложность, поскольку они не зависят друг от друга.

Ответ 2

Сложность времени и пространства - это разные аспекты вычисления эффективности алгоритма.

Сложность времени связана с выяснением того, как вычислительное время алгоритм изменяется с изменением размера ввода.

С другой стороны, сложность пространства имеет дело с выяснением, насколько (дополнительного) пространства потребуется алгоритм с изменением размер ввода.

Чтобы вычислить временную сложность алгоритма, лучший способ - проверить, увеличиваем ли мы размер ввода, будет ли количество сравнений (или вычислительных шагов) увеличиваться, а для вычисления сложности пространства лучше всего увидеть дополнительные потребность в памяти алгоритма также изменяется с изменением размера ввода.

Хорошим примером может быть 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) или постоянной сложности пространства.

Теперь как упражнение для вас, исследование сложности времени и пространства слияние сортировки

Ответ 3

Прежде всего, пространственная сложность этого цикла O(1) (вход обычно не включается при вычислении того, сколько памяти требуется алгоритму).

Итак, вопрос, который у меня есть, заключается в том, возможно ли, что алгоритм имеет разную временную сложность от пространственной сложности?

Да, это так. В общем, время и пространственная сложность алгоритма не связаны друг с другом.

Иногда можно увеличить за счет другого. Это называется коммьюнитом пространства-времени.

Ответ 4

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

Ответ 5

Существует известная связь между сложностью времени и пространства.

Прежде всего, время является очевидной привязкой к потреблению пространства: во времени 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).

Ответ 6

Способ, которым объем пространства памяти, требуемый алгоритмом, зависит от размера проблемы, которую он решает. Сложность пространства обычно выражается как порядок величины, например. O (N ^ 2) означает, что если размер задачи (N) удваивается, тогда потребуется в четыре раза больше рабочего хранилища.

Ответ 7

Иногда да, они связаны, а иногда нет, они не связаны, на самом деле мы иногда используем больше места для ускорения алгоритмов, как при динамическом программировании 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)