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

Question

Я видел, что в большинстве случаев сложность времени связана с сложностью пространства и наоборот. Например, в качестве траверс массива:

for i=1 to length(v) 
    print (v[i]) 
endfor 

в вышеупомянутом случае, легко видеть, что сложность алгоритма в терминах времени O (п), но для того, что я вижу сложность пространства также п (может он также будет представлен O (n)?)

Мой вопрос: Возможно ли, что алгоритм отличается сложностью во времени от космической сложности?

Answer 1

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

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

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

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

Answer 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) или постоянная сложность пространства.

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

Иногда да они связаны между собой, а иногда нет, они не связаны, на самом деле мы иногда используем больше пространства, чтобы получить более быстрые алгоритмы, как и в динамическом программировании https://www.codechef.com/wiki/tutorial-dynamic-programming динамического программирования использует запоминанием или снизу вверх, то первый метод использования памяти помнить о повторяющихся решениях, поэтому алгоритм должен не перепрограммировать его, а просто извлекать из списка решений. и подход «снизу вверх» начинается с небольших решений и основывается на конечном решении. Вот два простых примера, один показывает соотношение между временем и пространством, а с другой, показывают никакое отношение: предположим, что мы хотим найти сумму всех целых чисел от 1 до заданного п целое: code1:

sum=0 
for i=1 to n 
    sum=sum+1 
print sum 

Этот код используется только 6 байт из памяти я => 2, п => 2 и сумма => 2 байта поэтому сложность время О (п), в то время как пространство сложность 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)

Answer 7

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

Прежде всего, время является очевидной привязкой к потреблению пространства: во времени t вы не можете достичь более чем O (t) ячеек памяти. Это, как правило, выражается путем включения

      DTime(f) ⊆ DSpace(f) 

, где DTIME (е) и DSpace (е) является множество языков , распознаваемых детерминированной машиной Тьюринга во время (соответственно, пространство) О (е). То есть, если проблема может быть решена за время O (f), то она также может быть решена в пространстве O (f).

Менее очевидно тот факт, что пространство обеспечивает привязку к времени. Предположим, что на входе размера n вы имеете в своем распоряжении ячейки памяти f (n), , содержащие регистры, кеши и все такое. После того, как написавшие эти клетки в всевозможныхпуть вы можете в конечном итоге остановить свой расчет, поскольку в противном случае вы бы повторно конфигурацию вы уже прошли, начиная с циклом. Теперь, на двоичном алфавите, f (n) ячейки могут быть записаны в 2^f (n) разными способами, что дает нашу верхнюю границу времени : либо вычисление остановится внутри этой границы, либо , либо вы можете принудительно прекратить, так как вычисление никогда не прекратится.

Это обычно выражается во включении

      DSpace(f) ⊆ Dtime(2^(cf)) 

для некоторой константы с. причина константы c состоит в том, что если L находится в DSpace (f), вы только знаете, что оно будет распознано в пространстве O (f), а в предыдущих рассуждениях f была фактической границей.

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